Учебник по дискретной математики. Д. Ушинского Дискретная математика
![]()
|
Связность в неориентированных графахОпределение. Неориентированный граф G связен, если существует хотя бы один маршрут в G между каждой парой вершин i и j. Определение. Подграфом графа G(V,E) называется граф, все вершины которого принадлежат V(G), а все ребра принадлежат E(G). Определение. Максимальный связный подграф графа G называется связной компонентой графа G. Замечание: Максимальный не в смысле количества ребер, а в смысле нерасширяемости. Например, на рисунке 19 изображен несвязный граф с тремя компонентами связности. ![]() Заметим, что каждая компонента связности неориентированного графа представляет собой неориентированный граф, а значит, для нее выполняется лемма о рукопожатиях. Связность ориентированных графовОпределение. Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным. Определение. Ориентированный граф сильно связен, если для каждой пары вершин i и j существует по крайней мере один путь из i в j и по крайней мере один путь из j в i. Определение. Максимальный сильно связный подграф орграфа называется сильно связной компонентой. ![]() На рисунках 20 – 222 изображены несвязный, связный, но не сильно и сильносвязный графы соответственно. Циклы Эйлеров циклОпределение. Эйлеров цикл — цикл, который проходит ровно один раз по каждому ребру (дуге) графа. Определение. Если граф имеет цикл, содержащий все ребра (дуги) графа по одному разу, то граф называется эйлеровым. Н ![]() Граф, изображенный на рисунке 23 является эйлеровым. Задача о Кенегсбергских мостах, рассмотренная выше предполагает нахождение эйлерова цикла в мультиграфе. Теорема. Связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда все вершины в нем имеют четную степень. Доказательство.
Пусть граф G содержит эйлеров цикл, значит, существует цикл, проходящий по всем ребрам графа ровно по одному разу. Будем идти по циклу, и считать степени вершин. Т.к. проходя через вершину каждый раз, прибавляем к её степени 2, то степени всех вершин четны.
Пусть все вершины графа имеют четную степень. Будем строить эйлеров цикл, начиная с некоторой вершины v0, при этом пройденные ребра будем удалять. Так как все вершины имеют четную степень, то, попав в какую-либо вершину, обязательно найдем ребро, по которому можно из неё выйти. Таким образом, обязательно вернемся в вершину v0, получив при этом некоторый цикл Р. Если при этом все ребра графа участвуют в цикле, то теорема доказана. В противном случае, так как граф связен, обязательно найдется ребро не входящее в цикл, но инцидентное какой-либо вершине цикла. Обозначим эту вершину v1. Будем строить цикл начиная с вершины v1. Из аналогичных соображений мы обязательно вернемся в вершину v1, получив цикл Р1. Если при этом все ребра графа присутствуют в циклах Р и Р1, то цикл v1Рv1Р1v1 содержит все ребра графа по одному разу, то есть является эйлеровым, следовательно, теорема доказана. В противном случае продолжаем аналогичные рассуждения. Так как ребер в графе конечное количество построение цикла обязательно закончится. Теорема. Связный орграф является эйлеровым тогда и только тогда, когда полустепень исхода каждой вершины равна полустепени ее захода. Доказательство аналогично случаю неориентированного графа. Гамильтонов циклОпределение. Граф называется гамильтоновым, если в нем имеется цикл, содержащий каждую вершину этого графа. Уильям Роуэн Гамильтон выпустил головоломку, суть которой состояла в построении пути, который через каждую вершину проходит по одному разу. Задача похожа на задачу о нахождении эйлеровой линии, однако до сих пор не найдены необходимые и достаточные условия существования в графе гамильтоновых линий. Похожа на данную и задача о коммивояжере, которая тоже состоит в построении цикла, проходящего по всем городам по одному разу, но при этом требуется минимизировать транспортные расходы. Алгоритма решения данной задачи тоже не существует. Некоторые головоломки типа как перевезти волка, козу и капусту тоже сводятся к поиску гамильтоновой линии на некотором графе, изображающем все возможные перевозки. Известна также задача о нахождении пути коня на шахматной доске, при котором он побывает на каждом поле по одному разу (вариант – и вернется на исходное поле последним ходом), которая тоже является частным случаем задачи о нахождении гамильтоновой линии. Например, на рисунках 18 и 22 – изображены гамильтоновы графы, а на рисунках 21 и 23 графы, не являющиеся гамильтоновыми. |