Связность графов

курсовая работа

§2. Примеры графов

В этом параграфе я расскажу об исследованиях некоторых важных типов графов.

Вполне несвязные графы. Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Будем обозначать вполне несвязный граф с n вершинами через Nn; N4 показан на Рис. 1. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.

Полные графы. Простой граф, в котором любые две вершины смежны, называется полным графом. Полный граф с n вершинами оО, обычно обозначается через Кn. Графы K4 и K5 изображены на Рис. 2 и 3.3. Убедимся в том, что Кn имеет ровно n(n -- 1)/2 ребер.

Рис. 1. оо

Регулярные графы

Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называемые также кубическими (или трехвалентными) графами (см., например, Рис. 5, 3,2 и 3.4), представляют особый интерес в связи с задачей раскраски. Другим известным примером кубического графа является так называемый граф Петерсена, показанный на Рис. 5. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф Кn -- регулярным степени n-1.

Платоновы графы. Среди регулярных графов особенно интересны так называемые платоновы графы -- графы, образованные вершинами и ребрами пяти правильных многогранников -- платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Граф К4 соответствует тетраэдру (Рис. 2); графы, соответствующие кубу и октаэдру, показаны на Рис. 4 и 3.6; граф, соответствующий додекаэдру, изображен на Рис. 4

Двудольные графы. Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 c какой-либо из V2 (Рис. 7); тогда G называется двудольным графом. Такие графы иногда обозначают G(V1,V2), если хотят выделить два указанных подмножества.

Двудольный граф можно определить и по-другому -- в терминах раскраски его вершин двумя цветами, скажем красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой -- синий.

Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V1 соединена с каждой вершиной из V2; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается Km,n, где m и n -- число вершин соответственно в V1 и V2. Например, на Рис. 8 изображен граф К4,3 а на Рис. 5 -- два варианта графа Kз,з. Заметим, что граф Km,n имеет ровно m+ n вершин и mn ребер. Полный двудольный граф вида K1,n называется звездным графом; на Рис. 9 изображен звездный граф K1,5.

Объединение и соединение двух графов. Существует несколько способов соединения двух графов для образования нового, больше го графа; проиллюстрируем два из них. Пусть даны два графа G1= (V(G1), Е(G1) и G2 -- (V(G2), Е(G2)), причем множества V(G1) и V(G2) не пересекаются; тогда объединением G1?G2 графов G1 и G2 называется граф с множеством вершин V(G1) U V(G2) и семейством ребер E(G1) U E(G2) (Рис. 10). Можно также образовать соединение графов G1 и G2 (обозначаемое G1 +G2), взяв их объединение и соединив ребрами каждую вершину графа G1 с каждой вершиной графа G2. Пример графа K2 + К3 дан на Рис. 11. Заметим, что граф Km,n можно было бы определить как соединение графов Nm и Nn. Операции объединения и соединения можно распространить на любое конечное число графов и что они коммутативны и ассоциативны.

Связные графы. Все рассмотренные графы, состояли «из одного куска». Исключениями были вполне несвязные графы Nn (n ? 2) и объединения графов, состоящие из «не соединенных друг с другом частей». Формализуем это различие, называя граф связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае.

Очевидно, что всякий несвязный граф G можно представить в виде объединения конечного числа связных графов -- каждый из таких связных графов называется компонентой (связности) графа G. (На Рис. 12 изображен граф с тремя компонентами.) Доказательство некоторых утверждений для произвольных графов часто бывает удобно сначала провести для связных графов, а затем применить их к каждой компоненте в отдельности.

Циклические графы и колеса. Связный регулярный граф степени 2 называется циклическим графом (или циклом); циклический граф, с n вершинами обозначается через Сn. Соединение графов N1 и Сn-1 (n ? 3) называется колесом с n вершинами и обозначается Wn. На Рис. 13 изображены С6 и W6; граф W4 уже появлялся на Рис. 2.

Дополнение простого графа. Пусть G -- простой граф

с множеством вершин V(G). Дополнением G графа G называется простой граф с множеством вершин V(G), в котором две вершины смежны тогда и только тогда, когда они не смежны в G. Отсюда следует, что если граф G содержит n вершин, то граф G можно построить, удалив из графа Кn все ребра, принадлежащие G (здесь G считается подграфом Kn). Заметим, что дополнение полного графа является вполне несвязным графом и наоборот; дополнение регулярного графа регулярно.

Делись добром ;)