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

3. Понятия смежности, инцидентности, степени
Определение. Если x={v,w} - ребро, то v и w - концы ребра x.
Определение. Если x=(v,w) - дуга орграфа, то v - начало, w – конец дуги.
Определение. Если вершина v является концом ребра x неориентированного графа (началом или концом дуги x орграфа), то v и x называются инцидентными.
Определение. Вершины v, w называются смежными, если {v,w}X.
Определение. Степенью вершины v графа G называется число (v) ребер графа G, инцидентных вершине v.
Определение. Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей
Замечание. В неориентированном псевдографе вклад каждой петли инцидентной вершине v в степень вершины v равен 2.
Определение. Полустепенью исхода (захода) вершины v орграфа D называется число ⁺(v) (^(v)) дуг орграфа D, исходящих из v (заходящих в v).
Замечание. в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в ⁺(v), так и в ^(v).
Обозначение: n(G), n(D) количество вершин графа, m(G) - количество ребер, m(D) - количество дуг.
Утверждение. Для каждого псевдографа G выполняется равенство
.
Для каждого ориентированного псевдографа

Изоморфизм, гомеоморфизм.


Определение. Графы G₁=(V₁,X₁), G₂=(V₂,X₂) называются изоморфными, если биективное (взаимно однозначное) отображение : V₁V₂, сохраняющее смежность, т.е.
{v,w}X₁  {(v), (w)}X₂ .
Определение. Орграфы D₁=(V₁,X₁) и D₂=(V₂,X₂) называются изоморфными, если биективное отображение : V₁V₂, такое, что
(v,w)X₁  ((v), (w))X₂ .
Замечание: Изоморфные графы и орграфы отличаются лишь обозначением вершин.
Свойства изоморфных графов:
1) Если изоморфны и : V₁V₂ биективное отображение, сохраняющее смежность то:
а) vV₁ (v)=((v)),
б) - количество вершин,
- количество дуг.
Аналогично, если изоморфны и : V₁V₂ биективное отображение, сохраняющее смежность то выполняется
а) vV₁ ⁺(v)=⁺((v)), ^(v)=^((v))
б)
Замечание: Для псевдографов и мультиграфов нужно сохранять кратность ребер или дуг
Примеры



Два графа изоморфны


не изоморфный первым двум, так как нет ребра между крайними вершинами.