Элементарные задачи по топологии. Линии

[Someone]

caxap в сообщении #472434 писал(а):

имеем снова конечный связный граф с чётными индексами вершин

Не обязательно связный. Это, правда, не важно, но чуть-чуть об этом поговорить нужно.

[caxap]

Ой, извиняюсь. Действительно, может быть не связный. Тогда мы просто на время забываем про все остальные части.

А в остальном правильно?

Задача 24. Доказать, что граф уникурсален [можно пройти весь, пройдя по каждому ребру один раз] $\iff$ он содержит не более двух вершин нечётного индекса.

$\Leftarrow:$ Вершин нечётного индекса всегда чётное число. Если их ноль, то это прошлая задача. Пусть их две. Выходим из нечётной вершины, при этом мы "убираем" одно ребро и вершина становится чётной, поэтому у нас остаётся только одна нечётная вершина, в которой мы должны остановится. Пусть $a$ -- первая вершина, из которой выходит не пройденное ребро.

Стираем первый цикл. Если оставшийся граф несвязен, забудем про все части кроме той, в которой находится $a$. Мы имеем связный конечный граф с чётными вершинами, его можно пройти весь и вернуться снова в $a$ (предыдущая задача). Объединяем этот цикл с первым. И так далее, пока весь граф не пройдём.

$\Rightarrow:$ Пусть имеется "уникурсальный" обход графа. Все "проходные" вершины, не являющиеся началом и концом пути, должны иметь чётный индекс (входим и выходим). Если начало и конец совпадают, то у него чётный индекс, а значит, нет нечётных вершин. Иначе начало и конец нечётны: две нечётные вершины. $\square$

Я нигде не ошибся?

[Kallikanzarid]

caxap в сообщении #472466 писал(а):

Доказать, что граф уникурсален [можно пройти весь, пройдя по каждому ребру один раз] $\iff$ он содержит не более двух вершин нечётного индекса.

По лемме о рукопожатии их либо ноль, либо две. Если две, то проводим между ними ребро и сводим таким образом к предыдущей задаче.

[caxap]

Что далеко ходить: можно и сразу использовать лемму о том, что граф уникурсален $\iff$ он содержит не более двух вершин нечётного индекса Предположим, что я не знаю никаких лемм. Я школьник и знания у меня школьные. У меня нет ни книг, ни интернета: в моём распоряжении только та книжка по наглядной топологии. Вчера я только из неё узнал понятие графа. Прорешал несколько предлагаемых задачек и их могу использовать как известные леммы. Всё.

Я тут пишу, пишу..., а хотя бы одно из моих доказательств (с учётом исправлений) верно? В частности, последнее? (На собственных ошибках учится легче.)

[Kallikanzarid]

Цитата:

Задача 24. Доказать, что граф уникурсален [можно пройти весь, пройдя по каждому ребру один раз] $\iff$ он содержит не более двух вершин нечётного индекса.

$\Leftarrow:$ Вершин нечётного индекса всегда чётное число. Если их ноль, то это прошлая задача. Пусть их две. Выходим из нечётной вершины, при этом мы "убираем" одно ребро и вершина становится чётной, поэтому у нас остаётся только одна нечётная вершина, в которой мы должны остановится. Пусть $a$ -- первая вершина, из которой выходит не пройденное ребро.

Стираем первый цикл. Если оставшийся граф несвязен, забудем про все части кроме той, в которой находится $a$. Мы имеем связный конечный граф с чётными вершинами, его можно пройти весь и вернуться снова в $a$ (предыдущая задача). Объединяем этот цикл с первым. И так далее, пока весь граф не пройдём.

$\Rightarrow:$ Пусть имеется "уникурсальный" обход графа. Все "проходные" вершины, не являющиеся началом и концом пути, должны иметь чётный индекс (входим и выходим). Если начало и конец совпадают, то у него чётный индекс, а значит, нет нечётных вершин. Иначе начало и конец нечётны: две нечётные вершины. $\square$

Я нигде не ошибся?

Да вроде вот это верное, хотя я и не присматривался.