Общие сведения о графах

Понятие графа. Виды графов

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

Граф – совокупность точек, соединенных линиями. Точки называются вершинами, или узлами, а линии – ребрами или дугами.

Рис. 43. Пример графа.

На приведённом рисунке каждая линия, соединяющая две вершины, не имеет направления, т.е. позволяет «двигаться» как от первой вершины ко второй, так и наоборот. Такие соединительные линии называются рёбрами. С помощью рёбер, к примеру, можно изобразить улицы с двусторонним движением или факт дружбы между двумя людьми.

Когда у ребра оба конца совпадают, т. е. оно выходит из вершины и входит в нее, то такое ребро называется петлей.

Граф, в котором вершины соединяются только рёбрами, называется неориентированным.

Если для соединительной линии задаётся направление, она называется дугой. Граф, в котором вершины соединяются дугами, называют ориентированным графом или орграфом.

Рис. 44. Ориентированные графы (орграфы).

Примером ориентированного графа может служить генеалогическое древо, как на рисунке слева, где дуга A₃A₁ означает, что A₃ является родителем для A₁, а не наоборот, или голосование при выборе старосты класса[38] (на рисунке справа), где направление дуги определяет, кто из двух человек за кого отдал голос. При помощи орграфов удобно представить транспортную сеть для улиц с односторонним движением, схему эскалаторов в супермаркете и т.д.

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

Также графы делятся на связные и несвязные.

В связном графе между любой парой вершин существует как минимум один путь.

В несвязном графе существует хотя бы одна вершина, не связанная с другими.

Рис. 45. Связный граф (слева) и несвязный граф (справа)

Представление графа в программе

Рассмотрим граф V с n вершинами. Его матрицей смежности называется матрица A_{n , n} такая, что

       A_{i , j} = 1, если вершина V_i соединена с V_j

       A_{i , j} = 0 в противном случае.

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

Рис. 46. (Рисунок к примеру) матрица смежности

Пример №1 (слева)