90
правок
Изменения
Нет описания правки
|id=euler_gam
|statement=Если граф <tex>G</tex> {{---}} [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов#euler_graph|Эйлеров граф]], то его рёберный граф является [[Гамильтоновы_графы#hamiltonian_graph|Гамильтоновым графом]].
|proof=Рассмотрим Эйлеров путь <tex>e_{i_1},v_{k_1},e_{i_2},...,v_{k_{n-1}},e_{i_n}</tex> в исходном графе <tex>G</tex>. Составим из вершин реберного графа <tex>L(G)</tex> последовательность <tex>v_{j_1},...,v_{j_n}</tex>, поcтавив в соответсвие ребру <tex>e_{i_k}</tex> вершину <tex>v_{j_k}</tex>. Так как два подряд идущих ребра <tex>e_{i_k},e_{i_{k+1}}</tex> из исходного пути смежны, то из определения реберного графа следует, что сответствующие подряд идущие вершины в получившейся последовательности <tex>v_{j_k},v_{j_{k+1}}</tex> смежны. Следовательно мы получили Гамильтонов путь <tex>v_{j_1},e_{t_1},...,e_{t_{n-1}},v_{j_n}</tex> в реберном графе <tex>L(G)</tex>. Доказательство для циклов аналогично.
}}
{{Утверждение
{{Утверждение
|statement=Реберный граф реберного графа <tex>L(G)</tex> '''не''' является исходным графом <tex>G</tex>.
|proof=Контрпримером является граф и раздела [[#Построение|Построение]]. Построив по указанному принципу реберный граф В реберном графе количество вершин равно количеству ребер в исходном. Таким образом, в реберном графе к графу <tex>L(G)</tex>будет <tex>9</tex> вершин, мы убедимся, что он не совпадает с исходным графом а в исходном графе <tex>G</tex> их всего <tex>5</tex>.
}}
