на главнуюВсе эхи RU.ALGORITHMS
войти ?

Re: О представлении графа в базе данных

От Alex Mizrahi (2:5020/400) к Kalachihin Vladimir

В ответ на Заголовок предыдущего сообщения в треде (Имя Автора)


From: "Alex Mizrahi" <udodenko@users.sourceforge.net>

Hу тут неплохо вспомнить определение, например, из википедии (прости,
господи):
----

Граф или неориентированный граф G - это упорядоченная пара G: = (V,E), для
которой выполнены следующие условия:

V это непустое множество вершин или узлов,
E это множество пар (в случае неориентированного графа - неупорядоченных)
вершин, называемых рёбрами.

Ориентированный граф (сокращённо орграф) G - это упорядоченная пара G: =
(V,A), для которой выполнены следующие условия:
V это непустое множество вершин или узлов,
A это множество (упорядоченных) пар различных вершин, называемых дугами или
ориентированными рёбрами.
----

Hа практике неориентированные графы можно считать частным случаем
ориентированных:
если граф G неориентированный, то для каждого ребра A->B существует также и
ребро B->A.

Как ты правильно заметил, ориентированный граф соответствует некоему
отношению, т.к. отношение как раз и есть множество упорядоченных пар.
Тогда неориентированный граф можно сопоставить симметричному отношению, т.е.
такому отношению, в котором наличие пары <A,B> означает тажке и наличие
<B,A>.

KV> парой. В теории обе половины пары равноправны, и возможен запрос типа
KV> "сколько рёбер проходит через вершину A?".

В случае ориентированного графа нужно отдельно рассматривать количество
рёбер выходящих из вершины и количество рёбер, входящих в неё.

KV> иначе?) обе половины, очевидно, не равноправны, и предыдущий простой
KV> вопрос распадается на два независимых запроса к этому отношению.

Hу тут дело в том, что этот "простой вопрос" вообще не имеет смысл для
орграфов.

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

KV> Более того, представление ненаправленного графа становится вообще
KV> невозможным,

А если подумать -- возможным.

KV> Поэтому на практике отношение Предок, Потомок вида A,B рассматривают
KV> либо как "Объект A, имеющий потомка B", либо как "Объект B, имеющий
KV> предка A".

Hу это ты уже в какую-то не ту степь ушёл. В теории графов нет объектов,
предков и потомков. Есть вершины и рёбра/дуги.

KV> Так вопрос - а как правильно?

Честно говоря, не вижу разницы.
Коль уж речь о базах данных, покажи в виде SQL.

Кроме того мне не понятно, с ориентированными графами ты хочешь работать или
с неориентированными. С обоими сразу?

KV> Моя практика показывает, что представлять
KV> узлы дерева, как объекты, имеющие предка - радикально удобней, чем как
KV> объекты, имеющие потомка. В одной известной мне предметной области,
KV> которая точно никогда не заморачивалась такими вопросами, все связи
KV> строятся именно как указание предка, а не потомка.
KV> Hалицо ассиметрия. Этому есть какое-нибудь объективное обоснование, или
KV> это мои личные глюки?

Тут неплохо бы привести пример, честно говоря не понимаю о чём ты...

--- ifmail v.2.15dev5.4
* Origin: Demos online service (2:5020/400)

Ответы на это письмо:

From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку

From: Username
Или коротким

FGHI-url этого письма: area://RU.ALGORITHMS?msgid=<1187408869@killer>+f56ba153