Графы
Основные определения
Приведен список основных терминов и их определений, встречаемых в литературе по графам.
Основные определения
- Граф
- Неориентированный граф
- Неорграф
- — совокупность \(G (V, E)\) непустого множества вершин \(V \neq \emptyset\) и множества ребер — двухэлементных подмножеств множества \(V\): \(E \subset \{ e \in 2 ^V | \left| e \right| = 2 \}\).
- Смежность
- Инцидентность
- Две вершины \(u, v\) называют смежными в графе \(G (V, E)\) тогда и только тогда, когда существует соединяющее их ребро \(\{u, v\} \in E\). Такое ребро называют инцидентным вершинам \(u, v\); вершины, в свою очередь, также называют инцидентными данному ребру.
- Множество смежности
- Окрестность
- — множество вершин \(\Gamma ^+\), смежных с данной.
- \[\begin {split} \Gamma ^+ (v) &\overset {\text {df}} = \{ u \in V | \{u, v\} \in E \};\\ \Gamma ^* (v) &\overset {\text {df}} = \Gamma ^+ (v) \cup \{v\} \subset \Gamma ^+ (v). \end {split}\]
- Диаграмма
- — изображение графа. Принято обозначать вершины — кружками, ребра — линиями.
- Ориентированный граф
- Орграф
- Узел
- Дуга
- Если множество \(E\) состоит из упорядоченных пар (кортежей длины 2) различных вершин: \(E \subset V ^2 \wedge \forall \langle u, v\rangle \in E u \neq v\), то \(G (V, E)\) называют ориентированным графом, или орграфом. Элементы \(V\) тогда называют узлами; элементы \(E\) — дугами.
- Граф с петлями
- Псевдограф
- Если в множестве \(E\) найдется элемент, являющийся множеством, состоящим из единственной вершины, \(\exists e \in E \exists v \in V : e = \{v\}\) (или иначе: элемент, являющийся парой одинаковых вершин, \(\exists e \in E \exists v \in V : e = \langle v, v\rangle\)), то \(G (V, E)\) называют графом с петлями, или псевдографом. (Иногда, однако, к псевдографам относят кроме того и мультиграфы.)
- Мультиграф
- Кратное ребро
- Если \(E\) является мультимножеством, содержащим некоторые элементы более одного раза, то \(G (V, E)\) называют мультиграфом; такие элементы \(E\) — кратными ребрами.
- Гиперграф
- Гипердуга
- Если множество \(E\) содержит элементы, являющиеся непустыми подмножествами \(V\), мощность которых отлична от 2, \(\exists e \in E : e \in 2 ^V \wedge e \neq \emptyset \wedge \left| e \right| \neq 2\), то \(G (V, E)\) называют гиперграфом; такие элементы \(E\) — гипердугами.
- Помеченный граф
- Нагруженный граф
- Нумерованный граф
- Если задана функция, ставящая в соответствие каждой вершине (ребру) графа \(G (V, E)\) некий элемент множества \(M\), то такое множество называют множеством пометок, а сам граф — помеченным. Если различным вершинам (ребрам) всегда соответствуют различные пометки, то граф называют нумерованным.
- Изоморфные графы
- Графы \(G _1 (V _1, E _1)\), \(G _2 (V _2, E _2)\) называют изоморфными тогда и только тогда, когда существует взаимно-однозначное соответствие между элементами \(V _1\), \(V _2\), сохраняющее смежность.
- \[\begin {multline} G _1 (V _1, E _1) \sim G _2 (V _2, E _2)\\ \Leftrightarrow \left\{ \begin {split} & \exists h : V _1 \leftrightarrow V _2,\\ & \forall u, v \in V _1 \{u, v\} \in E _1 \Leftrightarrow \{h (u), h (v)\} \in E _2). \end {split}\right. \end {multline}\]
- Инвариант графа
- — числовая характеристика, равная для всех изоморфных графов. В частности, такими характеристиками являются количества вершин и ребер \(p, q\).
- \[\begin {align} p (G) &\overset {\text {df}} = \left| V \right|, & q (G) &\overset {\text {df}} = \left| E \right|.\\ \end {align}\]
- Подграф
- Изграф
- Часть графа
- Граф \(G' (V', E') : V' \subset V \wedge E' \subset \left(E \cap 2 ^{V'}\right)\) называют подграфом графа \(G (V, E)\).
- Правильный подграф
- Подграф
- Подграф \(G' (V', E')\) называют правильным тогда и только тогда, когда он включает все ребра исходного графа, инцидентные его собственным вершинам, \(E' = \left(E \cap 2 ^{V'}\right)\).
- Остовный подграф
- Частичный граф
- — подграф \(G' (V', E')\), множество вершин которого совпадает с таковым исходного графа, \(V' = V\).
- Вполне несвязный подграф
- Нуль-граф
- — подграф \(G' (V', E')\), множество вершин которого совпадает с таковым исходного графа, а множество ребер — пусто. \(V' = V \wedge E' = \emptyset.\)
- Степень
- Валентность
- — количество ребер \(d\), инцидентных данной вершине; или, иначе, — количество вершин, смежных с данной. Максимальная и минимальная степени \(\delta, \Delta\) вершин графа являются его инвариантами.
- \[\begin {align} d (v) &\overset {\text {df}} = \left| \Gamma ^+ (v) \right|; & \bar d (v) &\overset {\text {df}} = \left| V \backslash \Gamma ^* (v) \right|\\ \sum _{v \in V} d (v) & = 2 q; & & = p - 1 - d (v);\\ \delta (G) &\overset {\text {df}} = \min _{v \in V} d (v); & \Delta (G) &\overset {\text {df}} = \max _{v \in V} d (v).\\ \end {align}\]
- Изолированная вершина
- — вершина, не смежная никаким другим, \(d (v) = 0\).
- Висячая вершина
- Концевая вершина
- — вершина, смежная единственной другой вершине, \(d (v) = 1\).
- Полустепень исхода
- Полустепень захода
- — число дуг, исходящих (\(d ^-\)) из данного и входящих (\(d ^+\)) в данный узел, соответственно.
- \[ \sum _{v \in V} d ^- (v) + \sum _{v \in V} d ^+ (v) = 2 q. \]
- Регулярный граф
- Однородный граф
- — граф, степени всех вершин которого равны некоторому числу \(r (G)\) — степени регулярности графа. \(G (V, E) : \forall v \in V \ d (v) = r (G).\)
- Полный граф
- — граф \(K _p\), в котором любые две вершины — смежны, \(\forall u, v \in V \exists \{u, v\} \in E\).
- Клика
- — полный подграф некоторого графа.
- Двудольный граф
- Доли графа
- Двудольным называют граф, в котором множество вершин может быть разбито на два непересекающихся подмножества \(\exists V _1, V _2 \subset V : V _1 \cup V _2 = V \wedge V _1 \cap V _2 = \emptyset\) — доли графа, причем каждое ребро инцидентно как вершине из \(V _1\), так и вершине из \(V _2\): \(\forall e \in E \exists v _1 \in V _1 \exists v _2 \in V _2 : e = \{v _1, v _2\}\).
- Полный двудольный граф
- Если для каждой пары вершин из разных долей существует инцидентное им ребро, \(\forall v _1 \in V _1 \forall v _2 \in V _2 \exists e \in E : e = \{v _1, v _2\}\), причем \(m = \left| V _1\right|, n = \left| V _2\right|\), то такой граф называют полным двудольным графом \(K _{m, n}\).
- Антисимметричный орграф
- Направленный орграф
- — ориентированный граф (орграф), получаемый из неориентированного заданием ориентации для каждого из ребер.
- Турнир
- — направленный орграф, получаемый из полного графа.
- Основание ориентированного графа
- — неориентированный граф (неорграф), получаемый из ориентированного «забыванием» ориентации каждой из дуг.
- Матрица смежности
- Матрица инциденций
- Списки последователей
- Список ребер
- Структура графа может быть представлена матрицей смежности, \(M _{ij}\), матрицей инциденций (инцидентности) \(H _{ij}\), списками последователей \(\Gamma _i\), или же списком ребер (дуг) \(\langle e _1, \dots, e _q\rangle\). Все эти способы несложно распространить на случаи ориентированных графов, графов с петлями и мультиграфов.
- \[\begin {align} M _{ij} & = \begin {cases} 1, & \{v _i, v _j\} \in E,\\ 0, & \text {иначе}, \end {cases} & i, j \in \{1, \dots, p\};\\ H _{ij} & = \begin {cases} 1, & v _i \in e _j,\\ 0, & \text {иначе}, \end {cases} & i \in \{1, \dots, p\}, j \in \{1, \dots, q\}.\\ \end {align}\]
- Диаграмма Хассе
- Любому ориентированному графу (возможно — с петлями, но без кратных ребер) можно поставить в соответствие некоторое бинарное отношение \(R : \forall u, v \in V \quad u R v \Leftrightarrow \langle u, v\rangle \in E\). В случае транзитивного отношения, для каждой пары дуг, такой, что конечный узел первой дуги совпадает с начальным второй, всегда найдется третья, соединяющая начало первой с концом второй, и называемая транзитивной замыкающей дугой; \(\forall e _1, e _2 \in E : e _1 = \langle u, v\rangle \wedge e _2 = \langle v, w\rangle \exists e _3 \in E : e _3 = \langle u, w\rangle\). Изображение такого графа — за исключением петель и транзитивных замыкающих дуг — в виде диаграммы называют диаграммой Хассе.
Маршруты, цепи, циклы
- Маршрут
- — последовательность вершин и ребер \(v _0, e _1, v _1, \dots, e _k, v _k\), начинающаяся и заканчивающаяся вершиной, в которой любые два соседних элемента — инцидентны.
- Открытый маршрут
- Замкнутый маршрут
- Открытым называется маршрут, начальная и конечная вершины которого — различны. Если они совпадают, маршрут называется замкнутым.
- Цепь
- Простая цепь
- Путь
- Маршрут, в котором все ребра различны, называют цепью (в случае орграфа — путем.) Цепь с концами \(u = v _0, w = v _k\) обозначают \(\langle u, w\rangle\) или (путь в орграфе) \(\vec {\langle u, w\rangle}\). Если же различны все вершины, маршрут называют простой цепью.
- Цикл
- Простой цикл
- Контур
- Замкнутую цепь называют циклом (в орграфе — контуром); простую цепь — простым циклом. (Граф, состоящий из единственного цикла с \(p\) вершинами, обозначают \(C _p\).) Количество циклов в данном графе \(z (G)\) является его инвариантом.
- Ациклический граф
- — граф без циклов, \(z (G) = 0\).
Расстояния в графе
- Длина маршрута
- — количество ребер в маршруте.
- Расстояние
- Геодезическая цепь
- Расстоянием между вершинами называют длину кратчайшей из соединяющих их цепей, \(d (u, v) \overset {\text {df}} = \min _{p \in \{\langle u, v \rangle\}} \left| p \right|\). Саму кратчайшую цепь называют геодезической.
- Геодезический граф
- — граф, в котором для любых двух вершин существует единственная геодезическая цепь.
- Ярус
- — множество вершин \(D (v, n)\), находящихся на заданном расстоянии \(n\) от \(v\), \(D (u, v) \overset {\text {df}} = \{u \in V | d (v, u) = n\}\).
- Диаметр графа
- — длиннейшая геодезическая цепь графа; или же ее длина (другими словами — наибольшее расстояние между вершинами в графе), \(D (G) \overset {\text {df}} = \max _{u, v \in V} d (u, v)\).
- Эксцентриситет вершины
- — максимальное расстояние от данной вершины до всех прочих, \(e (v) \overset {\text {df}} = \max _{u \in V} d (v, u)\).
- Радиус графа
- — наименьший из эксцентриситетов вершин, \(R (G) \overset {\text {df}} = \min _{v \in V} e (v)\).
- Центральная вершина
- — вершина, эксцентриситет которой совпадает с радиусом графа, \(e (v) = R (G)\).
- Периферийная вершина
- — вершина, эксцентриситет которой совпадает с диаметром графа, \(e (v) = D (G)\).
- Центр графа
- — множество всех центральных вершин, \(C (G) \overset {\text {df}} = \{v \in V | e (v) = R (G)\}\).
Связность
- Связанные вершины
- — вершины, для которых существует связывающая их простая цепь. Отношение связанности вершин является эквивалентностью.
- Компонента связности
- — класс эквивалентности по отношению связанности. Число компонент связности графа \(k (G)\) является его инвариантом.
- Связный граф
- — граф \(G (V, E)\), в котором каждая пара вершин — связана, \(\forall u, v \in V \exists \langle u, v\rangle\); или же \(k (G) = 1\).
- Вполне несвязный граф
- — граф, состоящий только из изолированных вершин, \(k (G) = p (G), r (G) = 0\).
- Точка сочленения
- Разделяющая вершина
- — вершина, удаление которой увеличивает число компонент связности графа.
- Мост
- — ребро, удаление которого увеличивает число компонент связности графа.
- Блок
- — связный граф, не имеющий точек сочленения.
- Вершинная связность
- — наименьшее число вершин \(\chi (G)\), которое необходимо удалить, чтобы получить несвязный или тривиальный граф.
- n-связный граф
- — граф, вершинная связность которого равна n.
- Реберная связность
- — наименьшее число ребер \(\lambda (G)\), которое необходимо удалить, чтобы получить несвязный или тривиальный граф.
- \[ \chi (G) \leqslant \lambda (G) \leqslant \delta (G). \]
- Вершинно-непересекающиеся цепи
- — цепи, не содержащие общих вершин.
- Реберно-непересекающиеся цепи
- — цепи, не содержащие общих ребер.
- Разделяющее множество
- — такое множество \(S (u, v)\) вершин и (или) ребер, при вычитании которого из некоторого графа \(G\), заданные вершины \(u, v\) оказываются принадлежащими различным компонентам связности результирующего графа: \(\not \exists \langle u, v\rangle _{G'}, G' = G - S.\)
- \[\left\{ \begin {align} G _1 \cup G _2 & = G - S (u, v), & u & \in G _1,\\ G _1 \cap G_2 & = \emptyset, & v & \in G _2.\\ \end {align} \right.\]
- Разрез
- — разделяющее множество ребер.
- Простой разрез
- Коцикл
- — такой разрез, никакой собственное подмножество которого не является разделяющим ни для каких вершин.
- Теорема Менгера
- (В «вершинной форме».) Наименьшее число вершин в множестве \(S (u, v)\), разделяющем вершины \(u, v\), равно наибольшему количеству вершинно-непересекающихся простых цепей \(\langle u, v\rangle\), связывающих эти вершины.
- \[ \max \left| P (u, v) \right| = \min \left| S (u, v) \right|. \]
- Система различных представителей
- Трансверсаль
- — подмножество \(C = \{c _1, \dots, c _n\}\) конечного множества \(E\) такое, что \(c _i \in S _i \forall i \in \{1, \dots, n\}\), где \(S _i \subset E\) — некоторые (не обязательно различные) подмножества \(E\).
- Независимое множество ребер
- Паросочетание
- — множество ребер, в котором никакие два ребра не смежны.
- Максимальное паросочетание
- — паросочетание, не являющееся подмножеством никакого другого паросочетания.
- Совершенное паросочетание
- (из \(V _1\) в \(V _2\)) — паросочетание, покрывающее вершины доли \(V _1\) заданного двудольного графа.
- Теорема Холла
- Совершенное паросочетание из \(V _1\) в \(V _2\) для двудольного графа \(G (V _1, V _2, E)\) существует тогда и только тогда, когда \(\forall A \subset V _1 \quad \left| A \right| \leqslant \left| \Gamma (A) \right|\).
Связность в ориентированных графах
- Сильная связность
- Односторонняя связность
- Слабая связность
- Узлы \(u, v \in V\) ориентированного графа \(G (V, E)\) сильно связаны, если существует как путь \(\vec {\langle u, v\rangle}\), так и обратный ему \(\vec {\langle v, u\rangle}\). Узлы называют односторонне связанными, если существует лишь один из таких путей. Наконец, если узлы связаны в (неориентированном) основании графа, их называют слабо связанными. Если все узлы орграфа обладают каким-либо из этих свойств, то говорят, что таким свойством обладает и орграф в целом. (Например: слабо связным называют орграф, все пары вершин которого слабо связанны.)
- Компонента сильной связности
- КСС
- — максимальный сильно связный подграф данного ориентированного графа.
- Конденсация графа
- Граф Герца
- Фактор-граф
- — ориентированный граф \(G ^*\), получаемый стягиванием каждой компоненты сильной связности графа \(G\) в один узел.
Литература
- Новиков, Ф. А. Дискретная математика для программистов. — СПб.: Питер, 2011.
- Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики. — М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002.
- Шевелев, Ю. П. Дискретная математика. Ч. 2: Теория конечных автоматов. Комбинаторика. Теория графов. (Для автоматизированной технологии обучения «Символ»). — Томск: Том. гос. ун-т систем упр. и радиоэлектроники, 2003.