Файл: Учебника по курсу Основы дискретной математики и логики.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.10.2023
Просмотров: 211
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
5.
1 2 3 4 5 6 7 8 9
G[жэ] – связный граф без простых циклов.
На основе вышесказанного можно сделать вывод, что в любом дереве всегда есть по крайней мере две висячие вершины. Например, у дерева, изображенного на рис. 3.40, а, таких вершин в точности две. Дерево на рис.
3.40, е имеет пять висячих вершин.
Cлайд 88
Вершины в графе часто называют узлами. Этот термин мы будем использовать далее при рассмотрении ориентированных деревьев.
Ориентированным деревом, или ордеревом, называется орграф, удовлетворяющий следующим условиям:
1) существует единственный узел, полустепень захода которого равна 0; он называется корнем ордерева;
2) полустепень захода всех остальных узлов равна 1;
3) каждый узел достижим из корня.
На рис. 3.41 приведены диаграммы всех различных ориентированных деревьев с 3 узлами, а на рис. 3.42 – диаграммы всевозможных ордеревьев с 4 узлами.
Всякое ордерево G[жэ] обладает следующими свойствами:
1) число ребер в G[жэ] на единицу меньше числа вершин;
2) если в G[жэ] отменить ориентацию ребер, то получится свободное дерево;
3)
G[жэ] не содержит контуров;
4) для каждого узла существует единственный путь, ведущий в этот узел из корня;
5) подграф, определяемый множеством узлов, достижимых из узла v[вэ], является ордеревом с корнем v[вэ], называемым поддеревом узла v[вэ].
Если в свободном дереве любую вершину назначить корнем, то получится ордерево, при этом дуги будут последовательно ориентированы от корня.
Слайд 89
Листом ордерева называется вершина с нулевой полустепенью исхода.
Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется его высотой. Уровень узла ордерева – это расстояние от корня до узла. Сам корень имеет нулевой уровень. Узлы одного уровня образуют ярус дерева.
У дерева, изображенного на рис. 3.43, высота равна двум. Корнем дерева является вершина 1, листьями – вершины 4, 5, 6, 7. Формула (3.47) представляет все узлы первого уровня, формула (3.48) – узлы второго уровня.
Данное дерево имеет четыре ветви, представляемые формулой (3.49).
Наряду с растительной, применяется еще и генеалогическая терминология. Узлы, достижимые из узла u[у], называются потомками узла
u[у]. Потомки образуют поддерево в исходном дереве. Если в дереве существует дуга (u, v)[у вэ], то узел u[у] называется отцом, или родителем, узла v[вэ], а узел v[вэ] – сыном узла u[у]. Сыновья одного узла называются братьями.
Слайд 90
Пусть G[жэ] – связный неориентированный граф. Остовным деревом, или остовом, графа G[жэ] называется его ациклический связный подграф, содержащий все вершины G[жэ]. Другими словами, остовное дерево графа состоит из минимального подмножества ребер графа, таких, что из одной из вершин графа можно попасть в любую другую вершину, двигаясь по этим ребрам.
В качестве примера рассмотрим граф G[жэ], изображенный на рис.
3.44. Он имеет три остова, которые представлены на рис. 3.45.
Количество ребер остовного дерева графа на единицу меньше числа вершин графа.
Число остовов полного графа с n[эн] вершинами можно вычислить по формуле (3.50).
Количество остовных деревьев в полном двудольном графе с m[эм] и n[эн] вершинами в долях выражается формулой (3.51).
Слайд 91
Рассмотрим полный граф с тремя вершинами, изображенный на рис.
3.46. Он имеет три разных остовных дерева, представленных на рис. 3.47.
На рис. 3.48 изображен полный двудольный граф с двумя вершинами в каждой доле. Число его различных остовных деревьев равно четырем.
Указанные деревья представлены на рис. 3.49.
Число остовных деревьев полного графа быстро растет с увеличением количества его вершин. Так, полный граф с четырьмя вершинами имеет 16 остовных деревьев, у графа с пятью вершинами их уже 125, при добавлении шестой вершины число остовных деревьев увеличивается до 1296[одной тысячи двухсот девяноста шести].
Аналогично с увеличением количества вершин в долях быстро растет число остовных деревьев полного двудольного графа. У графа, имеющего по три вершины в каждой доле, их 81. Если в одной доле графа три вершины, а в другой четыре, то число остовных деревьев возрастает до 432[четырехсот тридцати двух]. У графа, имеющего три вершины в первой доле и пять во второй, число остовных деревьев равно 2025[двум тысячам двадцати пяти].
Слайд 92
Неориентированный граф G[жэ] без петель и кратных ребер называется планарным, если его можно изобразить на плоскости так, что никакие два ребра не пересекаются в точках, отличных от вершин. Такое изображение графа на плоскости называется плоским. Таким образом, если граф имеет плоское изображение, то он является планарным.
Граф K
4
[ка четыре], представленный на рис. 3.50, а, планарен, поскольку может быть изображен, как показано на рис. 3.50, б.
Не всякий граф является планарным. Справедливо следующее утверждение.
Если граф G[жэ] планарен, то он не содержит подграфа, изоморфного полному графу K
5
[ка пять] или полному двудольному графу K
3,3
[ка три три].
Указанные графы изображены на рис. 3.51.
Из последнего утверждения вытекает, что графы K
5
[ка пять] иK
3,3
[ка три три] не являются планарными.
Любой конечный граф может быть изображен в трехмерном пространстве без пересечения ребер вне их концов.
Для всякого связного планарного графа G[жэ] справедлива теорема
Эйлера, представленная формулой (3.52). Здесь p[пэ] − число вершин графа
G[жэ], q[кю] − число ребер, r[эр] − число областей, на которые разбивается плоскость плоским изображением графа G[жэ]. Следствия этой теоремы приведены в формулах (3.53) и (3.54).
Слайд 93
Проиллюстрируем теорему Эйлера и ее следствия на графе G[жэ], изображенном на рис. 3.52. Прежде всего построим его плоское изображение.
Оно приведено на рис. 3.53. В нашем случае граф имеет пять вершин и восемь ребер. Число областей, на которые разбивается плоскость плоским изображением графа, равно пяти. Как и утверждается в теореме Эйлера, вычитая из суммы числа вершин и числа указанных областей количество ребер графа G[жэ], получаем число два. Соответствующее равенство представлено формулой (3.55).
Поскольку число вершин графа больше трех, в силу первого следствия теоремы сумма числа ребер и шести не должна превосходить утроенного количества вершин. Требуемое соотношение, выражаемое формулой (3.56), очевидно, выполняется.
Наконец, степени всех вершин графа G[жэ] не превосходят пяти, что подтверждает справедливость второго следствия теоремы Эйлера.
Слайд 94
Рассмотрим классическую задачу, известную как задача о семи кёнигсбергских мостах. С постановки этой задачи начала свое развитие теория графов. Имеются два острова, соединенных семью мостами с берегами реки и друг с другом, как показано на рис. 3.54. Нужно осуществить прогулку по городу таким образом, чтобы, пройдя по каждому мосту один раз, вернуться обратно. Данная задача была поставлена философом Иммануилом Кантом в 1736 году, во время его прогулки по городу Кёнигсбергу.
Решение этой задачи сводится к нахождению некоторого специального маршрута на графе. Поставим в соответствие плану расположения участков суши и мостов, приведенному на рис. 3.54,мультиграф, вершины которого обозначаютчасти суши, а ребра – соединяющие их мосты. Указанный граф изображен на рис. 3.55. Теперь задача звучит следующим образом: найти цикл, содержащий все ребра графа. Эта задача была решена Леонардом
Эйлером, петербургским математиком швейцарского происхождения.
Слайд 95
Пусть G[жэ] – неориентированный граф.
Если G[жэ] имеет цикл, содержащий все ребра графа, то такой цикл называется эйлеровым циклом, а граф G[жэ] – эйлеровым графом. Если G имеет цепь, содержащую все вершины графа по одному разу, то такая цепь называется эйлеровой цепью, а граф G[жэ] – полуэйлеровым графом.
Граф G, изображенный на рис. 3.56, является эйлеровым. Он имеет эйлеров цикл, представленный формулой (3.57).
Граф D на рис. 3.57 является полуэйлеровым. Входящая в него эйлерова цепь представлена формулой (3.58).
Для всякого связного нетривиального графа G[жэ] следующие утверждения эквивалентны.
1. G[жэ] – эйлеров граф.
2. Каждая вершина G[жэ] имеет четную степень.
3. Множество ребер графа G[жэ] можно разбить на простые циклы.
Заметим, что в задаче о кёнигсбергских мостах все вершины графа имеют нечетные степени. Поэтому данная задача решения не имеет.
Граф F[эф], изображенный на рис. 3.58, не является эйлеровым, например, потому, что степень его вершины 4 равна трем. В то же время он принадлежит классу полуэйлеровых графов, поскольку содержит эйлерову цепь, задаваемую формулой (3.59).
Если граф без петель содержит 2k[два ка] вершин нечетной степени, то его можно разбить на k[ка] полуэйлеровых графов, то есть нарисовать k[ка] росчерками пера.
Задачи с эйлеровыми графами часто встречаются в книгах по занимательной математике – например, можно ли нарисовать какую-нибудь диаграмму, не отрывая карандаша от бумаги и не проходя никакую линию дважды. Принято всякую замкнутую линию, если ее можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, называть уникурсальной. Рисунок графа, обладающего эйлеровым путем или эйлеровым циклом, является уникурсальной линией.
Слайд 96
Напомним, что эйлеров цикл в связном нетривиальном графе существует тогда и только тогда, когда все его вершины имеют четные степени.
На этой теореме основан алгоритм построения эйлерова цикла.
Сначала нужно убедиться, что граф эйлеров, и построить любой цикл.
После такого построения возникают две возможности: а) в цикл входят все ребра графа; б) на графе остались неучтенные ребра.
В случае «а» задача решена. В случае «б» в построенном цикле нужно найти вершину, из которой выходит еще не пройденное ребро, и
сформировать цикл из не задействованных ранее ребер. Затем надо объединить два имеющихся цикла в один и вновь проверить, все ли ребра пройдены. И так далее. Процедура объединения двух циклов в один продемонстрирована на рис. 3.59.
Алгоритм заканчивает свою работу, когда будут задействованы все ребра графа.
Рассмотрим некоторые приложения теоремы Эйлера, которые в основном связаны с так называемой задачей китайского почтальона.
Пусть имеется связный граф, ребрам которого соответствуют некоторые числа, называемые весами. Требуется найти такой цикл, при котором каждое ребро проходится по крайней мере один раз и суммарный вес всех ребер, вошедших в цикл, минимален. Заметим, что если граф эйлеров, то искомым циклом является содержащийся в графе эйлеров цикл.
Эта задача имеет много приложений, одним из которых является поливка улиц одной машиной. Здесь ребра графа – дороги, вершины – перекрестки, веса – длины дорог. Подобная задача возникает при сборе мусора, доставке почты, выборе наилучшего маршрута для осмотра музея, уборке помещений и коридоров в больших учреждениях.
Слайд 97
Кратко остановимся на проблеме, связанной с возможностью обхода всех вершин в графе. Задача ставится следующим образом: выяснить, существует ли в данном графе простой цикл, проходящий через каждую вершину графа.
Рассмотрим неориентированный граф G[жэ].
Если G[жэ] имеет простой цикл, содержащий все вершины графа, то такой цикл называется гамильтоновым циклом, а граф G[жэ] – гамильтоновым графом.
Граф G[жэ] на рис. 3.60 является гамильтоновым. Он имеет гамильтонов цикл, представленный формулой (3.60).
Алгоритм заканчивает свою работу, когда будут задействованы все ребра графа.
Рассмотрим некоторые приложения теоремы Эйлера, которые в основном связаны с так называемой задачей китайского почтальона.
Пусть имеется связный граф, ребрам которого соответствуют некоторые числа, называемые весами. Требуется найти такой цикл, при котором каждое ребро проходится по крайней мере один раз и суммарный вес всех ребер, вошедших в цикл, минимален. Заметим, что если граф эйлеров, то искомым циклом является содержащийся в графе эйлеров цикл.
Эта задача имеет много приложений, одним из которых является поливка улиц одной машиной. Здесь ребра графа – дороги, вершины – перекрестки, веса – длины дорог. Подобная задача возникает при сборе мусора, доставке почты, выборе наилучшего маршрута для осмотра музея, уборке помещений и коридоров в больших учреждениях.
Слайд 97
Кратко остановимся на проблеме, связанной с возможностью обхода всех вершин в графе. Задача ставится следующим образом: выяснить, существует ли в данном графе простой цикл, проходящий через каждую вершину графа.
Рассмотрим неориентированный граф G[жэ].
Если G[жэ] имеет простой цикл, содержащий все вершины графа, то такой цикл называется гамильтоновым циклом, а граф G[жэ] – гамильтоновым графом.
Граф G[жэ] на рис. 3.60 является гамильтоновым. Он имеет гамильтонов цикл, представленный формулой (3.60).
Гамильтонов цикл не всегда содержит все ребра графа. Рассмотрим граф F[эф], изображенный на рис. 3.61. Его гамильтонов цикл, задаваемый формулой (3.61), содержит только 5 из 8 ребер графа.
Граф, являющийся гамильтоновым, обязательно связен.
Слайд 98
Несмотря на сходство постановки задач для гамильтоновых и эйлеровых графов, «хорошего» решения для гамильтоновых графов нет.
Вообще, о гамильтоновых графах известно очень мало. В основном это теоремы типа «Если в графе достаточное число ребер, то он гамильтонов».
Ясно, что подобные теоремы не могут служить критерием для проверки того, является ли граф гамильтоновым. Ведь в графах такого типа вершин может быть очень много, а ребер сравнительно мало.
Имеет место следующее утверждение, называемое теоремой Дирака.
Если в графе G[жэ], содержащем n[эн] вершин, степень любой вершины больше n/2[эн пополам], то граф G[жэ] является гамильтоновым.
Применим данную теорему к графу D[дэ], изображенному на рис. 3.62.
Этот граф имеет четыре вершины, причем степень каждой вершины больше двух. Следовательно, граф D[дэ] является гамильтоновым.
К графу F[эф], изображенному на рис. 3.63, указанная теорема не применима. Тем не менее он также является гамильтоновым.
Гамильтоновы путь, цикл и граф названы в честь ирландского математика Уи́льяма Га́мильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как
Брюссель, Амстердам, Эдинбург, Пекин, Прагу, Дели, Франкфурт и другие, а ребра – соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз.
Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже