1632
правки
Изменения
м
==Построение==
{| 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>
|}
rollbackEdits.php mass rollback
{{Определение
|definition =
Пусть задан граф <tex>G</tex>, тогда его '''рёберным графом ''' <tex>L(G)</tex> называется [[Основные_определения_теории_графов|граф]], для которого верны следующие утверждения
* любая вершина графа <tex>L(G)</tex> представляет ребро графа <tex>G</tex>,
* две вершины графа <tex>L(G)</tex> смежны тогда и только тогда, когда их соответствующие рёбра смежны в <tex>G</tex>.
}}
[[Файл: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:Вершинно-транзитивный_граф|вершинно-транзитивным графом]].
}}
{{Утверждение
|id=euler_gam|statement=Если граф <tex>G</tex> {{---}} [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов#euler_graph|Эйлеров граф]], то его рёберный граф является [[Гамильтоновы_графы#hamiltonian_graph|Гамильтоновым графом]].|proof=Для доказательства приведем контрпример к обратному утверждениюРассмотрим Эйлеров путь <tex>e_{i_1},v_{k_1},e_{i_2},\dots,v_{k_{n-1}},e_{i_n}</tex> в исходном графе <tex>G</tex>. На следующем рисунке граф Составим из вершин реберного графа <tex>L(G)</tex> последовательность <tex>v_{j_1},\dots,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},\dots,e_{t_{n---1}} Гамильтонов граф, а граф v_{j_n}</tex> в реберном графе <tex>L(G)</tex> не является Эйлеровым графом.[[Файл:Line_graph_gam_eulerДоказательство для циклов аналогично.PNG|300px]]
}}
{{Утверждение
{{Утверждение
|statement=Реберный граф реберного графа <tex>L(G)</tex> '''не''' является исходным графом <tex>G</tex>.
|proof=Контрпримером является граф из раздела [[#Построение|построение]]. В реберном графе количество вершин равно количеству ребер в исходном. Таким образом, в реберном графе к графу <tex>L(G)</tex> будет <tex>9</tex> вершин, а в исходном графе <tex>G</tex> их всего <tex>5</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>
}}
==Источники информации==
