Учебник по дискретной математики. Д. Ушинского Дискретная математика
 Скачать 2.66 Mb.
|
Связность в неориентированных графахОпределение. Неориентированный граф 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 графы, не являющиеся гамильтоновыми. |