Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 6

r

x0

x1

x2

x3

x4

x5

x0

0

2

µ

µ

5

µ

x1

2

0

µ

2

4

5

x2

µ

µ

µ

µ

µ

µ

x3

µ

2

µ

0

µ

3

x4

5

4

µ

µ

0

3

x5

µ

5

µ

3

3

0

3. 2 Числа графа

Функции, заданные на множестве графов {G=<X; r>} и принимающие значения на множестве целых чисел, называют числовыми характеристиками графа или просто числами. Наиболее очевидными и простыми числами являются: число вершин - n, число рёбер - m, степени вершин - di(или di+/di-). Остальные числа графа требуют вычисления их значений.

Число компонент связности графа G=<X; r>. Если множество вершин графа G можно разбить на попарно непересекающиеся непустые подмножества X={X1’;X2’;…;Xk’} так, чтобы никакие две вершины из разных подмножеств не были смежны, то подграфы G1=<X1’;r1’>,  G2=<X2’;r2’>,…, Gk=<Xk’;rk’> являются связными, а их число называют числом компонент связности графа G и обозначают k(G). Поиск числа компонент связности графа есть результат решения системы соотношений: если XiÈXj¢=X и  Xi¢ÇXj¢=Æ для i¹j, 1£i, j£k, то  существуют графы, для которых GiÈGj=G и GiÇGj=Æ для i¹j, 1£i,j£k . Для поиска числа компонент связности используют механизм вычисления матриц достижимости (см. 3.3) и определения полных подграфов.

На рис. 18 дан граф, содержащий три компоненты графа G=<X; r>, где

X={x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11}, G1=<X1; r1>, где X1={x1, x2, x3, x4},

G2=<X2; r2>, где X2={x5, x6, x7, x8}, G3=<X3; r3>, где X3={x9, x10, x11}.

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

Цикломатическое число можно определить по формуле l(G)=m-n+k(G),

где m - число рёбер, n - число вершин, k(G) - число компонент связности графа. Для графа на рис. 19 имеем n=8, m=10, k(G)=2 и l(G)=10-8+2=4.

Cледовательно, для устранения циклов в данном графе нужно удалить минимум четыре ребра. Например,  {(x1, x2), (x2, x3), (x2, x4), (x6, x8)} или    {(x1, x5), (x4, x5),

(x3, x4), (x6, x7)}.

Хроматическое число графаG=<X;r>. Раскраской вершин графа в g цветов называют разбиение множества вершин связного графа на попарно непересекающиеся непустые подмножества, состоящие из попарно несмежных вершин, т.е. Xi ÈXj¢=X и Xi¢ÇXj¢=Æ, для i¹j, 1 £i, j £g.

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

Нахождение хроматического числа достаточно трудоёмкая задача. Однако, можно дать оценку этого числа. Так хроматическое число полного n-вершинного графа равно n, пустого графа - 1, графа с циклом чётной длины - 2, графа с циклом нечётной длины - 3, графа типа дерево - 2. В отдельных случаях может быть рекомендована оценка по следующей формуле: g£maxi{di+1}. Например, для графа на рис. 12а) g=5, на рис. 12b) r=1, на рис. 13а) g=2, на рис. 20  g=4.

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

r(G)= maxi{|X¢i|}.

Например, для графа на рис. 13a)  r=5, на рис. 20 r=4 и т. д.

Механизм вычисления плотности приведен в 3.3.

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