Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Признаки уникурсалъных графов

Очевидно, что связность графа является необходимым условием его уникурсальности. К сожалению, для изображения графа одним росчерком одной его связности недостаточно. Для того чтобы найти признаки уникурсальности связных графов, понаблюдаем за свойствами эйлеровых линий. Если подсчитать степени всех вершин графов, полученных одним росчерком (см. рис. 44-46), то можно заметить, что все эйлеровы циклы имеют только четные вершины (см. рис. 45 и 46), а все эйлеровы цепи (см. рис. 44), имеют ровно две нечетные вершины, а все их остальные вершины - четны. Этот экспериментальный результат может быть строго доказан.

Лемма. Если связный граф имеет более двух нечетных вершин, то он не уникурсален.

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

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

Доказательство. Применим метод математической индукции по количеству ребер графа.

  • 1) База индукции очевидна, так как связный граф с одним ребром, не имеющий нечетных вершин, является петлей и эйлеровым циклом (см. рис.
  • 47). Рис- 47
  • 2) Для доказательства индуктивного перехода предположим, что связный граф, имеющий только четные вершины и содержащий п<к ребер, является эйлеровым циклом.

Рассмотрим связный граф G, имеющий только четные вершины и содержащий п=к+1 ребер. Так как граф связен, он не имеет изолированных вершин. Пусть Ао - некоторая вершина графа. Так как А0 - не изолированная вершина четной степени, то существует ребро еисходящее из А0, и мы можем по этому ребру перейти в некоторую вершину А /. Вершина Aj имеет четную степень, следовательно существует ребро е2, отличное от et и выходящее из А]. Переходя по ребру е2, мы попадем в вершину Aj, и так далее... После конечного числа таких переходов мы вновь вернемся в вершину Ао, т.е. пройдем некоторый цикл с вершиной Ао. Если пройденный цикл включает в себя все ребра графа, то он - искомый цикл. Предположим, что пройденный цикл не включает всех ребер графа. Удалим из исходного графа ребра выделенного цикла. В результате получим суграф, который имеет несколько компонент связности (возможно, всего одну) G, (/=/, 2, ... , г). При этом будут выполняться следующие свойства:

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

По предположению индукции каждая из частей G, является эйлеровым циклом, причем начало и конец пути могут находиться в любой из вершин (в частности ими могут быть точки примыкания к вершинам удаленного цикла). Итак, алгоритм построения у нику реального цикла можно сформулировать так: двигаясь из вершины Ао по выделенному циклу, попутно обрисовывать выделенные части Gj(см. схему на рис. 48).

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

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

Доказательство. Обозначим через А и В нечетные вершины графа G. Так как граф связен, то между этими вершинами существует простая цепь. Если эта цепь включает все ребра графа, то она является искомым уникурсальным путем. Предположим, что выделенная цепь не включает всех ребер графа. Удалим ребра выделенной цепи. В результате получим су граф, который имеет несколько компонент связности (возможно, всего одну) G, (/=/, 2, ... , г). При этом будут выполняться следующие свойства:

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

По теореме 6, каждая из частей G, является эйлеровым циклом, причем начало и конец. пути могут находиться в любой из вершин (в частности ими могут быть точки примыкания к вершинам удаленной цепи). Следовательно, алгоритм построения уникурсальной цепи можно сформулировать так: двигаясь из вершины А по выделенной цепи к вершине В попутно обрисовывать выделенные циклы G, (см. схему на рис. 49). Теорема доказана.

Доказанные теоремы объясняют, почему задача Эйлера о кенигсбергских мостах не имеет решения. Заметим, что если построить мост, соединяющий любые два участка суши, например, между В и С (см. рис. 42), то можно будет указать эйлерову цепь. Если к тому же построить мост между А и D, то появится и эйлеров цикл.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы