Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

Утверждение. Изоморфизм графов (орграфов) является отношением эквивалентности на множестве графов (орграфов).
Определение. Операцией подразбиения дуги (u,v) в орграфе D=(V,X) называется операция, которая состоит в удалении из X дуги (u,v), добавлении к V новой вершины w и добавлении к X\{(u,v)}, двух дуг (u,w) и (w,v).
Аналогично для ребер графа.
Определение. Орграф D₂ называется подразбиением орграфа D₁ если D₂ получается из D₁ путем последовательного применения операции подразбиения дуг.
Пример.

D₂



D₁



Определение. Орграфы (графы ) называются гомеоморфными, если их подразбиения, которые являются изоморфными.
Определение. Если степени всех вершин графа = k, то граф наз. регулярным степени k. (см. Рисунок выше).
Граф, состоящий из 1 вершины, называется тривиальным.
Двудольным называется граф G(V,X), такой, что множество вершин V разбито на 2 подмножества V₁ и V₂ (V₁V₂=V, V₁V₂=), причем каждое ребро инцидентно вершине из V₁ и V₂.
Матрицы смежности и инцидентности
Пусть D=(V,X) орграф, V={v₁,...,v_n}, X={x₁,...,x_m}.
Матрицей смежности орграфа D называется квадратная матрица
A(D)=[a_ij] порядка n, где

Матрицей инцидентности называется матрица B(D)=[b_ij] порядка nm, где

Для неориентированных графов G=(V,X)
Матрицей смежности графа G называется квадратная симметричная матрица A(G)=[a_ij] порядка n, где

Матрицей инцидентности графа G называется матрица B(G)=[b_ij] порядка nm, где

Примеры.
1. Для орграфа, изображенного на Рисунок

2. Для графа, изображенного на Рисунок

,

Ориентированный псевдограф

D

С помощью этих матриц графы задаются на ЭВМ.

Свойства матриц смежности и инцидентности.

Для ориентированного мультиграфа D=(V,X), V={v₁,...,v_n}, X={x₁,...,x_m}

- сумма строк матрицы B(D) является нулевой строкой (дуга один раз входит и один раз выходит);
- любая строка матрицы B(D) является линейной комбинацией остальных строк (вследствие предыдущего);
- ранг матрицы B(D) не превосходит n(D)-1 (также вследствие предыдущего);
- для любого контура в D сумма столбцов матрицы B(D), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.

Для неориентированного мультиграфа G=(V,X), V={v₁,...,v_n}, X={x₁,...,x_m}

- сумма строк матрицы B(G) по модулю 2 является нулевой строкой (дуга один раз входит и один раз выходит, а вместе четно);
- любая строка матрицы B(G) является суммой по модулю 2 остальных строк (вследствие предыдущего);
- для любого цикла в G сумма по модулю 2 столбцов матрицы B(G), соответствующих ребрам, входящим в этот цикл, равна нулевому столбцу.