[Список тем] [Вступление к этой теме] [1] [2] [3]

Элементы графов

После рассмотрения определений, относящихся к графам как к цельным объектам, естественно дать определения различным составным элементам графов.

1. Подграфы

Граф G'(V', Е') называется подграфом графа G(V, Е) (обозначается G' G), если V' V и/или Е' Е.
Если V' = V, то G' называется остовным подграфом G.
Если V' V & E' E & (V' V Е' Е), то граф G' называется собственным подграфом графа G.
Подграф G'(V',E') называется правильным подграфом графа G(V,E), если G' содержит все возможные ребра G:

Правильный подграф G'(V', E') графа G(V, E) определяется подмножеством вершин V'.

2. Cтепень вершины

Количество ребер, инцидентных вершине v, называется степенью (или валентностью) вершины v и обозначается d(v):

Обозначим минимальную степень вершины графа G через (G), а максимальную — через Δ(G):

Если степени всех вершин равны k, то граф называется регулярным степени k:

Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено.
Пример
На рис. 7 приведена диаграмма регулярного графа степени 3.

Рис. 7. Диаграмма регулярного графа степени 3

Если степень вершины равна 0 (то есть d(v) = 0), то вершина называется изолированной. Если степень вершины равна 1 (то есть d(v) = 1), то вершина называется концевой, или висячей.
Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода, а входящих — полустепенью захода. Обозначаются эти числа, соответственно, d^-(v) и d⁺(v).

ТЕОРЕМА (Эйлера)
Сумма степеней вершин графа равна удвоенному количеству ребер:

Доказательство

При подсчете суммы степеней вершин каждое ребро учитывается два раза: для одного конца ребра и для другого.

3. Маршруты, цепи, циклы

Маршрутом в графе называется чередующаяся последовательность вершин и ребер
v₀,e₁,v₁,e₂,v₂,...,e_k,v_k,
в которой любые два соседних элемента инцидентны.

Замечание
Это определение подходит также для псевдо-, мульти- и орграфов. Для “обычного” графа достаточно указать только последовательность вершин или только последовательность ребер.

Если v₀ = v_k, то маршрут замкнут, иначе открыт.
Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи v₀, e₁, ... ,e_k, v_k вершины v₀ и v_k называются концами цепи. Говорят, что цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v, обозначается <u,v>. Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины.
Замкнутая цепь называется циклом, замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.
Для орграфов цепь называется путем, а цикл — контуром.
Пример
В графе, диаграмма которого приведена на рис. 8:
1. v₁, v₃, v₁, v₄ — маршрут, но не цепь;
2. v₁, v₃, v₅, v₂, v₃, v₄ — цепь, но не простая цепь;
3. v₁, v₄, v₃, v₂, v₅ — простая цепь;
4. v₁, v₃, v₅, v₂, v₃, v₄, v₁ — цикл, но не простой цикл;
5. v₁, v₃, v₄, v₁ — простой цикл.

Рис. 8. Маршруты, цепи, циклы

4. Расстояние между вершинами

Длиной маршрута называется количество ребер в нем (с повторениями). Если маршрут М = v₀, e₁, v₁, e₂, v₂, ..., e_kv_k, то длина М равна k (обозначается |М| - k).
Расстоянием между вершинами u и v (обозначается d(u,v)) называется длина кратчайшей цепи <u, v>, а сама кратчайшая цепь называется геодезической.

Замечане
Если <u, v>, то по определению d(u, v): = + .

Диаметром графа G (обозначается D(G)) называется длина длиннейшей геодезической цепи.
Множество вершин, находящихся на одинаковом расстоянии n от вершины v (обозначение D(v,n)), называется ярусом:

5.Связность

Говорят, что две вершины в графе связаны, если существует соединяющая их (простая) цепь. Граф, в котором все вершины связаны, называется связным.

Определение
Граф G называется связным, если для любых двух его вершин существует путь, их соединяющий.

Отношение связанности вершин является эквивалентностью. Классы эквивалентности по отношению связанности называются компонентами связности графа. Число компонент связности графа G обозначается k(G). Граф G является связным тогда и только тогда, когда k(G) = 1. Если k(G) > 1, то G — несвязный граф. Граф, состоящий только из изолированных вершин (в котором k(G) = p(G) и r(G) = 0), называется вполне несвязным.

Вопросы тестирования по теме:

Графом G(V,E) называется
Маршрутом в графе называется
Степенью вершины v в графе называется
Длиной маршрута в графе называется
Циклом называется
Простым циклом называется
Ациклическим называется
Путем называется
Контуром называется
Простой цепью называется
Если степени всех вершин в графе равны k, то граф называется
Если степень вершины равна 0, то вершина называется
Если степень вершины равна 1, то вершина называется
Если начальная и конечная вершины маршрута совпадают, то маршрут называется
Если начальная и конечная вершины маршрута не совпадают, то маршрут называется

Из предыдущих занятий темы:

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

[Список тем] [Вступление к этой теме] [1] [2] [3]