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

9.3. АЛГОРИТМ ВЫЧИСЛЕНИЯ ЧИСЛА КОМПОНЕНТ СВЯЗНОСТИ ГРАФА

Шаг.1. Найти ненулевой элемент матрицы смежности, не стоящий на главной диагонали. Если он существует, перейти шагу.2, если нет, то перейти к шагу.3.

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

вершин xi и x j перейти к шагу.1.

Шаг.3. Подсчитать количество р строк матрицы, содержащих ненулевые элементы на главной диагонали. Результат: количество компонент связности мультиграфа равно р.

Упражнения

1. В неорграфе G = (X, U), в котором ½X½= 10 и X = { x1, x2, x3, x4, x5, x6, x7, x8, x9, x10} и U ¹ Æ, были склеены вершины x3 и x7 . В результате выполнения этой операции был получен граф G ’ = (X ’, U ’ ) c новым числом вершин. Установить соответствие между номерами вершин графа G и графа G ’.

84

2. Определить число компонент связности в графе G, заданного матрицей смежности R =(ri,j) , элементы которой равны: r1,2= 2 , r2,3= 1, r4,11= 1, r5,9= 1, r6,7= 2 , r4,10= 2, r11,10= 2, r7,8 = 1 (значения симметричных элементов матрицы R получить самостоятельно; значения неуказанных элементов при-равнять «нулю»), с помощью алгоритма рассмотренного в данной теме.

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

4.Разработать алгоритм определения числа компонент связности для компьютерной обработки.