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

e(G)= max_i{|X¢_i|}.

Очевидно, что e(G)= r(ùG) и r(G)= e(ùG).

Для графа на рис. 12а)   e=0, на рис. 12b)   e=5, на рис 20   e=4.

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

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

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

h_xiÇS=Æ, где x_iÎS,

т. е. SÍX есть подмножество вершин графа G, попарно несмежных между собой.

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

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

На рис. 20 j(G)=4. Это S={x₀, x₂, x₄, x₆}

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

Число внешней устойчивости графа G=<X; r>. Наименьшее число вершин графа G, смежных со всеми остальными вершинами связного графа, формирует число внешней устойчивости, которое обозначают f(G). Для поиска этого числа следует найти h_xiÇТ¹Æ, где x_iÎX\T,

т. е. TÍX есть подмножество вершин графа, смежных c вершинами X\T.

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

На рис. 20 f (G)=2. Это T={{x₁, x₅}, {x₃, x₇}}.

Механизм вычисления внешней устойчивости см. 3.3.

3.3. Операции над графами

Алгебраические операции над одним графом - унарные операции,- позволяют находить основные числовые характеристики (связности, плотности, устойчивости и т.п.), а над двумя графами - бинарные операции,- формировать новые графы в результате объединения, пересечения, разности или композиции нескольких графов.

3.3.1. Унарные операции

Поиск плотности и неплотности графа. Для определения плотности графа достаточно определить матрицу достижимости h⁺ = IÈr и выполнить необходимое число перестановок строк и столбцов, чтобы найти блоки, опирающиеся на максимальное число вершин.

Для графа G=<X; r>  (см. рис. 20) приведена матрица смежности ||r||, найдена матрица ||h⁺|| и выполнены необходимые перестановки ее строк и столбцов.