Рёберный граф
Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.
Рёберное хроматическое число графа [math]G[/math] равно вершинному хроматическому числу его рёберного графа [math]L(G)[/math] .
Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.
Если граф [math]G[/math] — Эйлеров граф, то его рёберный граф является Гамильтоновым графом.
Ребра графа [math]G[/math] можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.
Реберный граф реберного графа [math]L(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 + >\sum\limits_i^>[/math]
По определению реберного графа граф [math]L(G)[/math] имеет [math]q[/math] вершин. Каждые [math]d_i[/math] ребер, инцидентных вершине [math]v_i[/math] , дают вклад [math]\begin d_i \\ 2 \end[/math] в число ребер графа [math]L(G)[/math] , так что
Источники информации
- Wikipedia — Реберные графы
- Харари Фрэнк Теория графов: Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом «ЛИБРОКОМ», 2009. — 296 с. — ISBN 978-5-397-00622-4.(Глава 8: Реберные графы. стр. 91-104)
- Алгоритмы и структуры данных
- Основные определения теории графов
Основные определения теории графов
В графе ребро, концы которого совпадают, то есть [math]e=(v, v)[/math] , называется петлей (англ. loop).
Два ребра, имеющие общую концевую вершину, то есть [math]e_1=(v, u_1)[/math] и [math]e_2=(v, u_2)[/math] , называются смежными (англ. adjacent).
Если имеется ребро [math] (v, u) \in E [/math] , то говорят:
- [math] v [/math] — предок (англ. direct predecessor) [math] u [/math] .
- [math] u [/math] и [math] v [/math] — смежные.
- Вершина [math] u [/math] инцидентна ребру [math] (v, u) [/math] .
- Вершина [math] v [/math] инцидентна ребру [math] (v, u) [/math] .
Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.
Граф с [math] p [/math] вершинами и [math] q [/math] рёбрами называют [math] (p, q) [/math] -графом. [math] (1, 0) [/math] -граф называют тривиальным.
Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,~v[/math] нельзя соединить более чем одним ребром [math](u, v)[/math] . Поэтому часто используют другое определение.
| Определение: |
| Ориентированным графом [math]G[/math] называется четверка [math]G = (V, E, \operatorname, \operatorname)[/math] , где [math]V[/math] и [math]E[/math] — некоторые множества, а [math]\operatorname, \operatorname : E \rightarrow V[/math] . |
Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).