Ви є тут

Основные понятия теории графов, часть 2

Орграф

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

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

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

Ребра при изображении ориентированных графов представляют стрелками.

Ребро ориентированного графа называется дугой.

Если вершины  u  и  v определяют дугу, то  вершина   называется антицидентом вершины  v.

Степенью входа (выхода) вершины орграфа называется число ребер, для которых эта вершина является концом (началом).

Будем обозначать соответственно эти степени для некоторой вершины v  и .

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

Путем  v0 v1vn,  где vi   антицендент vi+1..

Контуром в ориентированном графе называют путь начинающейся и заканчивающейся в одной вершине.

Граф, в котором нет контура, называется безконтурным.


Подграфы

Подграфом графа G(VE) называется граф ¢(¢, ¢),  где  .

ПРИМЕР

 Граф ¢(¢, ¢), 

 ,

  

является подграфом  графа

  G(V,E),

V={1,2,3,4}, 

E={(1,2),(4,3),(3,4),(3,1),(4,1)}.

 

Подграф  называется остовным подграфом графа G(V,E), если .

Подграф   называется собственным подграфом граф G, если .

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer