Маршруты, цепи и циклы

9472
0
08 июля 2009
(38.2.) В рамках обозначенной темы рассмотрим случай определения связного неориентированного мультиграфа в качестве эйлерова и гамильтонова графа.

Предположим, что38.2_html_7a623d36.gifявляется неориентированным графом.

О: В качестве маршрута графа38.2_html_m6c10f406.gif

38.2_html_m4b42ecde.gifопределяют такую очередность ребер38.2_html_649605ba.gif, что для двух соседних ребер характерна общая инцидентная вершина, 38.2_html_m5529cae6.gifесть начальная,38.2_html_14879232.gif- конечная вершины. Под длиной маршрута понимают количество ребер маршрута.

О: Маршрут38.2_html_36b4ecae.gifименуют цепью в случае, когда все его ребра различны. Простой цепью маршрут38.2_html_36b4ecae.gifможно назвать, если все его вершины, за исключением первой и последней, различны.

Так, для графа, изображенного на рис. 38.4 обозначим:38.2_html_7ed426bd.gif- маршрут, а не цепь,38.2_html_5e55e177.gifпредставляет собой непростую цепь,38.2_html_5f75d148.gifявляется простой цепью.

О: Цепь, которая предполагает совпадение начальной и конечной вершин, имеет название цикла, в случае, когда цепь простая, — простого цикла.

38.2_html_53a30178.gif
Рис. 38. 4

38.2_html_651465c.gif
  38.2_html_5cae673f.gif
Рис. 38. 5

 

На рис. 38.4:38.2_html_m4add1da1.gif- непростой цикл,38.2_html_m25cb8bc0.gif- простой цикл.

В частности, всякая петля представляет собой цикл.

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

На рис. 38.4, 38.5 изображены связной и несвязной графы, соответственно.

Составление теории графов связывают с постановкой и решением задачи о Кенигсбергских мостах Эйлером.

Задача. На рис. 38.6. обозначено расположение мостов. Необходимо пройти каждый мост единожды и вернуться в начальную часть города (суши).

38.2_html_m13523d19.gif
Рис. 38. 6

38.2_html_5e1726ca.gif
Рис. 38. 7

 

Изобразим участок суши в виде точек38.2_html_5f1d9adf.gifи представим граф задачи (рис. 38.7). Для обхода мостов характерно соответствие последовательности ребер графа, при этом два соседних ребра соединены общей вершиной, т.е. имеют общий маршрут. Поскольку по окончании обхода необходимо возвратиться в исходную часть города и на каждом мосту находиться единожды, то такой маршрут можно назвать циклом, который включает в себя все ребра графа. Решение задачи предполагает формулировку ответа на вопрос, имеется ли в данном случае такой цикл?

О: Связный неориентированный мультиграф именуют эйлеровым при условии, что имеется цикл, который включает в себя все ребра графа (так называемый эйлеров цикл).

Эйлеров граф или цикл определяют в качестве следа пера, вычеркивающего данный граф, который не отрывается от бумаги.

Т: Неориентированный связанный мультиграф38.2_html_7a623d36.gifявляется эйлеровым только в случае четности степени его вершин.

В соответствии с теоремой заключим, что для задачи о Кенигсбергских мостах не существует решения в силу того, что для всех вершин характерна нечетная степень. На рис. 38.8. обозначен Эйлеров граф.

38.2_html_2e510e59.gif
Рис. 38. 8

 

38.2_html_5e9d5a21.gif
Рис. 38. 9

 

О: Связной неориентированный граф38.2_html_7a623d36.gifименуют гамильтоновым в случае, когда имеется простой цикл, который проходит через все вершины графа (так называемый гамильтонов цикл).

На рис. 38.9 представлен гамильтонов цикл.

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



(38.4.) Сформулируем понятие конечного автомата, обозначим входной алфавит, выходной алфавит, алфавит состояний, функцию переходов, функцию выходов, на рисунке изобразим граф переходов.
2622 0
(38.3.) Большинство графов, которые используются в приложениях (например, графы сортировок, классификаций) предполагают наличие диаграмм, именуемых деревьями. Связный неориентированный граф без циклов, в частности, предполагающий отсутствие петель и кратных ребер, именуют деревом. Несвязный неориентированный граф без цикла — лес, его связные компоненты являются деревьями.
7594 0
(38.1.) Одним из базовых разделов дискретной математики можно назвать теорию графов. Их применяют при решении задач теории автоматического управления. Применение их актуально и в таких науках, где существуют системы с большим количеством объектов, которые предполагают взаимосвязь, определяемую разнообразными отношениями.
5171 0

    Вы должны авторизоваться, чтобы оставлять комментарии.

    При использовании материалов данного сайта прямая и явная ссылка на сайт radiomaster.ru обязательна. 0.2701 s