Войти
ФлеймФорумОбщее

Что наука знает про графы с трёхконечными рёбрами?

#0
0:30, 19 мар. 2019

Название выбрано за неимением лучшего. Речь вот о чём.
Вот есть граф - это множество вершин v1, v2 ... vN + множество рёбер (vA,vB), соединяющих некоторые из этих вершин. Теперь расширим эту структуру и пометим каждое ребро некой отметкой. А эта отметка будет соответствовать какой-либо из вершин графа. То есть, рёбра у нашего графа будут уже не (vA,vB), а (vA,vB,vC) (где vA - начальная вершина, vB - конечная, vC - вершина, обозначающая отметку данного ребра). Т. е., в некотором смысле, рёбра получаются трёхконечные.
Вопрос же в следующем: что наука знает о таких объектах? Имеется ли какая-нибудь теория, терминология, применения всякие? Провижу, что можно задействовать подобную структуру для представления предметных областей в задачах т. н. искусственного интеллекта, но ведь умные люди уже наверняка до этого додумались и чего-нибудь понапридумывали.
Педивикия что-то заикается про гиперграф, но у гиперграфа набор вершин в ребре предполагается переменного размера и неупорядоченный, а в нашем случае он фиксированный и очень даже упорядоченный. И из этого ограничения наверняка следуют какие-нибудь плодотворные следствия.


#1
2:16, 19 мар. 2019

Ну будет у тебя 3 слоя в графе

#2
3:03, 19 мар. 2019

Sbtrn. Devil
> Теперь расширим эту структуру и пометим каждое ребро некой отметкой.
любая попытка добавить в типа_ребро ещё какие-то данные превращает это типа_ребро в узёл

#3
9:53, 19 мар. 2019

Можешь начать копать отсюда:

- https://en.wikipedia.org/wiki/Entity%E2%80%93attribute%E2%80%93value_model
- https://en.wikipedia.org/wiki/Semantic_triple
- https://en.wikipedia.org/wiki/Comparison_of_triplestores

#4
11:08, 19 мар. 2019

Sbtrn. Devil
Помеченные мультиорграфы?
А еще структура вроде изоморфна обычному графу, с тем же множеством вершин, где каждому трёхконечному ребру (vA,vB,vC) соответствуют два ребра (vA,vC) и (vC,vB).

#5
11:14, 19 мар. 2019

Zegalur
> соответствуют два ребра (vA,vC) и (vC,vB).
Три. еще vA,vB

#6
(Правка: 12:18) 12:17, 19 мар. 2019

9К720
> Три. еще vA,vB
Угу. И даже так не получится изоморфизм, если граф ориентированный и отметка может соответствовать вершине того же ребра:

Изображение

#7
17:06, 19 мар. 2019

Tiendil
> https://en.wikipedia.org/wiki/Semantic_triple
Во, это оно самое.

Zegalur
> Угу. И даже так не получится изоморфизм, если граф ориентированный и отметка
> может соответствовать вершине того же ребра:
Вот да. Если уж изоморфировать, то, скорее, красно-чёрный орграф, где красные вершины "настоящие", а чёрные - рёбра, и каждое "настоящее" ребро (rA,rB,rC) - отображается в вершину bABC и 4 ребра (rA->bABC), (bABC->rB), (rABC<->rC).

ФлеймФорумОбщее