10. (Теория графов. Основные понятия)

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

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

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

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

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

Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).

Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

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

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

Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).

Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

Лемма 1. Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.

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

11. (Способы задания графов)

Граф G=(V,E) можно задать списком вершин и ребер. Можно задать и геометрически, нарисовав его на плоскости или любой другой поверхности и отождествив его вершины с точками на плоскости, а ребра с отрезками, соединяющими смежные (соседние) вершины. Определение: Матрица смежности (соседства) вершин (p, q) – графа G=(V,E) с p вершинами есть квадратная симметричная матрица [p x p].

где a_ij: - 1, если вершины V_i, V_j – соседние - 0, в противном случае

Замечание: Всякому графу соответствует его бинарная симметричная матрица смежности. Всякая бинарная симметричная квадратная матрица с нулевой диагональю соответствует некоторому графу.

Определение: Матрица инциденций (соответствий) (p, q) – графа G=(V,E) с p вершинами и q ребрами есть [p x q] матрица

где B_ij: 1, если вершина V_i ∈ ребру e_j 0, в противном случае

Замечание: для всякого графа можно построить соответствующую ему бинарную матрицу инциденций.

12. (Операции над частями графов. Графы и бинарные отношения)

Операции над графами:

1) удаление вершины v из графа G приводит к подграфу G-v графа G без вершины v и принадлежащих вершине v ребер. 2) Удаление ребра e из графа G=(V,E) при сохранении вершин приводит к подграфу G-e=(V,E – {e}) 3) Добавление ребра e = (u, v) к графу G=(V,E), содержащему вершины u,v, приводит к графу G+e=(V,E∪{e})

Бинарное отношение R определяется как соотношение A R B, которое выполняется для некоторых пар элементов заданного множества V. В соответствии с этим бинарное отношение может быть представлено в виде графа с множеством вершин V, у которого ориентированное ребро (А, B) присутствует тогда и только тогда, когда выполняется отношение A R B.

Обратно, любой граф определяет бинарное отношение R на множестве своих вершин V, если наличию ребра (А, B) соответствует выполнение A R B.

Имеется, однако, небольшое различие между этими двумя понятиями. Приписывать отношению кратность обычно нет надобности. Поэтому говорить о взаимно-однозначном соответствии между бинарное отношение и графом можно лишь для графа с однократными ребрами.

Нуль-граф отвечает нулевому отношению А Æ B, которое не выполняется ни для одной пары элементов.

Полный граф U отвечает универсальному отношению А U B, которое выполняется для любой пары элементов.

Каждое отношение R имеет дополнительное отношение (или отрицание)  , которое выполняется тогда и только тогда, когда не выполняется R. Граф G( ) является дополнительным графом для G(R) по отношению к полному графу U, определенному на множестве вершин V.

G( ) = U(V) - G(R),  или U(V) = G(R) È G( ).

Для любого отношения R существует обратное отношение R*:

Соотношение B R* а выполняется тогда и только тогда, когда выполняется А R B.

Очевидно, что граф G(R*) есть обратный граф для G(R), то есть G(R) и G(R*) – это ориентированные графы с вершинами V и противоположной ориентацией ребер.

Если R* = R (т. е. A R B = A R* B), то такое отношение называется симметричным. В этом случае вершины А и B должны быть соединены ориентированными ребрами (двумя) по одному в каждом направлении. Это соответствует одному неориентированному ребру. Таким образом, симметричным отношениям соответствуют неориентированные графы.

Кроме симметрии у отношений есть свойство рефлексивности: А R а Выполняется для любых А Î V. Соответствующий граф имеет петлю в каждой вершине.

Если А R а не выполняется ни для какой А Î V, то отношение антирефлексивно, и ему соответствует граф без петель.

Если из A R B и B R с следует А R с, то отношение транзитивно. Ему соответствует граф G(R), в котором если есть ребра (A, B) и (B, С), то всегда есть и ребро (А, С), их замыкающее.

Бинарное отношение R на множестве A может иметь следующие свойства: •    рефлексивность  ∀x ∈ A, < x, x > ∈ R, •    иррефлексивность ∀x ∈ A, < x, x > ∉ R, •    симметричность ∀x, y ∈ A, < x, y > ∈ R ⇒< y, x > ∈ R, •    антисимметричность ∀x, y, < x, y > ∈ R, < y, x > ∈ R ⇒ x = y, •    транзитивность ∀x, y, z ∈ A, < x, y > ∈ R, < y, z > ∈ R ⇒< x, z > ∈ R, •    дихотомия ∀x ≠ y либо < x, y > ∈ R либо < y, x > ∈ R.