Hypergraph

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 5. huhtikuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Hypergrafi on graafin yleistys , jossa jokainen reuna voi yhdistää kahden kärjen lisäksi myös minkä tahansa kärkijoukon osajoukon.

Matemaattisesta näkökulmasta hypergrafi on pari , jossa on ei-tyhjä joukko jonkin luonteisia objekteja, joita kutsutaan hypergrafipisteiksi, ja se on joukon ei-tyhjien (ei välttämättä erilaisten) osajoukkojen perhe , jota kutsutaan hypergraafiksi. reunat. $(V, E)$ $V$ $E$ $V$

Hypergrafeja käytetään erityisesti sähköisten piirien mallintamisessa .

Hypergrafin poikkisuunta on joukko, joka sisältää ei-tyhjän leikkauspisteen jokaisen reunan kanssa. Tällainen transversaali on minimaalinen, jos mikään sen osajoukko ei ole itsessään hypergrafitransversaali. $T\subseteq V$

Kirjallisuus

V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Luku XI: Hypergraafit // Graafiteorian luentoja. - M .: Science , 1990. - S. 298-315. — 384 s. — ISBN 5-02-013992-0 .
I. A. Golovinsky. Sähköverkkojen kytkentäpiirien topologian analysointimenetelmät // Sähkö. - 2005. - Nro nro 3 . - S. 10-18 .
V. A. Evstigneev, V. N. Kasjanov. Graafiteorian selittävä sanakirja . - Novosibirsk: Nauka, 1999. Arkistokopio päivätty 29. kesäkuuta 2008 Wayback Machinessa
A. A. Zykov. Hypergraafit // Matemaattisten tieteiden edistysaskel. - 1974. - nro 6 (180) .

Tietorakenteet
Luettelot	joukko yksittäin linkitetty lista kaksoislinkitetty lista Passilista
puut	B-puu Binäärihakupuu AVL puu Puna-musta puu pino
Laskee	Suunnattu graafi Suunnattu asyklinen graafi Binääripäätöskaavio Hypergraph
muu	Hash-taulukko Pino