Условие
Докажите, что связный граф, имеющий не более двух нечётных вершин, можно нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро ровно один раз.
Решение
Разберём случай, когда граф не имеет нечётных вершин. Индукцией по числу рёбер графа докажем, что его можно обойти по циклу. База (граф без рёбер) очевидна.
Шаг индукции. Рассмотрим произвольный связный граф, степени всех вершин которого чётны. Поскольку в этом графе нет висячих вершин, то он не является деревом, и, следовательно, в нём есть простой цикл. Временно удалим из графа рёбра этого цикла. При этом граф распадётся на несколько компонент связности, имеющих общие вершины с выкинутым циклом. В каждой компоненте все вершины чётны, и по предположению индукции каждую из этих компонент связности можно обойти по циклу. Теперь ясно как обойти требуемым образом исходный граф: обходим цикл и попадая в вершину, относящуюся к какой-то компоненте, обходим её, в конце возвращаясь в ту же вершину, после чего продолжаем движение по циклу.
Доказательство для случая графа с двумя нечётными вершинами аналогично (нужно временно удалить путь, соединяющий две нечётные вершины).
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
Генкин С.А., Итенберг И.В., Фомин Д.В. |
|
Год издания |
1994 |
|
Название |
Ленинградские математические кружки |
|
Издательство |
Киров: "АСА" |
|
Издание |
1 |
|
глава |
|
Номер |
13 |
|
Название |
Графы-2 |
|
Тема |
Теория графов |
|
задача |
|
Номер |
028 |
