Учебное пособие: Дискретная математика

2.9 Структурный анализ графов

41

1. Упорядочим полученные множества вершин в порядке убывания их карди-

нальных чисел: x

2

x

4

x

5

x

7

; x

1

x

3

x

6

x

8

; x

4

x

8

; x

2

x

6

; x

3

x

7

; x

1

x

5

.

2. Припишем вершинам множества

(x

2

, x

4

, x

5

, x

7

) цвет «1» (цвет выбирается

произвольно).

3. Удалим раскрашенные вершины из всех множеств и оставшиеся множества

упорядочим в порядке убывания их мощности:

(x

1

, x

3

, x

6

, x

8

); x

8

; x

6

; x

3

; x

1

.

4. Припишем вершинам множества x

1

, x

3

, x

6

, x

8

цвет «2».

5. Удалим раскрашенные вершины из всех множеств.

Получаем пустое множество.
Вывод. Это говорит о том, что все вершины графа G — раскрашены. Для рас-

краски потребовалось всего два цвета, т. е. хроматическое число

γ

(G) графа G

равно двум:

γ

(G) = 2.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.9.2 Компоненты связности графа

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Граф G

(X,U) связен, если любые его две вершины можно соеди-

нить простой цепью.

Подграф G

′

графа G называется компонентой связности гра-

фа G, если:

1) подграф G

′

связен;

2) подграф G

′

обладает свойством максимальности, т. е. если

G

′′

— некоторый другой связный подграф графа G и G

′

⊂

⊂ G

′′

, то графы G

′

и G

′′

совпадают.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Иными словами, компонента связности — это наибольший связный
подграф данного графа.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

Пример 2.15

. . . . . . . . . . . . . . . . . . . . .

Граф G

=

(X,U) (рис. 2.24) содержит две компоненты связности: G

′

с верши-

нами

(x

1

, x

2

, x

3

, x

4

, x

5

) и G

′′

с вершинами

(x

6

, x

7

, x

8

, x

9

).

42

Глава 2. Теория графов

Рис. 2.24 – Граф G содержит две компоненты связи: G

′

и G

′′

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Способ определения числа компонент связности графа.
При помощи матрицы смежности графа G можно определить число компонент

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Мультиграф G

′

=

(X

′

, U

′

) можно получить из мультиграфа G =

=

(X,U) при помощи пошагового выполнения операции элемен-

тарной склейки вершин x

i

и x

j

из множества X , если:

1) X

′

=

(X/({x

i

} ∪ {x

j

})) ∪ {z}, где z /∈ X;

2)

(x

m

, x

l

, n

) ∈ U

′

, где

(m,l /= i,j), n — номер ребра (x

m

, x

l

),

тогда и только тогда, когда

((x

m

, x

l

),n) ∈ U, и (x

m

, z, n

) ∈ U

′

,

где

(m /= i,j).

Здесь z — «новая» вершина G

′

, полученная от склеивания вершин

в графе G.

Из условий 1, 2 следует, что склеиваются только те пары вершин,
которые являются концами одного и того же ребра. Ориентация
рёбер на операцию склеивания не влияет.

Очевидно, что после каждого выполнения операции «склеивания»
количество вершин множества X

′

уменьшается на единицу, а ко-

личество рёбер и их идентификационные номера остаются неиз-
менными, т.е.

∣U

′

∣ = ∣U∣.

Иными словами, при склейке вершин x

i

и x

j

склеиваются только

концы дуг, совпадающие с x

i

и x

j

, а сами дуги сохраняются.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

Пример 2.16

. . . . . . . . . . . . . . . . . . . . .

В графе G (рис. 2.25) поэтапно выполнить операцию склеивания вершин.

2.9 Структурный анализ графов

43

Рис. 2.25 – Граф G

Решение:

1-этап. В графе G склеиваем вершины x

1

и x

2

. Получаем граф G

′

(рис. 2.26),

где вершина x

k

= x

1

+

x

2

.

Рис. 2.26 – Граф G

′

, полученный из графа G склеиванием вершин x

1

и x

2

2-этап. В графе G

′

склеиваем вершины x

3

и x

k

. Получаем граф G

′′

(рис. 2.27),

где вершина x

′

= x

3

+

x

k

.

Рис. 2.27 – Граф G

′′

получен из графа G

′

склеиванием вершин x

3

и x

k

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

Выводы

. . . . . . . . . . . . . . . . . . . . . . . . .

Очевидно, поэтапное попарное склеивание вершин графа, принадлежащих од-

ной и той же компоненте связности, не изменяет количества компонент связности.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Процедура склеивания вершин графа должна выполняться поэтапно для каж-

дой пары вершин, из множества тех вершин, к которым можно применять данную
процедуру. После каждого склеивания какой-либо пары вершин получается «но-
вый» граф, в котором нарушен естественный порядок нумерации вершин, в силу

44

Глава 2. Теория графов

того, что количество вершин в новом графе на одну меньше числа вершин в графе,
из которого он получен, и появляется вершина с неопределённым номером.

Для восстановления естественной нумерации графа можно применить следу-

ющий способ.

Обозначим

∣X∣ через n. Это число вершин графа G

(k)

, полученного на k-й ите-

рации склеивания вершин, где k

= 0, 1, . . ., t. Перенумеруем вершины графа G

′

,

полученного элементарной склейкой x

i

и x

j

, следующим способом.

Номера вершин, начиная с первого до i − 1, сохраняют свои значения. Номера

вершин, начиная с i + 1 до j − 1, уменьшают свои значения на единицу, номера
остальных вершин уменьшают значения на две единицы.

«Новой» вершине x

′

присваивается номер (n − 1).

Так вершины графа G

′

(рис. 2.26) получат следующие номера: вершина x

′

—

номер 2; вершина x

3

— номер 1. Единственная вершина x

′′

графа G

′′

(рис. 2.27)

получит номер «1».

Если исходный граф G

(X,U) задан матрицей смежности, то значения элемен-

тов матрицы смежности нового графа G

′′

, полученного в результате склеивания

какой-либо пары вершин из множества X , можно получить, выполняя следующие
вычисления.

Обозначим через f

(k) (k = 1,2,...,n − 2) старый номер вершины с новым но-

мером k. Тогда матрица

∣∣a

′
ijk

∣∣ нового графа строится по матрице ∣∣a

ij

∣∣ графа по

формулам:

a

′
lk

= a

f

(l)f (k)

(l,k ⩽ n − 2),

a

′
n

−1k

= a

if

(k)

+

a

lf

(k)

(k ⩽ n − 2),

a

′
l, n

−1

= a

f

(l)i

+

a

f

(l)j

(l ⩽ n − 2),

a

′
n

−1, n−1

= a

ii

+

a

ji

+

a

jj

.

Для графов G и G

′

имеем соответственно матрицы смежности A, A

′

:

A

=

XXXXX

XXXXX

XXXX

0 2 1
1 1 0
0 1 0

XXXXX

XXXXX

XXXX

;

A

′

=

∥

0 1
1 4∥

.

Процедура «склеивания» вершин графа продолжается до тех пор, пока это

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

Матрица смежности графа G

′′

(рис. 2.27), который получен из графа G (рис. 2.25)

с помощью поэтапного применения операции склеивания вершин, является вырож-
денной, следовательно, граф G содержит только одну компоненту связности.

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

45

. . . . . . . . . . . . . . . . . . . . . . . . .

Выводы

. . . . . . . . . . . . . . . . . . . . . . . . .

Изложенный способ позволяет построить алгоритм для подсчёта числа компо-

нент связности по матрице смежности «нового» графа, полученного на последней
итерации процедуры склеивания вершин.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Алгоритм для вычисления числа компонент связности графа.
Шаг 1. Найти ненулевой элемент матрицы смежности, не стоящий на главной

диагонали. Если он существует, перейти к шагу 2, если нет, то перейти к шагу 3.

Шаг 2. Произвести над матрицей операцию, отвечающую склейке вершин x

i

и x

j

, перейти к шагу 1.

Шаг 3. Подсчитать количество p строк матрицы, содержащих ненулевые эле-

менты на главной диагонали. Результат: число компонент связности графа равно p.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. Способы задания графов.

2. Классификация графов.

3. Что определяет метрика графа?

4. Чему равно расстояние между вершинами в графе?

5. Компоненты связности графа (определение).

6. Маршрут в графе (определение). Способы вычисления длины маршрута

в графе.

7. Определение связанного графа.

8. Понятие компоненты связанности графа.

9. Части графа.

10. Операции над графами. Унарные операции на графе: правило удаления

вершин и рёбер в графе, стягивание вершин по ребру, замыкания вершин.

11. Раскраска графа. Правильная раскраска вершин и рёбер графа. Хроматиче-

ское число графа.

12. Вершинные характеристики графа.

13. Внешне устойчивое множество графа.

14. Внутренне устойчивое множество графа.