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

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

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

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

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

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

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

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

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

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

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

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
Подписываемся на обновления!  
 vk ok g

Главная   |   Обратная связь   |   Карта сайта   |   Заказать работу     |   Поддержи сайт 

infotables.ru © 2014 - 2017. Копирование материала с сайта возможно только при наличие активной индексируемой ссылки на infotables.ru

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

 вконтакте   однокласники   google plus