Изменения

Перейти к: навигация, поиск
Нет описания правки
Если в неориентированном графе существует цикл, то в этом графе существует простой цикл.
|proof=
Выберем в графе минимальный по количеству рёбер цикл (он существует, потому что количество циклов рёбер в графе любом цикле — натуральное число <ref>[[Натуральные и целые числа#.D0.A1.D1.83.D1.89.D0.B5.D1.81.D1.82.D0.B2.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D0.B8.D0.BC.D0.B5.D0.BD.D1.8C.D1.88.D0.B5.D0.B3.D0.BE_.D1.8D.D0.BB.D0.B5.D0.BC.D0.B5.D0.BD.D1.82.D0.B0|Существование наименьшего элемента в любом подмножестве <tex>\Bbb N</tex>]]</ref>). Предположим, что он не простой. Но тогда он содержит дважды одну и ту же вершину, т. е. содержит в себе цикл меньшего размера, что противоречит тому, что наш цикл минимальный. Таким образом, этот цикл — простой.}}
[[Файл:Simple cycle.png|thumb|580px|center|Из В графе минимальный цикл включает в себя четыре ребра — таких цикла два: [2 - 5 - 6 - 4 - 2 - 6 - 7 - 3] получаем цикл (выделен <font color="red">красным</font>) и [2 - 5 - 6 - 7 - 34]. Для вершины 2 находим последнее ее вхождение в цикл и удаляем отрезок цикла, выделенный (выделен <font color=#3771c8ff>синим.</font>). Согласно теореме, оба они просты.<br>]]
== Замечания ==
Анонимный участник

Навигация