Изменения

Пусть задан граф <tex>G</tex>, тогда его рёберным графом <tex>L(G)</tex> называется [[Основные_определения_теории_графов|граф]], для которого верны следующие утверждения:

{{Утверждение|statement=Рёберный граф [[Файл:Line_graph_exampleОтношение_связности,_компоненты_связности|связного графа]] связен.png|400pxproof= Если G связен, он содержит [[Основные_определения_теории_графов|thumb|right|Граф G и путь]], соединяющий любые два его реберный граф ребра, что переводится в путь графа L(G)]]* Рёберный граф связного , содержащий любые две вершины графа связенL(G).* }}{{Утверждение|statement=Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе. * }}{{Утверждение|statement=Рёберное [[Раскраска_графа#chromatic_number_difinition|хроматическое число ]] графа <tex>G</tex> равно вершинному хроматическому числу его рёберного графа <tex>L(G)</tex>.* }}{{Утверждение|statement=Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.* }}{{Утверждение|statement=Если граф <tex>G</tex> имеет [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров циклграф]], то есть его рёберный граф является [[Гамильтоновы_графы|Гамильтоновым графом]].|proof=Для доказательства приведем контрпример к обратному утверждению. На следующем рисунке граф <tex>L(G)</tex> связен и имеет чётное число рёбер в каждой вершине{{---}} Гамильтонов граф, то его рёберный а граф <tex>G</tex> не является Гамильтоновым Эйлеровым графом.*[[Файл:Line_graph_gam_euler.PNG|300px]]}}{{Утверждение|statement=Ребра графа <tex>G</tex> можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.}}{{Утверждение|statement=Реберный граф реберного графа <tex>L(G)</tex> '''не''' является исходным графом <tex>G</tex>.}}

|statement=Если <tex>G</tex> {{---}} это <tex>(p,q)</tex> - граф с вершинами, имеющими степени <math>d_i</math>, то <tex>L(G)</tex> имеет <tex>q</tex> вершин и <math>q_L</math> ребер, где<math>q_L = -q + {\fracdfrac{1}{2}}\sum\limits_i{d_{i}^{2}}</math>

<math>q_L = \sum\limits_i{\begin{pmatrix} d_i \\ 2 \end{pmatrix}} = \fracdfrac{1}{2}\sum\limits_i{d_i(d_i-1)} = \fracdfrac{1}{2}\sum\limits_i{d_i^2}-\fracdfrac{1}{2}\sum\limits_i{d_i} = \fracdfrac{1}{2}\sum\limits_i{d_i^2-q}</math>

{| 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 \rightarrow </tex> Вершины || Новые вершины <tex>L(G)</tex>, созданные из ребер графа <tex>G \rightarrow </tex> || Добавлены рёбра в <tex>L(G) \rightarrow </tex> || Рёберный граф <tex>L(G)</tex>|}

* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.(Глава 8: Реберные графы. стр. 91-104)  [[Категория: Алгоритмы и структуры данных]][[Категория: Основные определения теории графов]]