![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Если ребра не имеют ориентации, то граф называется неориентированным (неориентированный дубликат или неориентированный двойник). В случае когда 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 - конец дуги
Из двух определений мы увидели, что графы бывают двух типов - неориентированные и ориентированные. В нашем курсе мы будем в основном заниматься ориентированными графами.
Для удобства вместо термина "ориентированный граф" будем употреблять термин граф(такое упрощение допускается во многих книгах).
Отметим, что из определения вытекает, что в графе не может быть петель, т.е. ребер, соединяющих вершины сами с собой.
Дата публикования: 2014-11-04; Прочитано: 520 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!