Виды графов

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

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

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

а б в

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

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

Путь – это последовательность рёбер 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, обозначается .

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

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

---

Дата добавления: 2015-08-09