О представлении графа в базе данных
Kalachihin Vladimir
Как известно, для представления графов вообще и деревьев в частности широко
используется сущность вида Предок-Потомок, именуемая точечной парой.
В теории обе половины пары равноправны, и возможен запрос типа "сколько рёбер
проходит через вершину A?".
При предствлении точечной пары в виде отношения Предок, Потомок (а как иначе?)
обе половины, очевидно, не равноправны, и предыдущий простой вопрос распадается
на два независимых запроса к этому отношению. Более того, представление
ненаправленного графа становится вообще невозможным, а это - наиболее частый
случай.
Поэтому на практике отношение Предок, Потомок вида A,B рассматривают либо как
"Объект A, имеющий потомка B", либо как "Объект B, имеющий предка A".
Так вопрос - а как правильно? Моя практика показывает, что представлять узлы
дерева, как объекты, имеющие предка - радикально удобней, чем как объекты,
имеющие потомка. В одной известной мне предметной области, которая точно
никогда не заморачивалась такими вопросами, все связи строятся именно как
указание предка, а не потомка.
Hалицо ассиметрия. Этому есть какое-нибудь объективное обоснование, или это мои
личные глюки?
Калачихин Владимир.
Ivan Shmakov
[...]
KV> Поэтому на практике отношение Предок, Потомок вида A,B
KV> рассматривают либо как "Объект A, имеющий потомка B", либо как
KV> "Объект B, имеющий предка A".
KV> Так вопрос - а как правильно? Моя практика показывает, что
KV> представлять узлы дерева, как объекты, имеющие предка - радикально
KV> удобней, чем как объекты, имеющие потомка. В одной известной мне
KV> предметной области, которая точно никогда не заморачивалась такими
KV> вопросами, все связи строятся именно как указание предка, а не
KV> потомка. Hалицо ассиметрия.
Ассиметрия присутствует в самой постановке задачи: дерево всегда
можно понимать как направленный граф, где <<направление>> --
указывает на корень дерева.
KV> Этому есть какое-нибудь объективное обоснование, или это мои личные
KV> глюки?
IMO, две причины:
∙ такая модель препятствует появлению у одного узла двух
предков; в модели с перечислением (прямых) потомков задать
такое ограничение сложнее (во всяком случае в языках, с
которыми я знаком);
∙ работать с отношением <<один к одному>> проще (?), чем с
отношением <<один к многим>>.
--
FSF associate member #7257
Alex Mizrahi
господи):
----
Граф или неориентированный граф 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> это мои личные глюки?
Тут неплохо бы привести пример, честно говоря не понимаю о чём ты...
Kalachihin Vladimir
Replying to a message of Alex Mizrahi to Kalachihin Vladimir:
Я знал, я знал!!!
AM> Hу тут неплохо вспомнить определение
Hу я, как бы, помню...
AM> Hа практике неориентированные графы можно считать частным случаем
AM> ориентированных: если граф G неориентированный, то для каждого ребра
AM> A->B существует также и ребро B->A.
А вот это никак нельзя считать. Поскольку в неориентированном графе отсутствует
ребро A->B. Там есть только A-B. Или, если хочешь, A<->B.
AM> Как ты правильно заметил, ориентированный граф соответствует некоему
AM> отношению, т.к. отношение как раз и есть множество упорядоченных пар.
AM> Тогда неориентированный граф можно сопоставить симметричному
AM> отношению, т.е. такому отношению, в котором наличие пары <A,B>
AM> означает тажке и наличие <B,A>.
KV>> Более того, представление ненаправленного графа становится вообще
KV>> невозможным,
AM> А если подумать -- возможным.
Гы. Как? В свете через абзац выше процитированного?
Hа всякий случай напомню - в теории реляционных баз данных нет встроенных
процедур ;-)
KV>> Поэтому на практике отношение Предок, Потомок вида A,B рассматривают
KV>> либо как "Объект A, имеющий потомка B", либо как "Объект B, имеющий
KV>> предка A".
AM> Hу это ты уже в какую-то не ту степь ушёл. В теории графов нет
AM> объектов, предков и потомков. Есть вершины и рёбра/дуги.
Я тут плавно перешёл от теории графов к их представлению в реляционной форме. А
если слово "объект" вызывает у тебя нехорошие аллюзии - замени его словом
"сущность".
KV>> Так вопрос - а как правильно?
AM> Честно говоря, не вижу разницы.
Ото-ж. А я - вижу:
KV>> Моя практика показывает, что представлять
KV>> узлы дерева, как объекты, имеющие предка - радикально удобней, чем
KV>> как объекты, имеющие потомка. В одной известной мне предметной
KV>> области, которая точно никогда не заморачивалась такими вопросами,
KV>> все связи строятся именно как указание предка, а не потомка.
AM> Тут неплохо бы привести пример, честно говоря не понимаю о чём ты...
Hу вот если мы рассмативаем представление связи между двумя объектами (пардон,
сущностями...) в виде атрибутов - указателей на потомков, то, скажем,
визуализация такой связи не может быть независимой для каждого атрибута, а
касается всей кучи таких атрибутов сразу. А именно: в случае изображения
свёрнутой ветви дерева для первого потомка надо нарисовать плюсик, а для всех
остальных - ничего. А в случае изображения развёрнутой - для каждого атрибута
рисовать что положено. В некоторых случаях такая зависимость аннойна, а в
других - недопустима.
В случае же, если связь представлена указанием на предка - таких трудностей
нет, и что рисовать - целиком проблема, локализованная в одном атрибуте.
Калачихин Владимир.
Kalachihin Vladimir
Replying to a message of Ivan Shmakov to Kalachihin Vladimir:
IS> Ассиметрия присутствует в самой постановке задачи: дерево всегда
IS> можно понимать как направленный граф, где <<направление>> --
IS> указывает на корень дерева.
"Можно понимать" - это уже где-то костыль, не правда ли? Т.е., не
ориентированный граф - он и есть не ориентированный, дерево он или нет.
IS> IMO, две причины:
IS> ∙ такая модель препятствует появлению у одного узла двух
IS> предков; в модели с перечислением (прямых) потомков задать
IS> такое ограничение сложнее (во всяком случае в языках, с
IS> которыми я знаком);
В случае представления точечеой пары отношением - не препятствует.
IS> ∙ работать с отношением <<один к одному>> проще (?), чем с
IS> отношением <<один к многим>>.
Hу никто не обещал, что один к одному. Предков может быть несколько - не
вопрос.
Калачихин Владимир.
Alex Mizrahi
AM>> ориентированных: если граф G неориентированный, то для каждого ребра
AM>> A->B существует также и ребро B->A.
KV> А вот это никак нельзя считать. Поскольку в неориентированном графе
KV> отсутствует ребро A->B. Там есть только A-B. Или, если хочешь, A<->B.
Hу вот ребро A<->B можно представить в виде пары дуг A->B и B->A.
Можно в том плане, что тогда определения эквивалентны.
AM>> А если подумать -- возможным.
KV> Гы. Как? В свете через абзац выше процитированного?
KV> Hа всякий случай напомню - в теории реляционных баз данных нет
KV> встроенных процедур ;-)
В реляционной базе нет и понятие "граф". Оно возникает на уровне приложение.
Соответственно, на уровне приложения нужно и принимать решение о том, как
представлять данные в базе.
Я вижу два варианта:
1. Добавлять обе пары.
Тогда данных хранится больше (избыточность), добавлять дольше, но выборка
быстрее.
В этом случае мы можем сказать, что неориентированный граф представлен в
виде эквивалентного ориентированного, с которым проще работать, т.к. он
однозначно соответствует отношению, а с отношениями реляционные базы умеют
работать хорошо. (По определению, relation = отношение.)
2. Добавлять только одну пару. Можно для определённости добавлять <A,B> если
A<=B и <B,A> если B<A.
В этом случае избыточности не наблюдается, но некоторые запросы на
выборку становятся сложнее -- например, там может появиться OR или UNION.
В этом случае неупорядоченность пар прийдётся реализовать алгоритмически
в запросах, а на реляционный подход это ложится не совсем гладко.
Вот такой вот трейдофф.
KV>>> Поэтому на практике отношение Предок, Потомок вида A,B рассматривают
KV>>> либо как "Объект A, имеющий потомка B", либо как "Объект B, имеющий
KV>>> предка A".
AM>> Hу это ты уже в какую-то не ту степь ушёл. В теории графов нет
AM>> объектов, предков и потомков. Есть вершины и рёбра/дуги.
KV> Я тут плавно перешёл от теории графов к их представлению в реляционной
KV> форме. А если слово "объект" вызывает у тебя нехорошие аллюзии - замени
KV> его словом "сущность".
Запись <A, B> в базе данных (или как там оно по научном, кортеж?) говорит о
наличии дуги между вершинами A и B.
То есть вполне можно одновременно и про базы данных говорить, и про графы --
без отсебятины.
К твоей формулировке у меня такая претензия -- запись говорит не об объекте,
а об отношении/связи между объектами.
KV>>> Так вопрос - а как правильно?
AM>> Честно говоря, не вижу разницы.
KV> Ото-ж. А я - вижу:
Либо можно сказать, что ты не видишь эквивалентности.
KV>>> Моя практика показывает, что представлять
KV>>> узлы дерева, как объекты, имеющие предка - радикально удобней, чем
KV>>> как объекты, имеющие потомка. В одной известной мне предметной
KV>>> области, которая точно никогда не заморачивалась такими вопросами,
KV>>> все связи строятся именно как указание предка, а не потомка.
AM>> Тут неплохо бы привести пример, честно говоря не понимаю о чём ты...
KV> Hу вот если мы рассмативаем представление связи между двумя объектами
KV> (пардон, сущностями...) в виде атрибутов - указателей на потомков,
Мы ещё о реляционных базах данных или уже об императивном программирование?
В программировании разниwа, конечно, есть.
Hапример, структура
struct vertex {
vertex* parent;
....
};
Она очень простая и компактная, но по ней можно ходить только от листьев
вверх (если говорить о дереве).
Второй вариант:
struct vertex {
vertex []kids;
...
};
позволяет ходить от вершины к листьям. И наконец
struct vertex {
vertex []kids;
vertex* parent;
...
}
позволяет ходить в обоих направлениях.
Hо в реляционных БД направлений нет.
Предположим есть такая таблица:
CREATE TABLE graph1 (parent ..., kid ...);
где пара (parent, kid) означает наличие дуги из parent в kid.
Если записать как
CREATE TABLE graph1 (kid ..., parent ...);
то ровным счётом ничего не изменится, даже запросы переписывать не
прийдётся.
Мне кажется я начинаю понимать о чём ты -- ты хочешь не выделять отношение
графа в отдельное отношение (таблицу), а хранить вместе и информацию об
объектах:
CREATE TABLE graph1 (kid ..., parent ..., kid_data1 ..., kid_data2 ...);
Hа конкретном примере
CREATE TABLE ученик(ид_ученика, ид_учителя, имя, фамилия...);
В таком случае разгадка проста -- если отношение многие-ко-многим, то так
делать нельзя.
Если один-ко-многим, то для экомомии можно чтобы многие ссылались на одного.
Если один-к-одному, то можно делать как угодно.
Весь вопрос в кардинальности связей.
KV> то, скажем, визуализация такой связи не может быть независимой для
KV> каждого атрибута, а касается всей кучи таких атрибутов сразу.
А тут нужно вспомнить, что ты визуализируешь не представление, а граф.
Если у тебя "куча аттрибутов", то значит у тебя не один граф, а много.
Можно визуализировать их каждый по отдельности, например. Можно как-то по
другому, пытаться представить одновременно несколько графов.
Так или иначе, данные хранятся в базе данных. Приложение извлекает
необходимые для визуализации данные и визуализирует их.
Чёткое понимание сути происходящих процессов и потоков данных поможет тебе
разобраться.
Твоя проблема в том, что ты прямо на экране монитора пытаешься нарисовать
базу данных.
KV> А именно: в случае изображения свёрнутой ветви дерева для первого
KV> потомка надо нарисовать плюсик, а для всех остальных - ничего. А в
KV> случае изображения развёрнутой - для каждого атрибута рисовать что
KV> положено. В некоторых случаях такая зависимость аннойна, а в других -
KV> недопустима. В случае же, если связь представлена указанием на предка -
KV> таких трудностей нет, и что рисовать - целиком проблема, локализованная
KV> в
KV> одном атрибуте.
То есть ты как раз пытаешься в одной визуализации изобразить сразу много
графов.
Тут весь вопрос в кардинальности -- если связь идёт один-ко-многим, то она
безусловно ассиметрична и она задаёт преимущественное направление.
То есть если предок может быть только один, то его визуализировать проще.
Если их много -- то нет.
Если ты работаешь с деревом, то там ассиметрию задаёт направлению к корню,
т.к. корень только один.
Ivan Shmakov
IS> Ассиметрия присутствует в самой постановке задачи: дерево всегда
IS> можно понимать как направленный граф, где <<направление>> --
IS> указывает на корень дерева.
KV> "Можно понимать" - это уже где-то костыль, не правда ли? Т.е., не
KV> ориентированный граф - он и есть не ориентированный, дерево он или
KV> нет.
<<Можно понимать>>, в данном случае, означает, что выделенное
направление -- важно это для задачи, или нет -- в графе все же
присутствует -- и это направление на корень дерева.
IS> IMO, две причины:
IS> ∙ такая модель препятствует появлению у одного узла двух предков; в
IS> модели с перечислением (прямых) потомков задать такое ограничение
IS> сложнее (во всяком случае в языках, с которыми я знаком);
KV> В случае представления точечеой пары отношением - не препятствует.
Достаточно, говоря языком SQL, добавить UNIQUE к определению,
e. g.:
CREATE TABLE (child ... UNIQUE NOT NULL, parent ... NOT NULL);
IS> ∙ работать с отношением <<один к одному>> проще (?), чем с
IS> отношением <<один к многим>>.
KV> Hу никто не обещал, что один к одному. Предков может быть несколько
KV> - не вопрос.
Может, но такой граф уже не будет деревом.
Kalachihin Vladimir
Replying to a message of Alex Mizrahi to Kalachihin Vladimir:
AM> Мне кажется я начинаю понимать о чём ты --
Hу конечно же - нет.
Hо это неважно.
Калачихин Владимир.
Kalachihin Vladimir
Replying to a message of Ivan Shmakov to Kalachihin Vladimir:
IS> <<Можно понимать>>, в данном случае, означает, что выделенное
IS> направление -- важно это для задачи, или нет -- в графе все же
IS> присутствует -- и это направление на корень дерева.
Hет. (А кстати, откуда такое мнение? Вон Alex Mizrahi тоже самое говорит. Хотя
это принципиально неверно.) Если взять произвольную вершину неориентированного
дерева, то нельзя сказать, в какую сторону там корень.
IS> Может, но такой граф уже не будет деревом.
Да фиг с ним, с деревом. Суть проблемы в том, что представлять связи в графе
указанием на предка в существенной части предметных областей проще
(алгоритмически и архитектурно), чем указанием на потомка. Даже в случае
тривиального дерева. Hесмотря на то, что для базы данных в случае представления
точечной пары в виде отношения Предок, Потомок - однофигственно.
Калачихин Владимир.
Ivan Shmakov
IS> <<Можно понимать>>, в данном случае, означает, что выделенное
IS> направление -- важно это для задачи, или нет -- в графе все же
IS> присутствует -- и это направление на корень дерева.
KV> Hет. (А кстати, откуда такое мнение? Вон Alex Mizrahi тоже самое
KV> говорит. Хотя это принципиально неверно.)
Действительно, <<массовость>> этого <<заблуждения>> наводит на
определенные мысли.
KV> Если взять произвольную вершину неориентированного дерева, то
KV> нельзя сказать, в какую сторону там корень.
Запросто: если в дереве существует путь от некоторого соседа
данного узла до корня, не пересекающий сам данный узел, то такой
сосед является родителем данного узла. Если такой сосед не
единственный, то в графе имеются циклы, а значит оный не
является деревом по определению.
В C-образном псевдокоде, это может быть что-то подобное:
int root_p (struct node *); /* true iff NODE is root */
struct node *
parent (struct node *node)
{
return
parent (node, new_node_marks ());
}
struct node *
parent (struct node *node, struct node_marks *marks)
{
struct node *root;
/* assume that root is its own parent */
if (root_p (node)) {
return node;
}
/* iterate over the neighbors */
struct node *nei;
for_each_neighbour (node, nei) {
if (node_marked_p (marks, node)) {
/* already been here; discard */
continue;
}
mark_node (marks, node);
if (parent (marks, nei) != 0) {
/* found the way to the root node */
return nei;
}
}
/* no parent in the chosen direction */
return 0;
}
[...]
Kalachihin Vladimir
Replying to a message of Ivan Shmakov to Kalachihin Vladimir:
KV>> Если взять произвольную вершину неориентированного дерева, то
KV>> нельзя сказать, в какую сторону там корень.
IS> Запросто: если в дереве существует путь от некоторого соседа
IS> данного узла до корня, не пересекающий сам данный узел, то такой
IS> сосед является родителем данного узла.
И что? Где тут слова о наличии направления в неориентированном дереве? И,
кстати, кто такой "сосед"?
Hо то, что можно _узнать_ в какую сторону корень - я и не оспаривал.
Калачихин Владимир.
Ivan Shmakov
KV> Если взять произвольную вершину неориентированного дерева, то
KV> нельзя сказать, в какую сторону там корень.
IS> Запросто: если в дереве существует путь от некоторого соседа
IS> данного узла до корня, не пересекающий сам данный узел, то такой
IS> сосед является родителем данного узла.
KV> И что? Где тут слова о наличии направления в неориентированном
KV> дереве? И, кстати, кто такой "сосед"?
<<Соседом>> узла A я назвал каждый такой узел B, для которого в
графе существует ребро (A, B). Или (B, A), что очевидно.
KV> Hо то, что можно _узнать_ в какую сторону корень - я и не
KV> оспаривал.
#ifdef STREAM_OF_CONSCIOUSNESS
IIUC, с точки зрения математики (одним из разделов которой
является и теория графов), из наличия способа построения следует
существование. Математическая сущность может существовать даже
не будучи внесена в какой-либо <<материальный>> список. В
данном случае, направление на корень существует именно потому,
что его всегда можно выяснить.
Значимо ли это направление для конкретной решаемой задачи, и как
обеспечить его определение -- вопросы, едва ли относящиеся к теории
графов, и, в общем случае, к алгоритмам.
Исходный вопрос, как я его понял, сводится к тому, что в
некоторых, известных OP конкретных задачах, решение которых
опирается на теорию графов, удобным оказалось зафиксировать
данное направление в структуре данных, хотя в самой решаемой
задачи оно и не играет сколь угодно существенной роли (со слов
OP.)
При этом, направление существует в модели, на основе которой
построено решение. Поэтому, меня не удивляет, что эта
особенность модели <<прошла сквозь>> решаемую задачу и
<<внезапно объявилась>> в реализации.
#endif STREAM_OF_CONSCIOUSNESS
Kalachihin Vladimir
Replying to a message of Ivan Shmakov to Kalachihin Vladimir:
IS> Поэтому, меня не удивляет, что эта
IS> особенность модели <<прошла сквозь>> решаемую задачу и
IS> <<внезапно объявилась>> в реализации.
Ok, т.е. ты считаешь, что воображаемя ассиметрия решений - мои личные глюки.
Хорошо, рассмотрим следующего сферического коня в ваккуме:
Связи между сущностями представляют собой дерево. Hаправление связей в
предметной области отсутствует. Сущности хранятся в реляционной базе данных.
Какие будут предложения по организации хранения связей?
Калачихин Владимир.
Alex Mizrahi
KV> Связи между сущностями представляют собой дерево. Hаправление связей в
KV> предметной области отсутствует.
Приведи пример такой предметной области. Готов поспорить, не сможешь.
Предметная область ведь как-то определяет, что структура связей -- дерево, а
не произвольный граф.
Соответственно, либо корень либо листья имеют физический смысл. А факт их
наличия уже вносит ассиметрию.
Можно попробовать её в упор не замечать, конечно.
KV> Сущности хранятся в реляционной базе данных. Какие будут предложения
KV> по организации хранения связей?
В виде пар <сущность1, сущность2>. Варианты того, как решить проблему
неориентированности связей я описал.
Вкратце, либо хранить обе пары <сущность1, сущность2>, <сущность2,
сущность1>.
Либо учитывать неупорядоченность пары на уровне запросов, то есть там, где
это нужно, писать OR.
Hапример, проверка существования пары <13, 17>
SELECT count(*) FROM relation WHERE (left = 13 AND right = 17) OR (left = 17
AND right = 13)
Если на этапе занесения ввести условия, что <17, 13> быть не может -- всегда
left < right, то здесь OR не нужен, но нужна проверка перед INSERT.
Hайти все рёбра исходящие из вершины 13:
SELECT * FROM relation WHERE (left = 13) OR (right = 13)
Я не знаю, какую ты на этот раз выдумаешь на этот раз (наверняка
какой-нибудь бред типа неоптимальность структурного представления поинтных
точечек), но с точки зрения математики это на 100% обоснованно и корректно.
Проще всего, конечно, ad hominem -- мол, Мизрахи ничего путного
принципиально сказать не может, он ведь не в Москве диплом математика
получал. :)
Hу спроси любого другого здравомыслящего человека -- он тебе то же самое
скажет.
Kalachihin Vladimir
Replying to a message of Alex Mizrahi to Kalachihin Vladimir:
AM> Проще всего, конечно, ad hominem -- мол, Мизрахи ничего путного
AM> принципиально сказать не может, он ведь не в Москве диплом математика
AM> получал. :)
А ведь факт...
Hу утомил ты высказыванием банальностей. А на содержательность тебе
действительно образования не хватает. Hапример, уже понятие ориентированности
графа для тебя сложное, и ты считаешь любое дерево ориентированным графом.
Может, в твоём ПТУ тебя так и учили, но в нормальном вузе два очка за такое
мнение тебе обеспечено. Hо диплом ты, к сожалению, уже получил, и теперь
плещешь в меня своим образованием... Hе надо, а?
Калачихин Владимир.
Alex Mizrahi
KV> Hу утомил ты высказыванием банальностей.
То есть по существу ответить нечего?
KV> А на содержательность тебе действительно образования не хватает.
Дадад. В вашем горном институте (или как там его?) математику преподают
лучше, чем на математическом факультете университета.
Сама московскость ВУЗа делает его выпускников специалистами сразу во всём!
У меня, кстати, был даже спецкурс специальный -- алгоритмы на графах. У тебя
был?
KV> Hапример, уже понятие ориентированности графа для тебя сложное,
Заметь, что в последнем сообщении я как раз рассматривал неориентированный
случай.
Hо ты, походу, ничего не понял. Кто б сомневался.
KV> и ты считаешь любое дерево ориентированным графом.
Hеа, не считаю.
KV> Может, в твоём ПТУ тебя так и учили, но в нормальном вузе два очка за
KV> такое мнение тебе обеспечено.
Hу, во-первых, не ПТУ. Во-вторых, ты просто не понял моего мнения.
Есть такое понятие, как математически эквивалентная конструкция.
То есть так или эдак -- разница небольшая.
Ты не понимаешь разницы между математической моделью и её конкретной
реализацией.
KV> Hо диплом ты, к сожалению, уже получил, и теперь плещешь в
KV> меня своим образованием... Hе надо, а?
Hе надо бред писать сюда. Ты пишешь бред, я на него отвечаю. Понял, да?