Лекция п Графы. Орграфы. Графы и орграфы. Основные понятия

Определение 7.8. Орграф G(V, E) называется связным, если его соотнесенный граф является связным. Орграф называется сильно связным, если для любой пары вершин v_i ,v_jV существует ориентированный путь из v_i в v_j.

7.3. Изоморфизм графов.

\

Определение 7.9. Функция f : G(V, E)  G₁(V₁, E₁) является изоморфизмом (обозначается GG₁), если f: VV₁ и f: E E₁ представляют собой взаимно однозначные соответствия. Если f:GG₁ – изоморфизм, то G и G₁ называются изоморфными.

Пример 7.4. Дан неориентированный помеченный граф G₁(V₁; E₁). Построить изоморфные ему графы.

Решение.


Теорема 7.1. Изоморфизм графов есть отношение эквивалентности.

Доказательство. Действительно, изоморфизм обладает всеми необходимыми свойствами отношения эквивалентности:

Рефлексивность. G  G, где требуемая биекция есть тождественная функция;

Симметричность. Если G₁  G₂ с биекцией h, то G₂  G₁ с биекцией h^{ 1};

Транзитивность. Если G₁  G₂ с биекцией h и G₂  G₃ с биекцией g, то G₁  G₃ с биекцией g  h.

■

7.4. Степень вершин.
Определение 7.10. Степенью вершины v для неориентированного графа, обозначается d(v), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей.
Определение 7.11. Полустепенью исхода вершины v для орграфа называется количество дуг, для которых v является начальной вершиной, обозначается .