Алгебра
Английский
Биология
География
Геометрия
История
Русский
Обществознание
Физика
Химия
Информатика
Литература
МатематикаВопрос:
Ниже изображен граф: Как должна выглядеть матрица идентичности для данного графа?
Ответ:
Решение:
Матрица идентичности (или матрица смежности) для неориентированного графа имеет размер NxN, где N — количество вершин в графе. В данном случае граф имеет 5 вершин, поэтому матрица будет 5x5.
Значение элемента aij равно 1, если существует ребро между вершинами i и j, и 0 в противном случае. Для неориентированного графа матрица симметрична.
Исходя из изображения графа, определим рёбра:
- Между вершинами 1 и 2
- Между вершинами 2 и 4
- Между вершинами 2 и 5
- Между вершинами 3 и 5
- Между вершинами 4 и 5
Заполним матрицу смежности:
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 |
| 3 | 0 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 1 |
| 5 | 0 | 1 | 1 | 1 | 0 |
Ответ: Матрица идентичности для данного графа выглядит следующим образом:
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 |
| 3 | 0 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 1 |
| 5 | 0 | 1 | 1 | 1 | 0 |
