В городе Кёнигсберг (ныне Калининград) бытовала загадка: как пройти по всем семи мостам города, так, чтобы побывать на каждом мосту ровно один раз. В 1736 году эту загадку решил Леонард Эйлер, представив широкой общественности критерий существования в графе эйлерова (теперь его так называют) цикла.
Определение 7. Эйлеров путь в графе - такой путь, который проходит через все ребра ровно по одному разу.
Определение 8. Цикл в графе - это такой конечный путь, в котором начальная и конечная вершины совпадают.
Определение 9. Эйлеров цикл - это эйлеров путь, являющийся при этом циклом. Граф, в котором есть такой цикл, называют эйлеровым.
Теорема 2. Связный граф является эйлеровым тогда и только тогда, когда все степени его вершин - четные числа.
Доказательство. В действительности, если эйлеров цикл входит в вершину по одному ребру, то он должен выйти из нее по другому. Таким образом условие четности очевидно. Покажем теперь, что в связном графе с четными степенями вершин такой цикл существует.
Начнем путь P в произвольной вершине a графа G и будем продолжать его по все новым и новым ребрам. Так как все степени четные, этот процесс закончится в a. Если полученный цикл P не является эйлеровым, удалим из графа G все ребра, через которые проходит P. Понятно, что в оставшемся подграфе все степени останутся четными и найдется хотя бы одна вершина b, инцидентная какому-либо ребру из P. Тогда мы можем построить из нее подобный P цикл P' и проделать для нее вновь все те же самые операции.
Переобозначим: P=P(a, b) + P' + P(b, a), где P(k, l) - часть цикла P, соединяющая k и l.
Легко видеть, что рано или поздно ребра в графе кончатся и тогда цикл P станет эйлеровым.
 |
| Упрощенная схема мостов Кенигсберга. |
Определение 8. Цикл в графе - это такой конечный путь, в котором начальная и конечная вершины совпадают.
Определение 9. Эйлеров цикл - это эйлеров путь, являющийся при этом циклом. Граф, в котором есть такой цикл, называют эйлеровым.
Теорема 2. Связный граф является эйлеровым тогда и только тогда, когда все степени его вершин - четные числа.
Доказательство. В действительности, если эйлеров цикл входит в вершину по одному ребру, то он должен выйти из нее по другому. Таким образом условие четности очевидно. Покажем теперь, что в связном графе с четными степенями вершин такой цикл существует.
Начнем путь P в произвольной вершине a графа G и будем продолжать его по все новым и новым ребрам. Так как все степени четные, этот процесс закончится в a. Если полученный цикл P не является эйлеровым, удалим из графа G все ребра, через которые проходит P. Понятно, что в оставшемся подграфе все степени останутся четными и найдется хотя бы одна вершина b, инцидентная какому-либо ребру из P. Тогда мы можем построить из нее подобный P цикл P' и проделать для нее вновь все те же самые операции.
Переобозначим: P=P(a, b) + P' + P(b, a), где P(k, l) - часть цикла P, соединяющая k и l.
Легко видеть, что рано или поздно ребра в графе кончатся и тогда цикл P станет эйлеровым.
Комментариев нет:
Отправить комментарий