Связность графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w - вторым, называется дугой из v в w и обозначается (v, w). Заметим, что дуги (v, w) и (w, v) различны. На Рис. 3 изображен орграф, дугами которого являются (u, v), (v, v), (v, w), (v, w), (w, v), (w, u) и (w, z); порядок вершин на дуге указан стрелкой.
Рис 3
Рис. 4
Графы и орграфы - существенно различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги (Рис. 4).
Замечание по поводу терминологии. Язык теории графов, бесспорно, еще не стал стандартным - каждый автор вводит свою собственную терминологию. Я пользуюсь в основном терминологией Басакера и Саати . Некоторые специалисты по теории графов называют графом то, что мы назвали простым графом. Во многих случаях, и особенно в приложениях, под графом понимается орграф. Еще хуже, иногда графом называют объект, который получается, если снять условие конечности множества вершин или семейства ребер. (Если оба они бесконечны, будем называть соответствующий объект бесконечным графом; изучение бесконечных графов мы отложим до 8.) Следует подчеркнуть, что любое из перечисленных определений графа вполне допустимо, если только пользоваться им последовательно.
Прежде чем привести примеры некоторых важных типов графов (3), удобно дать еще несколько простых определений.
Две вершины v и w графа G называются смежными, если существует соединяющее их ребро (т. е. ребро вида {v, w}); при этом вершины v и w называются инцидентными этому ребру (а ребро - инцидентным этим вершинам). Аналогично, два различных ребра графа G называются смежными, если они имеют по крайней мере одну общую вершину. Степенью (или валентностью) вершины v графа G называется число ребер, инцидентных v; степень вершины v обозначается через ?(v). При вычислении степени вершины v будем учитывать петлю в v два раза, а не один (если только явно не сказано иное). Вершина степени 0 называется изолированной вершиной, вершина степени 1 называется висячей (или концевой) вершиной. Так, граф, изображенный на Рис. 2, имеет одну висячую вершину, одну вершину степени 3, одну - степени 6 и одну - степени 8.
Легко видеть, что если сложить степени всех вершин графа, то получится четное число - равное удвоенному числу ребер, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный еще двести лет назад Эйлеру, часто называют леммой о рукопожатиях. Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях). Из леммы о рукопожатиях сразу следует, что в любом графе число вершин нечетной степени должно быть четным.
Рис. 5
Два графа G1 и G2 называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в G1, равно числу ребер, соединяющих соответствующие вершины в G2. Так, два графа, изображенные на Рис. 5, изоморфны при соответствии u-l, v-m, w-n, x-p, y-q. Заметим, что эти графы имеют по шесть вершин - другие точки пересечения ребер вершинами не являются.
Подграфом графа G называется граф, все вершины которого принадлежат V(G), а все ребра принадлежат Е(G). Так, граф на Рис. 1 является подграфом графа, изображенного на Рис. 4, но не является подграфом ни одного из графов, приведенных на Рис. 5 (так как последние не содержат треугольников).
Наконец, матрицей смежности графа G с множеством вершин {v1, ..., vn} (соответствующей данной нумерации вершин) называется матрица А = (аij) размера n xn, в которой элемент аij равен числу ребер в G, соединяющих vi и vj. Например, на Рис. 6 дана матрица смежности графа, изображенного на Рис. 4. Можно получить несколько различных матриц смежности данного графа, меняя обозначения его вершин; это приведет к изменению порядка строк и столбцов матрицы A. Но в результате всегда получится симметричная матрица из неотрицательных целых чисел, обладающая тем свойством, что сумма чисел в любой строке или столбце равна степени соответствующей вершины (здесь каждая петля учитывается в степени вершины один раз).
Рис. 6
Обратно, по любой заданной симметричной матрице из неотрицательных целых чисел легко построить граф (единственный с точностью до изоморфизма), имеющий данную матрицу своей матрицей смежности. Отсюда следует, что теорию графов можно свести к изучению матриц особого типа.
2. Примеры графов
В этом параграфе я расскажу об исследованиях некоторых важных типов графов.
Вполне несвязные графы. Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Будем обозначать вполне несвязный граф с n вершинами через Nn; N4 показан на Рис. 1. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.
Полные графы. Простой граф, в котором любые две вершины смежны, называется полным графом. Полный граф с n вершинами оО, обычно обозначается через Кn. Графы K4 и K5 изображены на Рис. 2 и 3.3. Убедимся в том, что Кn имеет ровно n(n - 1)/2 ребер.
Рис. 1. оо
Регулярные графы
Граф, у которого все вершины имеют одну