Рёберный граф

Определение:

Пусть задан граф [math]G[/math], тогда его рёберным графом [math]L(G)[/math] называется граф, для которого верны следующие утверждения любая вершина графа [math]L(G)[/math] представляет ребро графа [math]G[/math], две вершины графа [math]L(G)[/math] смежны тогда и только тогда, когда их соответствующие рёбра смежны в [math]G[/math].

Граф [math]G[/math] и его реберный граф [math]L(G)[/math]

Построение

Граф [math]G[/math]	Новые вершины [math]L(G)[/math]	Добавлены рёбра в [math]L(G)[/math]	Рёберный граф [math]L(G)[/math]

Свойства

Утверждение:

Рёберный граф связного графа связен.

[math]\triangleright[/math]

Если [math]G[/math] связен, он содержит путь, соединяющий любые два его ребра, что переводится в путь графа [math]L(G)[/math], содержащий любые две вершины графа [math]L(G)[/math].

[math]\triangleleft[/math]

Утверждение:

Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.

Утверждение:

Рёберное хроматическое число графа [math]G[/math] равно вершинному хроматическому числу его рёберного графа [math]L(G)[/math].

Утверждение:

Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.

Утверждение:

Если граф [math]G[/math] — Эйлеров граф, то его рёберный граф является Гамильтоновым графом.

[math]\triangleright[/math]

Для доказательства приведем контрпример к обратному утверждению. На следующем рисунке граф [math]L(G)[/math] — Гамильтонов граф, а граф [math]G[/math] не является Эйлеровым графом.

[math]\triangleleft[/math]

Утверждение:

Ребра графа [math]G[/math] можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.

Утверждение:

Реберный граф реберного графа [math]L(G)[/math] не является исходным графом [math]G[/math].

[math]\triangleright[/math]

Контрпримером является граф и раздела Построение. Построив по указанному принципу реберный граф к графу [math]L(G)[/math], мы убедимся, что он не совпадает с исходным графом [math]G[/math].

[math]\triangleleft[/math]

Теорема:

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

Доказательство:

[math]\triangleright[/math]

По определению реберного графа граф [math]L(G)[/math] имеет [math]q[/math] вершин. Каждые [math]d_i[/math] ребер, инцидентных вершине [math]v_i[/math], дают вклад [math]\begin{pmatrix} d_i \\ 2 \end{pmatrix}[/math] в число ребер графа [math]L(G)[/math], так что [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]

[math]\triangleleft[/math]

Источники информации

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