Обсуждение участника:SergeyBud

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

Свойства

Граф G и его реберный граф L(G)
  • Рёберный граф связного графа связен.
  • Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.
  • Рёберное хроматическое число графа [math]G[/math] равно вершинному хроматическому числу его рёберного графа [math]L(G)[/math].
  • Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.
  • Если граф [math]G[/math] имеет Эйлеров цикл, то есть [math]G[/math] связен и имеет чётное число рёбер в каждой вершине, то его рёберный граф является Гамильтоновым графом.
  • Ребра графа [math]G[/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 + \frac{1}{2}\sum{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{\begin{pmatrix} d_i \\ 2 \end{pmatrix}} = \frac{1}{2}\sum{d_i(d_i-1)} = \frac{1}{2}\sum{d_i^2}-\frac{1}{2}\sum{d_i} = \frac{1}{2}\sum{d_i^2-q}[/math]
[math]\triangleleft[/math]

Построение

Line graph build 1.pngLine graph build 2.pngLine graph build 3.pngLine graph build 4.png

Граф [math]G \rightarrow [/math] Вершины [math]L(G)[/math], созданные из ребер графа [math]G \rightarrow [/math] Добавлены рёбра в [math]L(G) \rightarrow [/math] Рёберный граф [math]L(G)[/math]

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

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