Читайте также:
|
Рассмотрим задачу Эйлера "О ходе шахматного коня". Требуется шахматным конем обойти вся поля доски и вернуться в исходное поле, при этом ни разу не бывая в одном поле более одного раза.
Если поля шахматной доски принять за вершины графа G8 ´ 8 , ребрами считать возможность коня согласно шахматным правилам перемещаться с поля u на поле v ({ u, v } Î G8 ´ 8 , если конь может пойти с поля u на поле v), то это задача о гамильтоновом цикле. Задача Эйлера имеет хорошо известные многочисленные исследования и решения. Попробуем решить эту задачу для шахматной доски 5 ´ 7. Ей соответствует граф G5 ´ 7 . Заметим, что согласно шахматным правилам конь не может пойти с некоторой клетки на другую клетку того же цвета, т.е. рассматриваемый граф является двудольным. Так как граф G5 ´ 7 содержит 35 вершин, то он не является гамильтоновым, так как нарушаются необходимые условия существования гамильтонова цикла в двудольном графе. В то же время гамильтонова цепь в таком графе может существовать, так |17 – 18| = 1.
2.5. Планарные графы
O Плоские графы
O Формула Эйлера
O Критерий планарности Понтрягина-Куратовского
Плоские графы
Граф G называется плоским, если он изображен на плоскости без пересечения ребер (кроме соединения ребер в вершинах).
Говорят, что граф Gизоморфно укладывается на плоскость, если он изоморфен плоскому графу.
Граф G называется планарным, если он изоморфно укладывается на плоскость.
Гранью плоского графа G называется часть плоскости, не содержащая вершин и ребер, ограниченная простым циклом. Конечная грань графа называется внутренней, а бесконечная – внешней.
Замечание. Если у графа, содержащего простой цикл, удалить одно ребро из этого цикла, то количество внутренних граней этого графа уменьшится на единицу.
Дата добавления: 2015-07-20; просмотров: 47 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Пример 2.10 | | | Пример 2.13 |