Найти количество компонент связности в дополнительном (дополняющем) графе

Предмет: Математика
Раздел: Теория графов

Дана матрица смежности (или связности) графа, и нужно найти количество компонент связности в дополнительном (дополняющем) графе.

Шаг 1. Понимание задачи

Матрица связности задана для некоторого графа ( G ) с 6 вершинами:

 \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \ 1 & 0 & 1 & 0 & 1 & 0 \ 0 & 1 & 0 & 1 & 0 & 1 \ 1 & 0 & 1 & 0 & 1 & 0 \ 0 & 1 & 0 & 1 & 0 & 1 \ 1 & 0 & 1 & 0 & 1 & 0 \ \end{pmatrix} 

Элемент матрицы a_{ij} равен 1, если есть ребро между вершинами ( i ) и ( j ), и 0 — если ребра нет.

Шаг 2. Построение дополнительного графа

Дополнительный граф ( \overline{G} ) на тех же вершинах, но ребра в нем есть тогда и только тогда, когда ребра в исходном графе нет.

То есть, если в исходном графе смежность a_{ij} = 1, то в дополнительном графе \overline{a}_{ij} = 0, и наоборот (кроме диагонали, где всегда 0, так как петли не считаются).

Шаг 3. Запишем матрицу дополнительного графа

Для каждого элемента матрицы исходного графа:

 \overline{a}_{ij} = \begin{cases} 0, & \text{если } i = j \ 1 - a_{ij}, & \text{если } i \neq j \end{cases} 

Исходная матрица (для удобства):

[ \begin{array}{c|cccccc} & 1 & 2 & 3 & 4 & 5 & 6 \ \hline 1 & 0 & 1 & 0 & 1 & 0 & 1 \ 2 & 1 & 0 & 1 & 0 & 1 & 0 \ 3 & 0 & 1 & 0 & 1 & 0 & 1 \ 4 & 1 & 0 & 1 & 0 & 1 & 0 \ 5 & 0 & 1 & 0 & 1 & 0 & 1 \ 6 & 1 & 0 & 1 & 0 & 1 & 0 \ \end{array} ]

Тогда матрица дополнительного графа:

[ \overline{A} = \begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 & 0 & 1 \ 1 & 0 & 0 & 0 & 1 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 \ 1 & 0 & 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 1 & 0 & 0 \ \end{pmatrix} ]

Шаг 4. Найдем компоненты связности дополнительного графа

Посмотрим на вершины и ребра дополнительного графа:

• Вершина 1 связана с 3 и 5
• Вершина 2 связана с 4 и 6
• Вершина 3 связана с 1 и 5
• Вершина 4 связана с 2 и 6
• Вершина 5 связана с 1 и 3
• Вершина 6 связана с 2 и 4

Обозначим вершины:

• Группа 1: вершины 1, 3, 5 связаны между собой
• Группа 2: вершины 2, 4, 6 связаны между собой

Между группами ребер нет.

Ответ:

В дополнительном графе 2 компоненты связности:

2.

Если нужно, могу дополнительно расписать, как именно происходит обход графа (например, в глубину или в ширину) для поиска компонент связности.