Индивидуальное задание 10. Теория графов. Деревья.
Задание 1. Неориентированный граф задан матрицей смежности (табл.1). Построить граф. Вычислить число различных деревьев заданного графа. Изобразить все возможные деревья.
Таблица 1. Варианты заданий
| 6 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 1 | |
| 3 | 0 | 1 | ||
| 4 | 0 |
Ниже приведено подробное решение задачи.
Задача состоит из двух частей:
Шаг 1. Представление матрицы смежности и построение графа.
Матрица смежности задана для четырех вершин (1, 2, 3, 4). Из таблицы видно, что элементы следующие: Для вершины 1: связи с вершинами 3 и 4 (записи 1-3 и 1-4, так как 0 для связи с вершиной 2). Для вершины 2: связи с вершинами 3 и 4 (2-3 и 2-4). Для вершины 3: связь с ве...