23. Граф. Маршруты, цепи и циклы на графе. Однородные и полные графы.

Граф — это совокупность непустого множества V (вершин) и множества E пар из V (ребер).

G = G(V,E)

Конечным графом называется граф, в котором множества V и E — конечны.

Следует заметить, что большинство рассматриваевых нами графов — конечны.

Ориентированный граф (кратко орграф) — граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами.

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

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные).

Красным выделено кратное ребро (6, 2)
Синим обозначена петля (6, 6)

Граф с кратными рёбрами принято называть мультиграфом.

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

В графе ребро, концы которого совпадают, то есть e = (v,v), называется петлей.

Два ребра, имеющие общую концевую вершину, то есть e1 = (v,u1) и e2 = (v,u2), называются смежными.

Говорят, что вершина и ребро — инцидентны, если ребро содержит вершину.

Степенью вершины графа называется число рёбер, инцидентных ей.

Вершина называется изолированной, если её степень равна нулю. То есть это вершина, не являющаяся конечной ни для какого ребра.

Вершина называется листом (или висячей), если имеет степень единица.

Простым графом называется граф, в котором нет петель и кратных рёбер.

Маршруты, цепи и циклы на графе

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

Цепью называется маршрут без повторяющихся рёбер.

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

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

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

Путь (или цикл) называют простым, если рёбра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.

Однородные и полные графы

Однородный граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей.

Пример:

Простым графом называется граф, в котором нет петель и кратных рёбер.

Полный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.

Пример: