|
|
| Строка 1: |
Строка 1: |
| − | {{Определение
| |
| − | |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)
| |
| − |
| |
| − |
| |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | [[Категория: Основные определения теории графов]]
| |
