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

Подграфы

Граф G'(V’, Е') называется Подграфом Графа G(V, E) (обозначается G' Ì G), если V’ Ì V И/или Е' Ì Е.

Если V’ = V, То G' Называется Остовным подграфом G.

Если V’ Ì V & E' Ì E & (V‘ ¹ V V Е' ¹ Е), То граф G’ Называется Собственным Подграфом графа G.

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

"U, v Î V’ (U, v) Î E => (U, v) Î Е'.

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

Валентность

Количество ребер, инцидентных вершине V, Называется Степенью (или Валент­ностью) Вершины V И обозначается D(V):

"U, v Î V 0£ d(V) £ P–1, D(v) = |Г(V)|.

Обозначим Минимальную Степень вершины графа G через d(G), А Максималь­ную — Через D(G):

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

D (G) = D(G) = K.

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

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

Если V0 = Vk, То маршрут Замкнут, Иначе Открыт.

Если все ребра различны, то маршрут называется Цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется Простой Цепью. В цепи V0, E1, ... ,Ek, Vk Вершины V0 И Vk Называются Концами Цепи. Говорят, что цепь с концами И и V соединяет Вершины И И V. Цепь, соединяющая вершины И И V, Обозначается (U,V). Очевидно, что если есть цепь, соединяющая вершины И И V, То есть и простая цепь, соединяющая эти вершины.

Замкнутая цепь называется Циклом; Замкнутая простая цепь называется Простым циклом. Число циклов в графе G обозначается Z(G). Граф без циклов называется Ациклическим.

Для орграфов цепь называется Путем, А цикл — Контуром.

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

Длиной маршрута Называется количество ребер в нем (с повторениями). Если маршрут М = V0, E1, V1, E2, V2, …,Ekvk, То длина М Равна K (обозначается |М| = K).

Расстоянием Между вершинами И И V (обозначается D(U,V)) называется длина кратчайшей цепи (U, V), а сама кратчайшая цепь называется Геодезической.

Диаметром Графа G (обозначается D(G)) называется длина длиннейшей геоде­зической.

Множество вершин, находящихся на одинаковом расстоянии П от вершины V (обозначение D(V,N)), Называется Ярусом:

D(V, N) = {UV | D(V, U)=N}.

Связность

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

Отношение связанности вершин является эквивалентностью. Классы эквива­лентности по отношению связанности называются Компонентами связности Гра­фа. Число компонент связности графа G Обозначается K(G). Граф G Является Связным Тогда и только тогда, когда K(G) = 1. Если K(G) > 1, то G — несвязный Граф. Граф, состоящий только из изолированных вершин (в котором K(G) = P(G) и R(G) = 0), называется Вполне несвязным.

< Предыдущая		Следующая >