Гипердерево: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Гипердерево''' (''Hypertree'') - Гиперграф <math>H = (V,{\cal E})</math> есть ''гипердерево'' то...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Гипердерево''' (''Hypertree'') - | '''Гипердерево''' (''[[Hypertree]]'') - [[Гиперграф]] <math>H = (V,{\varepsilon})</math> есть ''гипердерево'' тогда и только тогда, когда его ''[[граф]] инциденций'' является [[дерево|деревом]]. Под графом инциденций <math>G(H)</math> <math>H = (V,{\varepsilon})</math> подразумевается [[двудольный граф]], [[вершина|вершины]] которого суть элементы множества | ||
Гиперграф <math>H = (V,{\ | <math>V \cup {\varepsilon}</math> с долями <math>V</math> и <math>{\varepsilon }</math>, а [[ребро]] <math>(v,E)</math> существует тогда и только тогда, когда <math>v \in E</math>. | ||
есть ''гипердерево'' тогда и только тогда, когда его ''граф инциденций'' | |||
является деревом. Под графом инциденций <math>G(H)</math> <math>H = (V,{\ | |||
подразумевается двудольный граф, вершины которого суть элементы множества | |||
<math>V \cup {\ | |||
==Литература== | ==Литература== | ||
[Евстигнеев/97] | [Евстигнеев/97] | ||
Версия от 13:26, 8 октября 2009
Гипердерево (Hypertree) - Гиперграф [math]\displaystyle{ H = (V,{\varepsilon}) }[/math] есть гипердерево тогда и только тогда, когда его граф инциденций является деревом. Под графом инциденций [math]\displaystyle{ G(H) }[/math] [math]\displaystyle{ H = (V,{\varepsilon}) }[/math] подразумевается двудольный граф, вершины которого суть элементы множества [math]\displaystyle{ V \cup {\varepsilon} }[/math] с долями [math]\displaystyle{ V }[/math] и [math]\displaystyle{ {\varepsilon } }[/math], а ребро [math]\displaystyle{ (v,E) }[/math] существует тогда и только тогда, когда [math]\displaystyle{ v \in E }[/math].
Литература
[Евстигнеев/97]