Графическое представление графов

Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а соединяющие пары точек линии (прямолинейные либо криволинейные) – рёбрам (табл.1).

Таблица 1

Элементы графов	Геометрические элементы
1. v Î V– вершина	1. • – точка в пространстве.
2. {u,v} – ребро неориентированного графа	2. u•−•v – отрезок.
3. (v1,v2) – дуги в ориентированном графе	3. v1•→v2 – направленный отрезок.
4. {v,v} – петля	4. – замкнутый отрезок.

Виды графов

Множество рёбер Е может быть пустым (рис. 1.1). Такой граф называется нуль-графом и обозначается Ø.

рис. 1.1. Нуль-граф

Если же множество вершин V – пустое, то пустым является также множество Е. Такой граф называется пустым. Линии, которые изображают рёбра графа, могут пересекаться, но точки пересечения не являются вершинами (рис. 1.2, а); разные рёбра могут быть инцидентными одной и той же паре вершин (рис. 1.2, б), такие рёбра называются кратными. Этот случай соответствует наличию нескольких одинаковых пар (v_i,v_j) E(G). Граф, который содержит кратные рёбра, называется мультиграфом. Ребро может соединять некоторую вершину саму с собою (рис. 1.2, в), такое ребро называется петлёй. Этот случай соответствует наличию в множестве Е пар вида (v,v). Граф с петлями и кратными рёбрами называется псевдографом. Конечный неориентированный граф без петель и кратных рёбер называется обычным.

а б в

Рисунок 1.2. Графы: а) – обычный, б) – с кратными рёбрами, в) – с петлёй

Элементы графов

Путь – это последовательность рёбер e₁, e₂, …, e_m, такая, что рёбра e_i, e_i+1 имеют общую вершину. Число рёбер называется длинной пути. Если ни одна из вершин не появляется больше одного раза, то путь называется простым. Понятно, что в простом пути ни одно ребро не используется дважды.

Путь называется циклом, если его начальная вершина совпадает с конечной; простым циклом, если это не выполняется для других вершин.

Чередующаяся последовательность v₁, e₁, v₂, e₂, …, e_l,v_l+1 вершин и рёбер графа, такая, что e_i = v_iv_i+1 (i = 1, l), называется маршрутом. Если v₁ = v_l+1, то маршрут замкнутый, иначе открытый.

Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины, кроме, возможно, крайних, различны. В цепи вершины v₀ и v_k называются концами цепи. Цепь, которая соединяет вершины v_i и v_j, обозначается

Для орграфов цепь называется путём, а цикл – контуром.

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