Определение графа. Виды графов. Подграфы. Операции над графами

Изоморфизм. Помеченные и непомеченные графы. Матрицы, ассоциативные с помеченными графами.
Определение графа
Пусть задано конечное множество V , которое будем называть множеством вершин. Некоторые из этих вершин соединим ребрами, т.е. выделим в множестве V(2) всех двухэлементных подмножеств множества V некоторое подмножество Е, которое и будем называть множеством ребер графа. Итак, граф - это пара (V, Е), где V - конечное множество, а Е V(2). Более подробно множества V и Е обозначаются как VG и EG соответственно. Число card(VG) вершин графа G называют его порядком и обозначают через |G|.
Говорят, что две вершины u и v смежны, если множество {u,v} является ребром, и не смежны в противном случае. Если е = {u,v} - ребро, то вершины и и v называют его концами и говорят, что ребро е соединяет вершины u и v, Такое ребро обозначается символом uv. Два ребра называются смежными, если они имеют общий конец. Вершина о и ребро е называются инцидентными, если и является концом ребра е (т.е. е = uv) и не инцидентными в противном случае.
Множество всех вершин графа G, смежных с некоторой вершиной v, называется окружением вершины v и обозначается через NG(v) ИЛИ N(v).

Рис.1
Графы удобно изображать в виде рисунков, состоящих из точек (вершины графа) и линий, соединяющих некоторые из этих точек (ребра графа). Приведем примеры некоторых графов специального вида. Граф G называется полным, если любые две его вершины смежны, т.е. EG = (VG)(2). Полный граф порядка п обозначим Кп, число ребер в нем равно Сn2 = п(п — 1)/2. На рис.1, а изображен полный граф К5. Граф называется пустым , если в нем нет ребер. Пустой граф порядка п обозначим Оn. На рис.1 б,в показаны также простые циклы Сп для n = 3,4 , а на рис.1 г, д - простые цепи Рп для п = 4,5. Очевидно, что К2 = Р2 и К3 = С3.


Рис.2
На рис.2, а,б приведены два изображения простого цикла С5 , а также колее Wn для п = 3,4 (в,г).
Красивыми примерами являются графы пяти платановых тел (т.е. правильных многогранников): тетраэдра, куба, октаэдра, додекаэдра, икосаэдра.
Напомним, что разбиением множества S называется представление его в виде объединения подмножеств, никакие два из которых не пересекаются. Граф называется двудольным, если существует разбиение множества его вершин на части (доли) такие, что концы каждого ребра принадлежат разным частям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф, доли которого состоят из р и q вершин, обозначается символом Kp,q . При р = 1 получаем звезду К1,q. Легко проверить, что K1,1 = К2 = P2 , K1,2 = Р3. На рис. 3 изображены звезда K1,5 и двудольный граф K3,3. Как видно из определения, граф - это алгебраическая система с одним отношением специального вида. Следовательно, к графам применимы понятия гомоморфизма, изоморфизма и автоморфизма. В частности, два графа G и Н называются изоморфными, если существует биекция φ: VG → VH такая, что две вершины u,v VG соединены ребром тогда и только тогда, когда их образы φ(и), φ(v) соединены ребром в H. В этом случае пишем G H, Например, граф К3,3 на рис.3 изоморфен графу "а" на рис.4, а графы "б" и "в" на этом же рис. 4 не изоморфны. В некоторых ситуациях все же приходится различать изоморфные графы, и тогда полезно понятие помеченного графа. Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1,2,... , п. Отождествим каждую из вершин графа с ее номером и определим равенство помеченных графов G и Н одного и того же порядка: G = Н тогда, когда EG = EH. Различные помеченные графы могут быть изоморфны между собой.
Для произвольного графа G определяется дополнительный граф : множество вершин у него то же самое, что и у графа G, a E = V(2) \ EG, т.е. две вершины в смежны тогда и только тогда, когда они не являются смежными в G. Граф, изоморфный своему дополнению, называется самодополнительным. Например, K1,P4,C5 - самодополнительные графы.
Иногда приведенное выше определение графа недостаточно и приходится рассматривать более общие объекты, в которых две вершины могут быть соединены более чем одним ребром. Так возникает понятие "мультиграф". Дальнейшее обобщение состоит в том, что кроме кратных ребер допускаются еще и петли, т.е. ребра, соединяющие вершину саму с собой. Такой объект называется псевдографом. Изучаются также ориентируемые графы: это пара, состоящая из множества вершин V и из нек. подмнож. А декартова квадрата V2 (вместо V(2)), Если а = (u,v) А, то а изобр. дугой со стрелкой; и назыв. началом, а v - концом этой дуги.
Подграфы
Граф Н называется подграфом графа G, если VH VG, ЕН EG. Подграф Н называется остовным подграфом (или фактором), если VH = VG. Если множество ребер U = ЕН совпадет с множеством всех ребер графа G, оба конца которых принадлежат VH, то Н называется подграфом, порожденным множеством U. На рис.5 изображены граф G и три его подграфа H1, Н2 и H3, среди которых H3 является остовным, a Н2 - порожденным.
Важный класс подграфов составляют подграфы, полученные в результате удаления вершины v VG. Граф Gv = G - v получается из графа G в результате удаления вершины v и всех инцидентных ей ребер. С графами Gv связана знаменитая гипотеза.
Гипотеза реконструируемости (П. Кэлли, С. Улам, 1945 г.). Пусть G и H - два графа одного порядка п > 2 и система {Gv|v VG} совпадает с системой {Hu|u VH} в том смысле, что вершины можно перенумеровать так, что Gv Hu, для всех i. Тогда G Н.
Подтверждена реконструируемость графов для 3 ≤ п ≤ 10. Заметим, что для п = 2 эта гипотеза не верна. Операции над графами
Удаление вершины или ребра - это пример операций, уменьшающих число элементов графа. Рассмотрим теперь операции над графами, увеличивающими число вершин или ребер. Такова, например, операция добавления ребра е = uv, если вершины u и v графа G не являются смежными. В результате получается граф G + е, у которого эти вершины уже соединены ребром.
Граф H называется объединением (или наложением) графов F и G, если VH = VF VG и ЕН = EF EG (рис.6). В этой ситуации пишут H=F G
Объединение F G называется дизъюнктным, если VF VG = Ø.
Пусть Gi m (Vi, Ei) (i = 1, 2)- два графа. Произведением G1 G2 = G называется граф, для которого VG = V1 V2 - декартово произведение множеств вершин исходных графов, a EG определяется следующим образом: вершины (и1 , и2) и (w1 , w2) смежны в графе G тогда и только тогда, когда или и1=w1 , а и2 и w2 смежны в G2 , или и2=w2 , а и1 и w1 смежны в G1 (см. рис.7).
Рис. 7
Очевидно, что |G1 G2 | = |G1| |G2 |, |E(G1 G2 )| = |G1 | |EG2 | + |G2 | |EG1 |
С помощью операции произведения вводится рекуррентным образом важный класс графов – п-мерные кубы Qn: Q1=K2; Qn=K2 Qn-1 (n>l).
Граф Qn имеет порядок 2п, вершины его можно представить (0,1)-векторами длины п таким образом, что две вершины будут смежны тогда и только тогда , когда соответствующие векторы различаются ровно в одной координате.
Матрицы, ассоциированные с графом
В этом параграфе и далее (i,j)-й элемент матрицы М обозначается Mij. Пусть G - помеченный граф порядка п, VG = {1,2,... ,п}. Определим п n - матрицу А = A(G), положив

A(G) называется матрицей смежности графа G. Это симметрическая матрица с нулями на главной диагонали.
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов.
Так как при такой перестановке строк и столбцов не меняется ранг, характеристический многочлен и корни характеристического многочлена, то имеет смысл для графа G определить ранг - rankG, как ранг матрицы A(G), характеристический полином графа и спектр графа как множество всех корней характеристического полинома (корни вещественны в силу симметричности матрицы A(G)).
Если спектры двух графов различны, то они не изоморфны. Обратное, однако, не верно, как показывает пример неизоморфных графов K1,4 и С4 O1, у которых один и тот же характеристический полином х3(x2 - 4).
Вторая из матриц В = B(G) графа G называется матрицей Кирхгофа

Сумма элементов в каждой строке и в каждом столбце матрицы B(G) равна 0. Теорема остается справедливой и для матрицы Кирхгофа.

Powered by Drupal - Design by artinet