Неориентированный граф

Если ребра не имеют ориентации, то граф называется неориентированным (неориентированный дубликат или неориентированный двойник). В случае когда G = (X, А) является ориентированным графом и не учитывается направленность дуг из множества А, то неориентированный граф, соответствующий G, обозначается как .

Пример. (рис. б)

Ориентированным графом или орграфом называется множество N = {x,y,..} вместе с множеством A = {(x,y),..}(некоторых упорядоченных пар), где множество N конечно (т.е. число его элементов конечно), а во множестве A нет элементов вида (х,х). Элементы множества N называют вершинами или узлами, элементы множества A называют дугами или ребрами. Обозначение неориентированного графа: G=(N,A)

В отличие от графа у орграфа пары (x,y) упорядочены.

N = {x,y,z,s} - вершины

A = {(sx),(sy),(xz),(xy),(yz)}

дуга (sx): s - начало дуги; x - конец дуги

дуга (yz): y - начало дуги; z - конец дуги

Из двух определений мы увидели, что графы бывают двух типов - неориентированные и ориентированные. В нашем курсе мы будем в основном заниматься ориентированными графами.

Для удобства вместо термина "ориентированный граф" будем употреблять термин граф(такое упрощение допускается во многих книгах).

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