Hypergraf

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 5. dubna 2021; ověření vyžaduje 1 úpravu .

Hypergraf je zobecnění grafu , ve kterém každá hrana může spojovat nejen dva vrcholy , ale také jakoukoli podmnožinu množiny vrcholů.

Z matematického hlediska je hypergraf párem , kde je neprázdná množina objektů nějaké povahy, nazývaná vrcholy hypergrafu, a je to rodina neprázdných (ne nutně odlišných) podmnožin množiny , nazývaná hypergraf. okraje. $(V, E)$ $PROTI$ $E$ $PROTI$

Hypergrafy se používají zejména při modelování elektrických obvodů .

Transverzál hypergrafu je množina obsahující neprázdný průsečík s každou hranou. Taková transverzálie je minimální, pokud žádná její podmnožina není sama o sobě hypergrafickou transverzálou. $T\subseteq V$

Literatura

V. A. Emeličev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyškevič. Kapitola XI: Hypergrafy // Přednášky o teorii grafů. - M .: Science , 1990. - S. 298-315. — 384 s. — ISBN 5-02-013992-0 .
I. A. Golovinskij. Metody analýzy topologie spínacích obvodů elektrických sítí // Elektřina. - 2005. - č. č. 3 . - S. 10-18 .
V. A. Evstignejev, V. N. Kasjanov. Výkladový slovník teorie grafů . - Novosibirsk: Nauka, 1999. Archivní kopie ze dne 29. června 2008 na Wayback Machine
A. A. Zykov. Hypergrafy // Pokroky v matematických vědách. - 1974. - č. 6 (180) .

Datové struktury
Seznamy	pole jednotlivě propojený seznam dvojitě propojený seznam Seznam průchodů
Stromy	B-strom Binární vyhledávací strom strom AVL Červeno-černý strom halda
Počítání	Orientovaný graf Orientovaný acyklický graf Binární rozhodovací diagram Hypergraf
jiný	Hash tabulka Zásobník