16. Изоморфизм графов. Примеры.

Графы Г1=(V1,E1) и Г2=(V2,E2) называются изоморфными, если существует взаимно однозначное соответствие f:V1→V2, переводящие дуги в дуги, т.е. такое, что (a,b) принадл. Е1 тогда и только тогда, когда (f(a), f(b)) принадл. Е2.

Отсюда следует, что у изоморфных графов поровну дуг. Обратное неверно: для этого изоморфизма не достаточно.

Примеры применения изоморфизма – разные изображения графа К₃₃, известная задача о шахматных конях на доске 3*3.

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

17. Представление графа. Матрицы смежности и инцидентности ориентированного и неориентированного графов. Примеры. Смысл элемента п-й степени матрицы смежности.

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

Матрица Смежности S(Г).

Это квадратная матрица размером p*p (p - число вершин). Для ее построения надо занумеровать вершины. Матрица S(Г) – булева (элементы 0 или 1). S(Г)_у = 1 тогда, когда в графе существует дуга (а_i, a_j). Т.о. каждой дуге графа соответствует 1 в матрице смежности и наоборот, на главной диагонали расположены 0. Матрица смежности для неориентированного графа симметрическая.

Матрица инцидентности I(Г).

Размеры этой матрицы q*p. Для ее построения необходимо занумеровать и вершины, и дуги.В каждой строке матрицы для ориентированного графа присутствуют один элемент -1, один элемент 1, остальные 0. Для неориентированного графа – две единицы, остальные нули. I(Г)_y= -1, если i-я дуга исходит из j-той вершины (в случае, когда I(Г)_y= 1 наоборот).

Элемент n-й степени матрицы смежности.

Элемент Sⁿ(Г)_у n-й степени матрицы S(Г) равен числу маршрутов длины n, соединяющих i-ю вершину графа с j-й.

18. Полный граф. Пустой граф. Дополнение графа. Двудольный граф. Полный двудольный граф. Планарный граф. Однородный граф. Подграф. Частичный граф. Примеры.

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

А) Б)

Б)Пустой граф ( дерево) - это граф с пустым множеством вершин.

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

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

1. 2. 3.

2.Полный двудольный граф- двудольный граф, у которого любые две вершины, входящие в разные доли, смежны.

3.Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.

Однородный граф - это граф, у которого все вершины имеют одинаковую степень.

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

Частичный граф исходного графа — граф, содержащий все вершины исходного графа и подмножество его рёбер.