Регулярный граф. Гамильтонов граф

Регулярный граф

Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k. Таким образом, на рисунке к примеру 2 изображены примеры регулярных графов, называемых по степени его вершин 4-регулярными и 2-регулярными графами или регулярными графами 4-й степени и 2-й степени.

Число вершин регулярного графа k-й степени не может быть меньше k+1. У регулярного графа нечётной степени может быть лишь чётное число вершин.

Пример 3.Построить регулярный граф, в котором самый короткий цикл имеет длину 4.

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

Увеличиваем число вершин до восьми (следующее число, кратное четырём). Соединяем вершины рёбрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи.

Нет времени вникать в решение? Можно заказать работу!

Гамильтонов граф

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

Пример 4.Задан двудольный граф, в котором n - число вершин из множества A, а m - число вершин из множества B. В каком случае граф будет эйлеровым графом, а в каком случае - гамильтоновым графом?

Ответ. Если n и n - чётные, то граф будет эйлеровым. Если n = n, то граф будет гамильтоновым.

⇐ Предыдущая 1 234 Следующая ⇒