Связность графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
и ту же степень, называется регулярным графом. Если степень каждой вершины равна 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). Заметим, что дополнение полного графа является вполне несвязным графом и наоборот; дополнение регулярного графа регулярно.
3. Связность графов
Одна из топологических характеристик графа. Граф называется связным, если для любых его вершин u и v существует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение (G)] наз. наименьшее число вершин, удаление к-рых (вместе с инцидентными им ребрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. Числом реберной связности [обозначение ?(G)] наз. наименьшее число ребер графа G, удаление к-рых приводит к несвязному графу. Граф G наз. k-связным, если (G) ? k, и k-реберно связным, если ?(G) ? k. Максимальный по включению k-связный подграф графа G наз. его k-связной компонентой; 1-связная компонента наз. компонентой связности. При исследовании коммуникационных и логических сетей числа связности соответствующих графов можно интерпретировать как степень надежности этих сетей.
В теории графов изучаются способы установления Г. с, условия, при к-рых граф явл