Неориентированные графы

Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно (иначе говоря, ребро --- это пара вершин). Если две вершины, связанные между собой ребром, равноправны, то  графы называются неориентированными: нет никакой разницы между "началом" и "концом" ребра.

Ориентированные графы

Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. На рисунках дуги изображаются стрелочками.

В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги ( дуга из нее исходит ), вторая - концом дуги ( дуга в неё  входит ). Можно сказать, что любое ребро - это пара дуг, направленных навстречу друг другу.

Способы представления графов:

Первый способ: массив ребер.

Пусть в графе M ребер. Заведем массив размером Mx2, в котором будем хранить ребра парами вершин, которые они соединяют. Это наиболее понятный, но достаточно неудобный способ хранения графа. Однако у него есть один большой плюс - при таком способе представления легко вводить дополнительные характеристики ребер. Например, чтобы сохранить веса ребер, достаточно сделать массив размером Mx3 и в дополнительную ячейку для каждого ребра записать его вес.

Второй способ: матрица смежности.

Матрица смежности Sm - это квадратная матрица размером NxN ( N - количество вершин в графе ), заполненная единицами и нулями по следующему правилу:

Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = 1, в противном случае Sm[u,v] = 0. Аналогично, если граф имеет кратные ребра, то в элемент Sm[u,v] запишем количество ребер из вершины u в вершину v.

Заметим, что данное определение подходит как ориентированным, так и неориентированным графам: матрица смежности для неориентированного графа будет симметричной относительно своей главной диагонали, а для орграфа - несимметричной.

Задать взвешенный граф при помощи матрицы смежности тоже возможно. Необходимо лишь внести небольшое изменение в определение:

Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = ves(e), в противном случае Sm[u,v] = 0.

В матрице смежности графа без петель на главной диагонали стоят 0.

Третий способ: списки смежности.

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

УКАЗАНИЕ: Для работы со списками в DELPHI используйте указатели или класс TLIST. В С++ используйте указатели или класс VECTOR.

ЗАДАЧИ.

1. По матрице смежности построить списки смежности неориентированного графа и подсчитать степени его вершин.

2. По массиву рёбер построить списки смежности ориентированного графа и подсчитать полустепени исхода его вершин.

3. По матрице смежности построить списки смежности ориентированного графа и подсчитать полустепени захода его вершин.

4. По массиву рёбер построить списки смежности неориентированного графа и подсчитать степени его вершин.

5.  По массиву рёбер построить списки смежности неориентированного графа, записи в каждом списке упорядочить по убыванию номеров вершин.

7. По матрице смежности построить списки смежности ориентированного графа, записи в каждом списке упорядочить по убыванию номеров вершин.

9. По матрице смежности построить списки смежности неориентированного графа, удалить из графа все рёбра, начинающиеся и заканчивающиеся в вершинах n₁, n₂, n₃.

10. По таблице рёбер построить списки смежности ориентированного графа, добавить рёбра с началом в вершинах с номерами, кратными 2, и концом в вершинах с номерами, кратными 3.

11. По массиву рёбер построить списки смежности ориентированного графа, удалить из графа вершины с номерами n₁ и n₂.

12. По массиву рёбер построить списки смежности ориентированного графа, удалить из графа рёбра, оканчивающиеся в вершинах n₁ и n₂.

12. По матрице смежности построить списки смежности ориентированного графа, добавить рёбра с началом в вершинах n₁, n₂  и концом в вершинах n₃, n₄.

13. По массиву рёбер построить списки смежности неориентированного графа, удалить из графа все рёбра, обе вершины которых кратны 3.

14. По массиву рёбер построить списки смежности ориентированного графа и найти все вершины, которые являются его истоками, и все его вершины, которые являются его стоками.

15. По массиву рёбер построить списки инцидентности ориентированного графа, записи в каждом списке упорядочить по возрастанию номеров вершин.

16. По матрице смежности построить списки инцидентности неориентированного графа, записи в каждом списке упорядочить по возрастанию номеров вершин.