• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Ребровий граф

Розглянемо|розгледимо| двох графів 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. Тому

.

Переглядів: 499