Основные виды графов

Определение 19: Цикл называется эйлеровым, если он содержит все ребра графа и является простым.

Определение 20: Граф называется эйлеровым если он содержит эйлеров цикл.

Определение 21: Цикл называется гамильтоновым, если он содержит все вершины графа и является элементарным.

Определение 22: Граф называется гамильтоновым если он содержит гамильтонов цикл.

Теорема 1: Если граф Эйлеров, то все его вершины – четные.

Доказательство. Пусть - эйлеров цикл и . Началом и концом цикла можно считать некоторую вершину . Направление обхода цикла можно выбрать произвольно. Пусть при обходе цикла первый раз мы входим в вершину по некото-рому ребру и выходим по ребру . Если других ребер, инцидентных , нет, то степень вершины равна 2 и теорема доказана. Иначе, убираем ребра , и замечаем, что цикл повторно входит в вершину по некоторому ребру и выходит по ребру , так, что либо и теорема доказана, либо рассуждение можно продолжить. В результате будут исчерпаны все инцидентные ребра, что и завершает доказательство.

Рис 1. Эйлеровы и гамильтоновы графы.

Эйлеров и Гамильтонов но не

гамильтонов эйлеров

Эйлеров (эйлеров цикл

),

но не гамильтонов.

Приведем доказательство негамильтоновости графа .

Вершину назовем изолированной элементарным циклом , если он содержит цепь , включающую все смежные с ней вершины, и не включающую саму вершину.

Заметим, что у гамильтонова цикла нет изолированных вершин.

Пусть существует гамильтонов цикл . Возможны следующие случаи:

1). . Тогда - изолированная вершина.

2). . Тогда - изолированная вершина.

3). . Тогда и - изолированные вершины.

Следовательно, цикл не гамильтонов, и граф также негамильтонов.

Дата добавления: 2014-01-05