Определение

Компонентами связности графа G называются максимальные связные подграфы этого графа.

Здесь максимальность понимается как максимальность числа вершин и ребер, входящих в компоненты связности.

То есть связный подграф G₁= (V₁, U₁) графа G = (V, U) называется компонентой связности этого графа, если он содержит все ребра из U, начала и концы которых лежат в V_1, и множество V₁ не может быть расширено так чтобы, G₁ остался связным.

Пример. Граф, изображенный на рис.5.14, имеет три компоненты связности.

Рис.5.14

Упражнения

1. Показать, что компоненты связности неориентированного графа образуют разбиения множеств вершин и ребер графа на части, относящиеся к разным компонентам.

2. Показать, что предыдущее свойство не всегда верно для ориентированных графов.

5.6. Транзитивное замыкание графов определение

Граф G₁ = (V, U₁) называется транзитивным замыканием графа G = (V, U), если (a, b) U₁ (в графе G вершины a и b соединяет некоторый путь).

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

Определим операцию логического умножения двоичных матриц.

Пусть A = (a_i,_j) и B = (b_i,_j)  двоичные матрицы, имеющие размер n n. Двоичная матрица C = (c_i,_j) размером n n, является логическим произведением A и B, если значение элемента c_i,_j, лежащего на пересечении строки с номером i и столбца с номером j матрицы C, равно:

c_i,j = .

Логическое произведение матриц A и B записывается как A B.

Тогда, если A  это матрица смежности для графа G = (V, U), где V = {v₁, ... v_n}, то a_i,j = 1 тогда и только тогда, когда из вершины v_i в вершину v_j ведет ребро.

В матрице A A значение a_i,_j = 1 тогда и только тогда когда в графе G из v_i в v_j ведет путь длиной 2.

Аналогично в матрице A^r = A ... A (произведение r матриц A) элемент a_i,_j равен 1 тогда и только тогда, когда в G из v_i в v_j ведет путь длиной r  1.

Если вершины v_i и v_j в графе G с n вершинами соединяет некоторый путь, то существует и элементарный путь между этими вершинами, который имеет длину, не превосходящую n  1.

Поэтому матрица B = A⁰ A¹ A² ... A^n1 представляет транзитивное замыкание графа G.

Здесь дизъюнкция матриц понимается как поэлементная дизъюнкция одинаково расположенных в них элементов. Матрица A⁰  это единичная диагональная матрица, которая содержит значение 1 только на главной диагонали. Такая матрица представляет наличие путей нулевой длины из всякой вершины графа в эту же вершину.

Действительно, элемент b_i,_j матрицы B принимает значение 1 тогда и только тогда, когда вершины v_i и v_j в G соединяет хотя бы один путь, длина которого не превосходит n  1.

5.7.Деревья

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

Пусть G = (V, U)  это некоторый граф. Ребро u  U называется циклическим ребром, если в G имеется элементарный цикл ненулевой длины, проходящий через концы ребра u. Нетрудно проверить, что если ребро u является циклическим в графе, то существует элементарный цикл длины не меньше, чем 3, содержащий u.