22. Граф. Изоморфные и гомеоморфные графы. Матрица смежности и матрица инцидентности.

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

G = G(V,E)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изоморфные и гомеоморфные графы

Изоморфные графы — два графа A и B называются изоморфными, если можно установить взаимно-однозначное соответствие между их вершинами и соответствующими им рёбрами.

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

Пример:

Два графа, приведенные в примере, являются изоморфными.

Гомеоморфные графы — два графа A и B называются гомеоморфными, если один из них может быть получен из другого применением конечного (возможно нулевого) числа операций добавления и/или стирания вершин степени 2.

Пример:

В следующем примере графы G и H гомеоморфны.

Матрица смежности и матрица инцидентности

Матрица смежности — один из способов представления графа в виде матрицы.

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

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a_ii в этом случае равно удвоенному числу петель вокруг i-й вершины. Матрица смежности неориентированного графа симметрична.

Пример:

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

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

В случае ориентированного графа каждой дуге <x,y> ставится в соответствующем столбце: «−1» в строке вершины x и «1» в строке вершины y; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0».

Пример:

Строки соответствуют вершинам от 1 до 6, а столбцы — рёбрам e1–e7. Например, единицы во втором столбце во 2-й и 3-й строчках означают, что ребро e2 соединяет вершины 2 и 3.