Сколько ребер в графе у олеси
Перейти к содержимому

Сколько ребер в графе у олеси

  • автор:

Основные определения теории графов

В графе ребро, концы которого совпадают, то есть [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).

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

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

Рёберное хроматическое число графа [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)
  • Алгоритмы и структуры данных
  • Основные определения теории графов

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *