<<
>>

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

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

Теорема. Для того, чтобы связный псевдограф G обладал эйлеровым циклом, необходимо и достаточно, чтобы степени его вершин были четными.

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

Определение. Цикл (цепь) в псевдографе G называется гамильтоновым, если он проходит через каждую вершину псевдографа G ровно один раз.

Пример.

– в графе есть и эйлеровый и гамильтонов циклы

– в графе есть эйлеров цикл, но нет гамильтонова

– в графе есть гамильтонов, но нет эйлерова цикла

– в графе нет ни эйлерова, ни гамильтонова цикла

Граф G называется полным, если если каждая его вершина смежна со всеми остальными вершинами. В полном графе всегда существуют гамильтоновы цмклы.

Также необходимым условием существования гамильтонова цикла явояется связность графа.

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

Еще по теме Эйлеровы и гамильтоновы графы.:

  1. ряд примеров приложений теории графов.
  2. Содержание дисциплины
  3. ПЕРЕЧНЬ ТЕМ ДЛЯ САМОСТОЯТЕЛЬНОГО ИЗУЧЕНИЯ
  4. Эйлеровы и гамильтоновы графы.
  5. Перечень вопросов к экзамену на первом курсе
  6. 4.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
  7. §5. Графы