Аналитический.
Рассмотрим аналитический способ задания графа. Говорят, что задан граф, если даны множество вершин Х (обязательно непустое), множество ребер U (может быть пустым) и инцидентор F, определяющий, какую пару вершин (xi, xj) ÎX
(принадлежащих множеству Х) соединяет ребро uk ÎU.
Именно, дан граф G=(X, U; F), если даны два множества X ¹ Æ, U (XÇU=Æ) и трёхместный предикат F, удовлетворяющий следующим двум условиям:
- F определён на всех таких упорядоченных тройках элементов x, u, y, для которых x, y ÎX; uÎU;
- "u $ x, y í F(x, u, y) &"x¢,y¢ é F(x¢, u, y¢) Þ
(x=x¢ & y=y¢)Ú(x=y ¢ & y=x¢)ùý.
Очевидно, что для каждого uÎU истинно одно и только о дно из
трёх высказываний:
$ x, y½x¹y& F(x, u, y) & ØF(x, u, y) (1).
$ x, F (x, u, x) (2).
$ x, y½x¹y& F(x, u, y) & F(y, u, x) (3).
В соответствии с этим множество U разбивается на три попарно не пересекающихся подмножества рёбер - . Элементам множества истинно первое высказывание. Будем называть их дугами. При этом говорят, что дуга идёт из вершины x и входит в вершину y.
Элементам множества истинно второе высказывание. Будем называть их петлями. Если ребро u Î , то говорят: u есть петля при вершине x.
Элементам множества истинно третье высказывание. Будем называть их звеньями.
Дата добавления: 2015-09-27 | Просмотры: 374 | Нарушение авторских прав
|