Лабораторная работа № 10 Числовые характеристики графа

Цель работы:

Теоретические сведения

Пусть G– связный граф, а u и v– две его несовпадающие вершины. Длина кратчайшего (u, v)-маршрута называется расстоянием между вершинами u и v и обозначается d(u, v). Положим d(u, u)=0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

1. d(u, v)≥0;

2. d(u, v)=0 тогда и только тогда, когда u=v;

3. d(u, v)=d(v, u);

4. d(u, v)+ d(v, w)=d(u, w) (неравенство треугольника).

Для фиксированной вершины u величина e(u)=max d(uv) называется эксцентриситетом вершины u. Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d(G). Тем самым

dG =max e(u)

Вершина v называется периферийной, если e(v)=d(G). Простая цепь длины d(G), расстояние между концами которой равно d(G), называется диаметральной цепью.

Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G).

Очевидно, что радиус графа не больше его диаметра.

Вершина v называется центральной, если e(v)=r(G). Множество всех центральных вершин графа называется его центром. Граф может иметь единственную центральную вершину или несколько центральных вершин. Наконец, центр графа может совпадать с множеством всех вершин.

Функции, заданные на множестве графов {G=<X;r>} и принимающие значения на множестве целых чисел, называют числовыми характеристиками графа или просто числами графа.

Наиболее очевидными и простыми числами графа являются: число вершин графа - n, число рёбер или дуг графа - m, степени и полустепени вершин графа - deg _i.

Все остальные характеристики графа требуют поиска и вычисления их значений.

Если множество вершин графа G можно разбить на попарно непересекающиеся непустые подмножества X={X₁;X₂;…;X_æ} так, чтобы никакие две вершины из разных подмножеств не были смежны, то связанные подграфы G₁=<X₁;r₁>, G₂=<X₂;r₂>,…,G_æ=<X_æ;r_æ> называются компонентами графа G=<X;r>, а их число æ- числом компонент связности графа G, которое обозначают æ(G).

G x₂ x₆

G₁ G₂

x₁ x₃ x₅ x₇

x₁₀

x₄ x₈

G₃

x₉ x₁₁

Рис. 24. Компоненты связности графа G=<X;r>.

Наименьшее число рёбер, удаление которых приводит к графу без циклов и петель, называют цикломатическим числом и обозначают ν(G). Цикломатическое число можно определить по формуле:

ν(G)=m-n+æ(G),

где m - число рёбер, n - число вершин, æ(G) - число компонент связности графа.

На рис. 25 дан пример определения цикломатического числа. Для графа G=<X;r> имеем:

n=8, m=10, æ(G)=2.

Следовательно, ν(G)=10-8+2=4. Можно убрать рёбра

{(x₁;x₂),(x₂;x₃),(x₂;x₄),(x₆;x₈)} или {(x₁;x₅);(x₄;x₅);(x₃;x₄);(x₆;x₇)}.

G

x₂ x₃

x₁ x₄

x₇

x₅

x₆ x₈

Рис. 25. Цикломатическое число графа G=<X;r>.

X=X₁X₂…X_;

X_iX_j=, где i ≠j, 1i,jn.

Тогда каждому подмножеству X_i можно соотнести особый цвет краски. В этом случае никакие две смежные вершины не могут быть окрашены в один цвет. Наименьшее число χ при котором никакие две смежные вершины графа не могут быть окрашены в один цвет, называют хроматическим числом графа.

Нахождение хроматического числа достаточно трудоёмкая задача, имеющая сложный алгоритм и требующая большого объёма вычислений. Однако, можно дать оценку этого числа. Так хроматическое число полного n-вершинного графа равно n, пустого графа - 1, графа с циклом чётной длины - 2, графа с циклом нечётной длины - 3, графа типа дерево - 2. В отдельных случаях может быть рекомендована оценка по следующей формуле: χmax_i{_i+1}.

Например, для графа, приведённого на рис. 25, хроматическое число равно 3, т.к. он содержит циклы нечётной длины: пусть x₁- красный, x₂ - синий, x₃- зелёный, x₄- красный, x₅- зелёный, x₆- красный, x₇- синий, x₈- зелёный.

Наибольшее число вершин полного подграфа G=<X;r>, между всеми вершинами которого задано отношение смежности, называют плотностью графа G и обозначают γ(G), т.е.

γ(G)= max_i{|X_i|}.

Например, для графа, приведённого на рис. 24, плотность графа равна 3, а на рис. 17а) - 5.

Наибольшее число попарно несмежных вершин графа G формирует число внутренней устойчивости графа.

Для поиска этого числа следует воспользоваться условием:

h_xiS=, где x_iS, SX и S-множество несмежных вершин графа G.

Таких подмножеств в графе G может быть несколько. Выбор из множества {S} подмножества с наибольшим числом вершин определяет число внутренней устойчивости, т.е.

h(G)=max_i{|S_i|}.

Наименьшее число вершин графа G смежных со всеми остальными вершинами графа формирует число внешней устойчивости графа. Для поиска этого числа следует воспользоваться условием:

h_xiТ= x_iT, TX и T-множество вершин графа G, смежных c вершинами X\T.

Таких подмножеств в графе G может быть несколько. Выбор из множества {T} подмножества с наименьшим числом вершин определяет число внешней устойчивости, т.е.

g(G)=min_i{|T_i|}.

Задания

Для заданного графа определить:

• диаметр и радиус графа;

• числа реберной и вершинной независимости;

• числа реберного и вершинного покрытия;

• цикломатическое и хроматическое числа.

Варианты заданий:

Контрольные вопросы