На этом шаге мы приведем задачи для самостоятельного решения.
Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.
1. Представление графов с помощью матрицы смежности
1. В неориентированном графе GRAPH функция NEIGHBOUR1 находит список соседей вершины X (т.е. вершин, соединённых с ней хотя бы одним ребром) с помощью представления графа в виде матрицы смежности. Модифицируйте функцию NEIGHBOUR1, чтобы она правильно работала для ориентированных графов.
2. Определите количество рёбер, инцидентных данной вершине (степень вершины) в графе, заданном матрицей смежностей.
3. Граф задан матрицей смежности. Найдите все вершины, в которые существует путь длины не более 3 из данной (её номер k задан).
4. Граф задан матрицей смежности. Найдите все вершины, в которые существует путь из данной (её номер k задан).
5. Граф задан матрицей смежности. Найдите все вершины, из которых существует путь в данную, номер которой задан.
6. Напишите процедуру, которая по матрице смежностей и двум вершинам графа вычисляет: (1) число путей данной длины между данными двумя вершинами; (2) общее число путей между данными двумя вершинами; (3) длину кратчайшего пути между данными двумя вершинами.
7. Найдите все источники и стоки данного ориентированного графа с помощью представления графа в виде матрицы смежностей.
Указание. Источником ориентированного графа назовём вершину, из которой достижимы все другие вершины; стоком - вершину, достижимую из всех других вершин.
8. Найдите, используя матрицу смежностей, медиану графа, т.е. такую его вершину, что сумма расстояний от нее до остальных вершин минимальна.
9. Диаметром d связного графа G называется максимальное возможное расстояние между любыми двумя его вершинами. Найдите диаметр данного графа, используя матрицу смежностей.
10. Постройте матрицу достижимости по заданной матрице смежностей неориентированного графа.
11. В дереве, все вершины которого имеют степень не больше 3, найти самый длинный путь от выделенной вершины до вершины со степенью 1, используя матрицу смежностей дерева.
Указание. Деревом называется связный граф без циклов.
2. Представление графов с помощью матрицы инцидентности
1. Определите количество рёбер, инцидентных данной вершине (степень вершины) в графе, заданном матрицей инцидентности.
2. Напишите функцию для перехода между представлением графа с помощью матрицы смежностей и представлением графа с помощью матрицы инцидентности.
3. Для произвольного неориентированного графа определим матрицу соседства рёбер C=[Cij], где Cij=1, если i-е и j-е ребра инцидентны с общей вершиной, и Cij=0 в противном случае (Cii=0). Как можно выразить матрицу C через матрицу инцидентности?
4. [1, с.114] Докажите, что для произвольного неориентированного графа матрица смежности B выражается через матрицу инцидентности A так:
B = A × AT- diag[d1, ..., dn],
(1)Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с.
Со следующего шага мы начнем рассматривать структуры смежности.
