90
правок
Изменения
Новая страница: «{{Определение |definition = Пусть задан граф <tex>G</tex>, тогда его рёберным графом <tex>L(G)</tex> называ...»
{{Определение
|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|Граф G и его реберный граф L(G)]]
==Свойства==
{{Утверждение
|statement=Рёберный граф [[Отношение_связности,_компоненты_связности|связного графа]] связен.
|proof= Если 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>.
}}
{{Теорема
|id=Теорема1
|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 + {\dfrac{1}{2}}\sum\limits_i{d_{i}^{2}}</math>
|proof=По определению реберного графа граф <tex>L(G)</tex> имеет <tex>q</tex> вершин. Каждые <math>d_i</math> ребер, инцидентных вершине <math>v_i</math>, дают вклад <math>\begin{pmatrix} d_i \\ 2 \end{pmatrix}</math> в число ребер графа <tex>L(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>
}}
==Построение==
{| 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>
|}
==Источники информации==
*[[wikipedia:ru:Рёберный_граф | Wikipedia {{---}} Реберные графы ]]
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.(Глава 8: Реберные графы. стр. 91-104)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
|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|Граф G и его реберный граф L(G)]]
==Свойства==
{{Утверждение
|statement=Рёберный граф [[Отношение_связности,_компоненты_связности|связного графа]] связен.
|proof= Если 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>.
}}
{{Теорема
|id=Теорема1
|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 + {\dfrac{1}{2}}\sum\limits_i{d_{i}^{2}}</math>
|proof=По определению реберного графа граф <tex>L(G)</tex> имеет <tex>q</tex> вершин. Каждые <math>d_i</math> ребер, инцидентных вершине <math>v_i</math>, дают вклад <math>\begin{pmatrix} d_i \\ 2 \end{pmatrix}</math> в число ребер графа <tex>L(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>
}}
==Построение==
{| 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>
|}
==Источники информации==
*[[wikipedia:ru:Рёберный_граф | Wikipedia {{---}} Реберные графы ]]
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.(Глава 8: Реберные графы. стр. 91-104)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
