90
правок
Изменения
Нет описания правки
}}
[[Файл:Line_graph_example.png|400px|thumb|center|Граф <tex>G </tex> и его реберный граф <tex>L(G)</tex>]]==Построение=={| cellpadding="0"| [[Файл:line_graph_build_1.png|200px]] || [[Файл:line_graph_build_2.png|200px]] || [[Файл:line_graph_build_3.png|200px]] || [[Файл:line_graph_build_4.png|200px]]|-|Граф <tex>G</tex> || Новые вершины <tex>L(G)</tex> || Добавлены рёбра в <tex>L(G)</tex> || Рёберный граф <tex>L(G)</tex>|}
==Свойства==
{{Утверждение
|statement=Рёберный граф [[Отношение_связности,_компоненты_связности#connected_graph|связного графа]] связен.|proof= Если <tex>G </tex> связен, он содержит [[Основные_определения_теории_графов#path|путь]], соединяющий любые два его ребра, что переводится в путь графа <tex>L(G)</tex>, содержащий любые две вершины графа <tex>L(G)</tex>.
}}
{{Утверждение
}}
{{Утверждение
|statement=Рёберный граф [[wikipedia:ru:Рёберно-транзитивный_граф|рёберно-транзитивного графа ]] является [[wikipedia:ru:Вершинно-транзитивный_граф|вершинно-транзитивным графом]].
}}
{{Утверждение
|statement=Если граф <tex>G</tex> {{---}} [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов#euler_graph|Эйлеров граф]], то его рёберный граф является [[Гамильтоновы_графы#hamiltonian_graph|Гамильтоновым графом]].
|proof=Для доказательства приведем контрпример к обратному утверждению. На следующем рисунке граф <tex>L(G)</tex> {{---}} Гамильтонов граф, а граф <tex>G</tex> не является Эйлеровым графом.
[[Файл:Line_graph_gam_euler.PNG|300px]]
{{Утверждение
|statement=Реберный граф реберного графа <tex>L(G)</tex> '''не''' является исходным графом <tex>G</tex>.
|proof=Контрпримером является граф и раздела [[#Построение|Построение]]. Построив по указанному принципу реберный граф к графу <tex>L(G)</tex>, мы убедимся, что он не совпадает с исходным графом <tex>G</tex>.
}}
<math>q_L = \sum\limits_i{\begin{pmatrix} d_i \\ 2 \end{pmatrix}} = \dfrac{1}{2}\sum\limits_i{d_i(d_i-1)} = \dfrac{1}{2}\sum\limits_i{d_i^2}-\dfrac{1}{2}\sum\limits_i{d_i} = \dfrac{1}{2}\sum\limits_i{d_i^2-q}</math>
}}
==Источники информации==
