На этом шаге мы приведем задачи для самостоятельного решения.

Определения, необходимые для решения задач.

(1) Графом Бержа называется ориентированный граф, в котором из любой вершины в любую другую идёт не более одной дуги, а при каждой вершине может быть не более одной петли.
(2) G-графом называется ориентированный граф Бержа, у которого из каждой вершины выходит хотя бы одна дуга.
(3) Операция надразбиения - это операция, состоящая в замене в неориентированном графе двух смежных рёбер (x,y) и (y,z), общая вершина v которых имеет степень 2, одним ребром (x,z).
Последовательно применяя операцию надразбиения, можно получить из произвольного графа G, содержащего вершины степени 2, граф, не содержащий вершин степени 2. Этот граф будем называть полным надразбиением графа G.

Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.

Представление графов с помощью списка рёбер (дуг)

1^*. Напишите функцию для определения количества рёбер в неориентированном графе, представленном списком рёбер.

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

3^*. Напишите функцию для определения количества дуг в ориентированном графе, представленном списком дуг.

4^*. Напишите функцию для определения в данном неориентированном графе, представленном списком рёбер, вершины, к которой примыкают рёбра от остальных вершин.

5^*. Напишите функцию для определения в данном ориентированном графе, представленном списком дуг, вершин, из которых не исходит ни одна дуга.

6^*. Напишите функцию для определения в данном неориентированном графе, представленном списком рёбер, количества рёбер, инцидентных некоторой вершине (степень вершины).

7^*. Напишите функцию для определения в данном ориентированном графе, представленном списком дуг, количества дуг, инцидентных некоторой вершине (степень вершины).

8^*. Напишите функцию для проверки, является ли неориентированный граф, заданный списком рёбер, однородным.

9^*. Напишите программу, определяющую какой из двух неориентированных графов, заданных списками рёбер, имеет большее число рёбер.

10^*. Напишите программу, определяющую какой из двух ориентированных графов, заданных списками дуг, имеет их больше.

11^*. Напишите программу, удаляющую из неориентированного графа, заданного списком рёбер, вершину, имеющую большее число смежных вершин.

12^*. Напишите программу, удаляющую из ориентированного графа, заданного списком дуг, вершину, имеющую большее число смежных вершин.

13^*. Напишите программу, удаляющую из неориентированного графа, заданного списком рёбер, все изолированные вершины.

14^*. Напишите программу, определяющую, является ли ориентированный граф, представленный списком дуг, графом Бержа.

15^*. Напишите программу для определения, является ли граф, представленный списком дуг, G-графом.

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

17^*. Проверьте на нескольких неориентированных графах, представленных списками рёбер, утверждение теоремы, утверждающей, что число нечётных вершин любого графа чётно.

18^*. Напишите программу, определяющую количество путей длины 3 из i-ой вершины в j-ю вершину заданного неориентированного графа, представленного списком рёбер.

19^*. Напишите программу для преобразования представления заданного неориентированного графа в виде списка рёбер, в представление в виде матрицы смежности.

20^*. Напишите программу для преобразования представления заданного неориентированного графа в виде матрицы смежности в представление в виде списка рёбер.

21^*. Напишите программу для построения по неориентированному графу, представленному с помощью списка рёбер, его полное надразбиение.

22^*. Напишите программу для построения по ориентированному графу, представленному с помощью ассоциативного списка инцидентности, его полное надразбиение.

2. Представление графов с помощью ассоциативных списков инцидентности

1^*. Напишите функцию для определения количества рёбер в неориентированном графе, представленном ассоциативным списком инцидентности.

2^*. Напишите функцию, добавляющую к заданному неориентированному графу ребро, соединяющее две заданные вершины.

3^*. Напишите функцию для определения количества дуг в ориентированном графе, представленном ассоциативным списком инцидентности.

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

5^*. Напишите функцию для определения в данном ориентированном графе, представленном ассоциативным списком инцидентности, вершин, из которых не исходит ни одна дуга.

6^*. Напишите функцию для определения в данном неориентированном графе, представленном ассоциативным списком инцидентности, количества рёбер, инцидентных некоторой вершине (степень вершины).

7^*. Напишите функцию для определения в данном ориентированном графе, представленном ассоциативным списком инцидентности, количества дуг, инцидентных некоторой вершине (степень вершины).

8^*. Напишите функцию для проверки, является ли неориентированный граф, заданный ассоциативным списком инцидентности, однородным.

9^*. Напишите программу, определяющую какой из двух неориентированных графов, заданных ассоциативными списками инцидентности, имеет большее число рёбер.

10^*. Напишите программу, определяющую какой из двух ориентированных графов, заданных ассоциативными списками инцидентности, имеет большее число дуг.

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

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

13^*. Напишите программу, удаляющую из неориентированного графа, заданного ассоциативного списка инцидентности, все изолированные вершины.

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

15^*. Напишите программу для определения, является ли граф, представленный ассоциативным списком инцидентности, G-графом.

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

17^*. Проверьте на нескольких неориентированных графах, представленных ассоциативными списками инцидентности, утверждение теоремы, утверждающей, что число нечётных вершин любого графа чётно.

18^*. Напишите программу, определяющую количество путей длины 3 из i-ой вершины в j-ю вершину заданного неориентированного графа, представленного ассоциативным списком инцидентности.

19^*. Напишите программу для преобразования представления заданного неориентированного графа в виде ассоциативного списка инцидентности, в представление в виде матрицы смежности.

20^*. Напишите программу для преобразования представления заданного неориентированного графа в виде матрицы смежности в представление в виде ассоциативного списка инцидентности.

21^*. Напишите программу для построения по неориентированному графу, представленному с помощью ассоциативного списка инцидентности, его полное надразбиение.

Со следующего шага мы начнем рассматривать реализацию алгоритмов на графах.

Предыдущий шаг Содержание Следующий шаг