CLASS 1 «Представление графов с помощью матриц»

1.    Напишите программу, осуществляющую переход от представления графа с помощью матрицы смежностей к представлению графа с помощью матрицы достижимости.

2.    Напишите программу, осуществляющую переход от представления графа с помощью матрицы смежностей к представлению графа с помощью матрицы инцидентности.

3. Проверьте, имеет ли граф, заданный матрицей инцидентности, петли.

4. Постройте матрицу смежности графа. Установите, будет ли граф связным, если удалить к-ю заданную вершину.

5.    Посчитайте количество ребер в графе, заданном матрицей инцидентности.

6.    Определите, существуют ли в графе, заданном матрицей инцидентности, изолированные вершины.

7. Определите, является ли граф, заданный матрицей инцидентности, полным (в полном графе любые две вершины смежны).

8. Определите, является ли граф, заданный матрицей инцидентности, кольцом (кольцо -связный граф, степень каждой вершины которого равна 2).

9. Определите, каково среднее количество ребер в графе, заданном матрицей инцидентности.

10. Напишите программу, осуществляющую переход от представления графа с помощью матрицы инцидентности к представлению графа с помощью матрицы смежностей. Указание: Для произвольного неориентированного графа матрица смежностей В

выражается через матрицу инцидентности А следующим образом: B=AxA^T-diag [d₁,...,d_n].

где А^т - транспонированная матрица A, d_i-степень i-ой вершины, diag [d₁,...,d_n] - матрица размерности nxn с элементами d₁,...,d_n, расположенными на главной диагонали.

11. Определите степень каждой вершины (количество ребер, инцидентных данной вершине) в графе, заданном матрицей смежностей.

12. Посчитайте количество ребер в графе, заданном матрицей смежности.

13. Посчитайте количество кратных ребер в графе, заданном матрицей смежности.

               14. Посчитайте число вершин в графе (граф задан матрицей смежности), от которых отходит

более m ребер.

15.  Напишите программу, осуществляющую переход от представления графа с помощью матрицы инцидентности к представлению графа с помощью матрицы достижимости.

16. Определите степень каждой вершины (количество ребер, инцидентных данной вершине) в графе, заданном матрицей инцидентности.

17.  Напишите программу, определяющую существуют ли в графе, заданном матрицей смежности, изолированные вершины.

■

,18. В графе, заданном матрицей смежности, определите количество петель.

19. Установите, является ли граф, заданный матрицей смежности, регулярным (в регулярном графе степень всех вершин одинакова).

20.  Проверьте, есть ли в графе, заданном матрицей смежности, кратные ребра.

21. Определите, каково максимальное (минимальное) количество ребер, выходящих от одной вершины в графе, заданном матрицей смежности.

2.2.. Проверьте, имеет ли граф, заданный матрицей смежности, петли.

23. Определите максимальную кратность ребер в графе, заданном матрицей смежности.

24. Напишите программу, определяющую среднее количество ребер в графе, заданном матрицей смежности.

25. Определите, является ли граф, заданный матрицей инцидентности, звездой (звезда -граф, у которого одна вершина соединена со всеми, а у остальных степень равна 1).

26. Определите, каково минимальное количество ребер, отходящих от одной вершины, в графе, заданном матрицей инцидентности.

27. Определите, каково максимальное (минимальное) количество ребер, отходящих от одной вершины в графе, заданном матрицей инцидентности.

28. Определите, является ли граф, заданный матрицей инцидентности, регулярным (в регулярном графе степень всех вершин одинакова).

29.  Посчитайте количество кратных ребер в графе, заданном матрицей инцидентности.

30.  Посчитайте число вершин в графе (граф задан матрицей инцидентности), от которых отходит более m ребер.

31.  Установите, является ли граф, заданный матрицей смежности, полным (в полном графе любые две вершины смежны).

32. Определите степень каждой вершины (количество ребер, инцидентных данной вершине) в графе, заданном матрицей инцидентности.

33.  Проверьте, есть ли в графе, заданном матрицей инцидентности, кратные ребра.

34. Определите максимальную кратность ребер в графе, заданном матрицей инцидентности.

35.  В графе, заданном матрицей инцидентности, определите количество петель.

НОМE 1

Реализовать граф как класс на основе структуры Вирта. Методы:

-    добавление и удаление вершины;

-     добавление и удаление ребра (дуги);

-     ориентирование (неориентирование).

10

баллов

Реализовать процедуры преобразования структуры Вирта во все динамические и матричные (смежность, инцидентность, достижимость) структуры. Реализовать интерфейс для всех представлений.