Курсовая работа: Поиск оптимального пути в ненагруженном орграфе

Псевдограф − граф, в котором есть петли и/или кратные ребра.

Мультиграф − псевдограф без петель.

Граф − мультиграф, в котором ни одна пара не встречается более одного раза.

Граф называется ориентированным, если пары (v,w) являются упорядоченными.

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

Итак, используемые далее обозначения:

V – множество вершин;

X – множество ребер или дуг;

v (или vi)– вершина или номер вершины;

G, G0 - неориентированный граф;

D, D0 – ориентированный;

{v,w} − ребра неориентированного графа;

{v,v} – обозначение петли;

(v,w) − дуги в ориентированном графе;

v,w - вершины, x,y,z – дуги и ребра;

n(G), n(D) количество вершин графа;

m(G) - количество ребер, m(D) - количество дуг.

Примеры

1) Ориентированный граф D=(V, X), V={v1, v2, v3, v4},

X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.

Рис. 3.

2) Неориентированный граф G=(V, X), V={v1, v2, v3, v4, v5},

X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.

Рис. 4.

б) Понятия смежности, инцидентности, степени

Если x={v,w} - ребро, то v и w − концы ребер.

Если x=(v,w) - дуга ориентированного графа, то v − начало, w – конец дуги.