Основные типы графов и их примеры (Таблица)

Типы графов (определение)

Условия существования

Иллюстрирующие примеры

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

Граф, обладающий эйлеровым циклом (путем), называется эйлеровым 

Путь (цикл), содержащий все вершины графа по одному разу, называется гамильтоновым.

Граф, обладающий гамильтоновым циклом (путем), называется гамильтоновым

Критерий существования эйлерова цикла: степени всех графа четные

Критерий существования эейлерова пути: граф имеет ровно две вершины нечетной степени 

Достаточные условия существования:

1.   Всякий полный граф является гамильтоновым.

2.   Если граф, помимо простого цикла, содержит и другие ребра, то он также является гамильтоновым.

3.   Если граф имеет гамильнов цикл, то он может иметь и другие гамильтоновы циклы

 

mat 12 45

Есть эйлеров и гамильтонов цикл.

mat 12 46

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

mat 12 47

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

mat 12 48

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

 



1 1 1 1 1 1 1 1 1 1 Рейтинг 5.00 [1 Голос]

Поделитесь ссылкой с друзьями:


Подписываемся !!!

Комментарии:

comments powered by HyperComments

библиотеки Яндекс.Метрика