А.В. Бирюков Графы. Методические указания к изучению раздела программы курса математики для студентов всех специальностей

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра высшей математики

ГРАФЫ

Методические указания к изучению раздела программы курса математики для студентов всех специальностей

Составитель А. В. Бирюков

Утверждены на заседании кафедры Протокол № 3 от 16.05.03

Рекомендованы к печати учебнометодической комиссией по специальности 290300 Протокол № 27 от 3.06.03

Электронная копия хранится в библиотеке главного корпуса ГУ КузГТУ

КЕМЕРОВО 2003

1

Граф обычно представляют рисунком, на котором изображены точки и отрезки, соединяющие некоторые пары точек. Точки – это вершины графа, а отрезки – его ребра.

Две вершины смежны, если они соединены ребром. Ребра смежны, если они имеют общую вершину.

Граф с n вершинами и m ребрами называют (n, m) – графом. Число вершин графа – это его порядок. Число ребер, выходящих из вершины, есть степень этой вершины.

Если степень вершины равна нулю или единице, то вершину называют соответственно изолированной и концевой. Граф, у которого степени всех вершин одинаковы, регулярен.

На рис. 1 приведены все графы четвертого порядка.

1

2

3

4

5

6

7

8

9

10	11
	Рис. 1.

2

У графа 1 все вершины имеют степень 3, т.е. он является регулярным. Графы 4, 5, 7, 8, 9, 10 имеют концевые вершины, а графы 3, 8, 10, 11 - изолированные вершины.

Кроме графического изображения граф может быть задан списком вершин и ребер. Например, граф 1 на рис. 1 имеет список вершин (1, 2, 3, 4) и список ребер (12, 23, 34, 41, 13, 24).

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

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

Для любого (n, m) – графа выполняются неравенства

0 ≤ m ≤ n(n −1)2 .

Если m=0 (т.е. все вершины изолированные), то граф называется пустым или тривиальным. Если же m=n(n-1)/2, то любые две вершины графа смежны. Такой граф называется полным. На рис. 1 первый граф – полный, последний – пустой.

Граф называется подграфом данного графа, если все его вершины и ребра принадлежат данному графу.

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

Маршрут называется цепью, если все его ребра различны (вершины могут повторяться). Простая цепь – это цепь, в которой

3

все вершины (кроме, может быть, начальной и конечной) различны.

Если начальная и конечная вершины простой цепи совпадают, то она называется простым циклом.

Граф называется связным, если любые две его вершины соединены маршрутом. На рис. 1 связными являются графы с первого по пятый и граф 7.

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

Наибольшее расстояние между всевозможными парами вершин графа называется его диаметром. На рис. 2 приведены графы шестого порядка – веер, колесо, звезда и простой цикл. Легко видеть, что диаметры первых трех графов равны 2, а диаметр цикла равен 3.

Рис. 2.

Если удаление ребра в связном графе делает его несвязным, то это ребро называется мостом. Если удаление вершины делает

4

граф несвязным, то ее называют точкой сочленения. На рис. 3 ребро 12 является мостом, а вершина 1 – точкой сочленения.

Рис. 3.

Связный граф без циклов называется деревом. У дерева любое ребро является мостом, а любые две вершины можно соединить единственной простой цепью.

Для (n, m) – графа равенство

m = n - 1

выполняется тогда и только тогда, когда граф является деревом. Остовом связного графа называют подграф, который является

деревом и содержит все вершины данного графа. На рис. 4 приведены граф и два его остова.

Рис. 4.

Цикл, содержащий все ребра графа, называется эйлеровым. Граф, у которого имеется эйлеров цикл, называется эйлеровым графом. Любой эйлеров граф связен и не имеет мостов, а все его вершины имеют четные степени.

Для построения эйлерова цикла применяется следующий алгоритм Флери. В эйлеровом (n, m) – графе А выбираем любое реб-

5
ро и включаем его вершины в цепь	X 0 , X1 . Пусть уже построена
цепь X 0 , X1 ,..., X K и пусть В-граф,	полученный из А удалением

всех ребер этой цепи. Выбираем в В ребро X K X K +1 , которое не является мостом, если такое есть; в противном случае берем любое ребро, выходящее из вершины X K . Получаем цепь X 0 X1...X K X K +1 . Построение заканчивается после m шагов. При этом всегда начало и конец цепи совпадают.

Граф называется гамильтоновым, если в нем есть простой цикл, содержащий все вершины графа. Алгоритм построения гамильтонова цикла сводится к перебору простых цепей с фиксиро-

ванной	начальной вершиной X 0 . Пусть	уже построена	цепь
X 0 ...X K .	Продолжим ее до цепи X 0 ...X K +1 ,	если это возможно.		В
противном случае из построенной цепи исключаем вершину			X K	и

ищем другие возможные продолжения цепи. Алгоритм заканчивает работу, когда будут рассмотрены все цепи, начинающиеся с X 0 .

Множество вершин графа называется независимым, если любые две вершины не смежны. Раскраской графа в N цветов называется разбиение множества его вершин на N независимых множеств, в каждом из которых вершины имеют один цвет.

В этом случае любые две смежные вершины имеют разный цвет. Наименьшее значение N, для которого существует раскраска графа в N цветов, называется хроматическим числом графа, а соответствующая раскраска – минимальной.

Хроматическое число равно единице лишь у пустого графа. Граф, у которого хроматическое число равно двум, называется двудольным (рис. 5).

6

Рис. 5.

Алгоритм последовательной раскраски находит раскраску графа в N цветов, где N не превосходит максимальной степени вершин, увеличенной на единицу. Произвольно выбранной вершине присвоим цвет 1. Если уже раскрашены N вершин, то вершине с номером N+1 присваиваем цвет с наименьшим номером, отличный от цветов всех смежных с ней вершин.

Такая раскраска в общем случае не является минимальной. Для построения минимальной раскраски применяется перебор, аналогичный алгоритму поиска гамильтонова цикла. Более эффективные алгоритмы вычисления хроматического числа неизвестны.

Граф называется плоским, если его вершины являются точками плоскости, а ребра – отрезками, причем несмежные ребра не имеют общих точек, а два смежных ребра пересекаются только в их общей вершине.

Граф называется планарным, если он изоморфен некоторому плоскому графу. Соответствующий изоморфизм называют укладкой графа на плоскость.

Любой плоский граф разбивает плоскость на конечное число непересекающихся областей, которые называются гранями графа. Среди них есть единственная неограниченная грань, которую называют внешней, а остальные грани – внутренними.

Граница любой грани является объединением ребер графа. Если ребро не является мостом, то оно лежит на границе двух гра-

7

ней и его удаление уменьшает число граней на единицу. Мост лежит на границе единственной грани.

Если связный плоский (n, m) – граф имеет p граней, то справедлива формула Эйлера

n − m + p = 2 .

Если он не является деревом, то граница любой его грани содержит простой цикл. Дерево имеет только внешнюю грань и является ее границей.

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

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

Если исходные данные представлены списком длины N (например, список вершин и ребер графа), то число N называют размером задачи. Обозначим через F (N) максимальное число операций, выполняемых алгоритмом при решении задачи размера N. Если эта функция возрастает не быстрее, чем некоторая степень NK, то алгоритм называют полиномиальным. При K ≤ 4 алгоритмы достаточно эффективны в практических задачах.

Если же функция F (N) растет как некоторая экспонента, то алгоритм называют экспоненциальным, а соответствующую задачу

– труднорешаемой. В этом случае оптимальное решение можно найти лишь для задач небольшого размера.

8

Граф называется взвешенным, если каждому ребру приписан вес, т.е. некоторое число. В разных задачах вес может интерпретироваться как расстояние, стоимость, пропускная способность и т.д. Суммарный вес ребер некоторого подграфа во взвешенном графе называется весом этого подграфа.

Рассмотрим задачу о минимальном остове. Она состоит в построении остова минимального веса в связном взвешенном графе с n вершинами. Для решения этой задачи применяют следующий алгоритм Прима.

Находим в данном графе ребро Е1 минимального веса и обозначаем через А1 подграф, состоящий из этого ребра. Пусть уже построен подграф АК порядка k < n-1. Среди всех ребер, соединяющих его вершины с остальными вершинами графа, находим ребро EK+1 наименьшего веса. Обозначим через AK+1 подграф, полученный добавлением к AK ребра EK+1. Заметим, что на каждом шаге этого построения подграф AK является деревом. При этом подграф An-1 есть остов минимального веса в данном графе.

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

Пусть имеется граф с n вершинами. Рассмотрим все его подграфы третьего порядка. Их общее количество равно

n(n −1)(n − 2)6 ,

т.е. равно числу сочетаний из n по 3.

Среди них различными (неизоморфными) являются лишь четыре подграфа: цикл, цепь, ребро и вершина, три попарно несмежные вершины (рис. 6).

9

1

2

3

4

Рис. 6.

Отношение числа каждого из этих подграфов к общему их числу равно вероятностям встречи подграфов каждого вида в данном графе. Обозначим эти вероятности соответственно через P1 , P2 , P3 , P4 и найдем нормированную энтропию полученного вероятностного распределения:

H = −[P1 L ( P1 ) + ... + P4 L ( P4 )]2 ,

где символом L обозначены логарифмы с основанием 2.

Из определения энтропии следует, что она принимает значения на отрезке от нуля до единицы. При этом Н = 1 лишь для равномерного распределения, у которого все вероятности равны ¼.

Нулевой энтропией обладает распределение, у которого одна из вероятностей равна единице. В частности, нулевую энтропию имеют полный и пустой графы. У первого Р1 = 1, поскольку любые три вершины образуют цикл, а у второго Р4 = 1, так как любые три вершины попарно несмежны.

Найдем, например, энтропию графа и его остова, приведенных на рис. 7.

Рис. 7.