| Типы графов (определение) | Условия существования | Иллюстрирующие примеры |
|---|---|---|
| Путь (цикл), содержащий все ребра графа и притом по одному разу, называется эйлеровым путем (циклом).
Граф, обладающий эйлеровым циклом (путем), называется эйлеровым Путь (цикл), содержащий все вершины графа по одному разу, называется гамильтоновым. Граф, обладающий гамильтоновым циклом (путем), называется гамильтоновым |
Критерий существования эйлерова цикла: степени всех графа четные
Критерий существования эейлерова пути: граф имеет ровно две вершины нечетной степени Достаточные условия существования: 1. Всякий полный граф является гамильтоновым. 2. Если граф, помимо простого цикла, содержит и другие ребра, то он также является гамильтоновым. 3. Если граф имеет гамильнов цикл, то он может иметь и другие гамильтоновы циклы |
Есть эйлеров и гамильтонов цикл. Есть эйлеров цикл, но нет гамильтонова цикла. Есть гамильтонов, но нет эйлерова цикла. Нет ни эйлерова, ни гамильтонова цикла |
