Составители:
Рубрика:
6
б) когда существенно, в каком порядке выбираются вершины, т.е. когда
пары (x
i
, x
j
) и (x
j
, x
i
) считаются различными; в этом случае пару (x
i
, x
j
)
будем называть дугой
.
Пара множеств G= ( X, U ) называется конечным графом
если имеет
место случай “ а “. В случае “ б “ пара ( X, U) называется конечным
ориентированным
графом или орграфом. Здесь U и U - множество ребер и дуг
соответственно. В случае графа говорят, что ребро (x
i
, x
j
) инцидентно
вершинам
x
i
, x
j
. В свою очередь вершины x
i
, x
j
инцидентны ребру (x
i
, x
j
).
Если граф ориентированный, то говорят, что дуга ( x
i
, x
j
) исходит из вершины
x
i
и заходит в вершину x
j
. Вершину x
i
называют при этом
предшественником
вершины x
j
, а вершину x
j
последователем вершины x
i
.
Подграфом
графа G=(X,U) называется граф G
′
= (X′,U′), такой что X′
является подмножеством множества X, а U′ подмножеством множества U.
Если при этом X′ совпадает с X, то G′ называется остовным
подграфом
графа G. Граф называется полным
, если для любых двух его вершин
существует соединяющее их ребро.
На рис. 1а изображен граф, на рис. 1б- один из его подграфов, на рис. 1в
остовной подграф этого графа. На рис. 1г приведен пример полного графа с
четырьмя вершинами.
Рис.1
Геометрическая реализация графа
Не следует путать понятие графа с его геометрической реализацией. Для
знакомства с этим понятием введем предварительно понятие геометрической
фигуры.
Под геометрической фигурой в обычном трехмерном пространстве или
на плоскости будем понимать множество точек таких, что некоторые из них
соединены отрезками линий; при этом пересечение допускается только в их
концах. Фигура называется геометрической
реализацией графа, если между
Страницы
- « первая
- ‹ предыдущая
- …
- 4
- 5
- 6
- 7
- 8
- …
- следующая ›
- последняя »
