2Андрей Плахов:
2) Граф есть самая полная и универсальная структура, все прочие - суть частные случаи или структуры, которые могут быть выражены через граф. Думал ли кто-нибудь об обобщающей граф структуре? если да, то что это?

Запросто ;-) "Обычный " граф, который состоит из "элементов " и "связей " не является "универсальной структурой ", хотя бы потому, что ОТНОШЕНИЯ между элементами не обязаны исчерпываться БИНАРНЫМИ связями. "Обобщающая граф структура " должна быть, ИМХО, такой: система состоит из сущностей трех типов -
а) элементы,
б) обобщенные связи,
в) валентные-связи между элементами и "обобщенными связями ". Пункты б) и в) требуют пояснений: обобщенная связь - это как бы многоместный предикат с упорядоченным набором "валентностей ", к каждой из которых может "крепиться " ровно один элемент. Вырожденный случай "просто граф " получаем, если все обобщенные связи имеют ровно две валентности.

Но я бы думал о структуре данных, обобщающей граф, совсем по-другому. Нам ведь нужно не просто "обобщение "... Нам нужно, такое обобщение, которое по-другому организовывало бы доступ к данным. Думаю, такое обобщение - это обощение не понятия "графа ", а понятия "указателя ". Ведь именно указатели - те ребра, которые связывают вершины-данные. А обобщаются они до "адресации другими способами ". Например, до "адресации по значению " (или "адресации по части значения "). Интересно, какую еще можно придумать адресацию, кроме "по местоположению (указатель) " и "по значению (карты) "?

Андрей Плахов 21 января, 13:11
... у структуры, обобщающей граф, должны быть не только ... "ребра ", но также "грани ".
" " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " "
Да, спасибо, очень точная метафора! Вот представьте себе четыре шеста, к которым (своими углами) привязан тент ... Вот этот тент - он связывает СРАЗУ четыре элемента (=шеста)!
====================================
Egoroff 21 января, 13:13
прости, не понял... чем именованная коллекция ребер отличается от твоей валентной связи?
" " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " "
Ээээээ ... "именованная коллекция ребер " - это Вы уж даже и СТАНДАРТНОЕ понимание графа упростили ... Связи ведь там бывают а) направленные б) разнотипный, - или это все у Вас помещается внутри термина "именованная "?
------------------------------------
Я РАСЩЕПИЛ связь-как-сущность - на две сущности: валентность и обобщенную связь ... После этого валентность стала в самом деле очень похожа на "ребро ", только это ребро-то - строго моно-функционально, занимается ТОЛЬКО тем, что присоединяет элемент к обобщенной-связи (то есть, например, два элемента такое ребро связывать ну никак не может!). А вся ПРАГМАТИКА (=содержательный СМЫСЛ) связывания - поднялась на этаж выше и живет в обобщенной-связи. Кстати, обобщенной-связи - это ведь не элемент, она не может, например, сама быть ни с чем обобщенно-связана, а только (через валентности) с обслуживаемыми элементами. То есть в моей конструкции имеются ДВА принципиально различных класса элементо-подобных сущностей и - одна освобожденная-от-прагматики сущность (=валентность). НП, Иван FXS.
PS. А я в игрушки не играю :-(

2Андрей Плахов:
я все-таки искренне продолжаю не понимать... граф обычно (насколько я знаю, но могу и ошибаться) записывается (хранится) бранчами: ID1; ID2; ID3 - тройка имен (прости, Иван). Для удобства можно завести коллекцию вершин и ребер... если у нас отношения вырожденные (неименованные (прости, Иван)), то мы как раз hash_map и получим... Но я предлагаю завязать с hash_map... ибо реализация, а во-вторых, я не сильно ундерстанд в этом... замечу только, что ты с Иваном меня не убедили...

Egoroff
А, аж в таком смысле граф. Хм. ОК, я понял. В свое оправдание скажу, что говорил не о реализации, а скорее о том, что в момент реализации считается важным. Т.е. какие операции считаются самыми важными при последующей работе с этим графом. Для одних задач это "переход по заданному ребру из одного конца в другой ", и такая расстановка приоритетов рождает понятие указателя. Для других задач это "нахождение в графе ребра с заданными свойствами ", и рождаются всякие реализации вроде множеств, хэш-карт и т.п.

...Я правильно думаю, что в таком понимании реляционная БД и граф - одно и то же?...

2Андрей Плахов:
да, конечно, если считать, что таблица - это тип, а запись - экземпляр...

Сорри (ну зануда я, зануда!), но мне так нравится пример про тент, что - можно я еще раз про него выступлю: в этом примере шесты - это элемены, тент - это связь между элементами, а УЗЛЫ, которыми тент привязан к шестам - "валентности "!
НП, Иван FXS.

2Иван FXS:
не плодите сущности без необходимости... ну и что, что ты все элементы переименовал :-))) ну лечге тебе стало, и всё? :-))) (оффтопик: хорошо пиво пошло...)

Иван FXS,
речь о том, что методами реляционных БД (= графов) можно, и даже несложно, выражать множественные отношения (то есть "тент "). Поэтому введение множественных отношений не обогащает понятие графа как общего средства выражения структуры данных. По-моему, Егоров говорил об этом. Я, кстати, считаю, что не всегда "если Х выражается через У, и У у нас уже есть, значит Х нам не нужен ". По-моему Алекс склонен к такому мнению, а если так думать, можно проигнорировать много интересных концепций "за изоморфизм " уже существующим. Речь именно о расстановке акцентов. Как раз обычно если Х "выражается, но коряво ", это значит, что Х сам по себе очень даже интересен.

2Андрей Плахов:
отчасти ты прав... но вот по поводу "концепций " буду спорить... РБД - это опять реализация... если бы у нас был сетевой комп (сетевая адресация), мы бы не пользовались бы БД, а писали бы иные структуры... Здесь не должно быть нигилизма и максимализма, как правильно было замечено supremum'ом пару страниц назад... мне (в силу возраста наверное) реализация менее всего интересна... ибо я понимаю, что решение инвариантно, а реализация предметна... я уже желею, что затеял разговор о структурах, ибо мы мыслим их применение совершенно по-разному...

Андрей Плахов 21 января, 16:09
речь о том, что методами реляционных БД (= графов) можно, и даже несложно, выражать множественные отношения (то есть "тент ").
" " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " "
"методами реляционных БД ... можно " - соглашусь, но, ИМХО, у Вас ошибка в записи "БД (= графов) " ... либо же я не понимаю Вашего РАСШИРИТЕЛЬНОГО толкования слова "граф " ... Должно быть "БД <= граф ", граф может быть описан средствами РБД, но не наоборот!
---------------------------------------- -----
Классический граф (тот, который на бумаге рисуют) состоит из ДВУХ типов сущностей: "точечки " и "палочки-стрелочки ". То есть связи - строго бинарны! А когда Вы рисуете что-то типа:
Q1\_
Q2---O--Q3
И говорите, что Q1, Q2 и Q3 - это элементы, О - это связь между ними ТРЕМЯ, а палочки - это так, фигли-мигли, выдуманные Иваном сущности, то ... мое сорри, это ни в какие ворота не лезет!
НП, Иван FXS.

РБД - это, естественно, реализация. Знаком равенства я имел в виду, скорее, то, что она такое понимание графа наиболее полно реализует.
>мы мыслим их применение совершенно по-разному...
Так это мне и интересно, как его мыслит "Egoroff он же Алекс "?

Q1\_
Q2---O--Q3
или наоборот, это я говорю: О - это трехвалентная связь (тент, натянутый между тремя башнями), у меня в системе одна связь и три элемента. А Вы говорите, что О это тоже такой элемент? Тогда я отвечу, что Вы СМЕШИВАЕТЕ сущности! Например, у нас ведь может быть система:
Q1\_
Q2---O1--Q3---O2--Q4 ,
про которую ТОЧНО известно, что О1 и О2 - это СВЯЗИ! (Они, например, имеют ИДЕНТИЧНУЮ ПРИРОДУ! ...)
НП, Иван FXS.

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

Обобщением графа G({V},{(v1,v2)})
является система множеств S({V},{{vi}}), т.е. количество вершин 2 является частным случаем.

NO,
Вы с Иваном FXS, если не ошибаюсь, сказали об одном и том же?..

Или вот еще:
Ъ({V},{{vi}},{{{vi}}},...)

2Андрей:
Действительно {vi} это "тент ". Для "элементов " и "многовалентных связей " я бы сделал две соответствующие точки и связал каждую абстрактную с одной из этих двух.
2Иван:
Про Explain я как-то говорил: есть мысль (тент, валентность и т.д.) - нужно сразу ставить точку, ничего не подразумевать, все на листе.
2Егоров:
ID1,ID2 для графа достаточно если ID2 это номер ребра или валентности. Бранч (A,B,C) описывается как (A,1),(B,1),(B,2),(C,2)