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

Рассмотрим два графа G и L(G). Граф G имеет произвольную форму, а вершины графа L(G) расположены на ребрах графа G. В этом случае граф L(G) называется реберным графом по отношению к графу G.

Английское название реберного графа – line graph, отсюда и обозначение графа – L(G). На рис. 12.7 показан реберный граф (он выделен жирными линиями), построенный для графа с рис. 12.1.

Рис. 12.7. Реберный граф

Теорема 12.6. Если – степенная последовательность (n, m) графа G, то L(G) является (m, )-графом, где

. (12.3)

Для графа G, показанного на рис. 12.7 (и рис. 12.1), его степенная последовательность: 1-3-2-3-3. Поэтому

.