1. Главная
  2. Библиотека
  3. Программирование
  4. Неориентированный граф задан матрицей смежности egin{array...
Решение задачи

Неориентированный граф задан матрицей смежности egin{array}{l} 02000 \ 20000 \ 00000 \ 00021 \ 00010 end{array} Сколько различных классов эквивалентности по бинарному отношению достижимости имеется в этом графе?

  • Программирование

Условие:

Неориентированный граф задан матрицей смежности
\begin{array}{l}
02000 \\
20000 \\
00000 \\
00021 \\
00010
\end{array}

Сколько различных классов эквивалентности по бинарному отношению достижимости имеется в этом графе?

Решение:

Мы начинаем с того, что рассмотрим заданную матрицу смежности графа:   Строка 1: 0 2 0 0 0   Строка 2: 2 0 0 0 0   Строка 3: 0 0 0 0 0   Строка 4: 0 0 0 2 1   Строка 5: 0 0 0 1 0 Рассмотрим шаг за шагом, как найти количество классов эквивалентности по бинарному отношению достижимости (то есть количество компонент связности). Шаг 1. Интерпретация матрицы Поскольку граф неориентированный, матрица должна быть симметричной. Проверим:  • Вершина 1 и вершина 2: элемент в строк...

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет