76. Гамильтоновы циклы.

Еще быстрее мы попадем к выходу из лабиринта (когда его граф G связен), двигаясь по гамильтонову циклу, т. е. по простому циклу, проходящему через все вершины рассматриваемого графа G. Однако не во вся­ком связном графе, содержащем циклы, существует га-мильтонов цикл. Более того, через любые две вершины рассматриваемого графа может проходить простой цикл (в этом случае граф G называется циклически связным), а га-мильтонов цикл при этом может отсутствовать.

На рис. изображены граф с гамильтоновым циклом (рис. а) и циклически связный граф, в котором нет гамильтонова цикла (рис. б). В последнем, чтобы пройти через вершины, расположенные внутри сторон тре­угольника АВС, гамильтонов цикл должен содержать все лежащие на этих сторонах ребра. Но тогда он не проходит через расположенную в центре треугольника вершину 0.

Иногда можно построить проходящую через все вер­шины графа простую цепь с началом и концом в различных заданных вершинах V', V" С. Такая цепь тоже называется гамильтоновой.

77. Некоторые классы графов и их частей. Дерево и лес.

Граф без циклов наз. ациклическим. Связный ацекличный граф наз. деревом. Граф каждая компонента связности к-го – дерево, наз. лес.

Теорема.

Для графа G следующие условия эквивалентны.

1. G – дерево;

2. В G любые две вершины связаны единственной простой цепью;

3. G – связный граф, имеющий n – вершин и (n-1) – ребро;

4. G – ациклический граф, имеющий n – вершин и (n-1) – ребро;

Доказательство.

Докажем, что 12341.

Пусть G дерево. Предположим, что  i,j: i,j связаны двумя цепями. Тогда в G  замкнутый маршрут, а из него можно выделить простой цикл, что противоречит ацикличности графа G.

Пусть выполнено 2. В этом случае в G  висячие вершины. Предположив обратное, получим, что степень каждой вершины 2. Войдя в вершину по некоторому ребру можно выйти из неё по другому, а это позволяет построить цикл графа G: i₁i₂i₃…i_k (каждый раз новое ребро), где K^~{1,2,…,k-1}, т.е. имеем противоречие. При удалении висячей вершины вместе с инцидентным ей ребром св-во 2 не нарушается. Число вершин и число рёбер уменьшились при этом на 1. Следовательно в новом графе  висячие вершины. Удалим их и т.д. В результате получим одновершинный граф. Следовательно, число рёбер в исх. графе меньше числа вершин на единицу. Связнось его очевидна.

Пусть выполнено 3. Покажем, что G – ациклический. В G  висячая вершина, т.к. в противном случае нарушается соотношение между числом врешин и числом рёбер. Удаление висячей вершины не влияет на связность и ацикличность. После (n-1) удаления мы получаем связный ациклич. граф. Поэтому исх. граф также ациклич.

41 (док-ть самостоятельно).

Для проверки на древесность достаточно проверить условие 3. Но можно реализовать проверку следующим образом:

Находим строку матрицы смежности, содержащей только одну единицу. Если такой строки нет, то G не дерево. Иначе вычёркиваем из матрицы строку и столбец соотв. этой единице и т.д. Если в результате получим одноэлем. Матрицу, то граф – дерево.

Пусть D – некоторый граф, причём связный. Остовный подграф этого графа, явл. деревом, наз. остовным деревом. Для связного графа всегда  остовное дерево.

Временная сложность проверки графа на древесность не хуже чем n³. Временная сложность выделения остовного дерева не хуже чем n³.