Suunnattu graafi

Suunnattu graafi (tai lyhyesti digraafi ) on (moni) graafi , jonka reunoilla on suunta. Suunnattuja reunoja kutsutaan myös kaariksi , ja joissakin lähteissä niitä kutsutaan yksinkertaisesti reunoiksi. Graafia, jonka reunalle ei ole määritetty suuntaa, kutsutaan suuntaamattomaksi graafiksi tai ei- digraafiksi .

Peruskäsitteet

Muodollisesti digrafi koostuu joukosta , jonka alkioita kutsutaan pisteiksi , ja joukosta järjestettyjä kärkipareja . $D=(V,E)$ $V$ $E$ $u,v\in V$

Kaari on tapaus vertics ja . Tässä tapauksessa he sanovat, että se on kaaren alkupiste ja lopullinen kärki . $(u,v)$ $u$ $v$ $u$ $v$

Yksinkertaisesta graafista reunoja suuntaamalla saatua digraafia kutsutaan suunnatuksi . Toisin kuin jälkimmäinen, mielivaltaisessa yksinkertaisessa digrafissa kaksi kärkeä voidaan yhdistää kahdella eri suunnalla kaarella.

Suunnattua täydellistä kuvaajaa kutsutaan turnaukseksi .

Yhteydet

Reitti digrafissa on vuorotteleva sarja pisteitä ja kaaria , muotoa (pisteet voidaan toistaa). Reitin pituus on siinä olevien kaarien lukumäärä. $v_{0}\{v_{0},v_{1}\}v_{1}\{v_{1},v_{2}\}v_{2}...v_{n}$

Polku on kaksisuuntainen reitti ilman toistuvia kaaria, yksinkertainen polku on ilman toistuvia pisteitä. Jos yhdestä kärjestä toiseen on polku, niin toinen kärki on saavutettavissa ensimmäisestä.

Ääriviiva on suljettu polku .

Puolireitillä kaarien suunnan rajoitus poistetaan ja puolitie ja puolikäyrä määritellään samalla tavalla .

Digraafi on vahvasti yhdistetty tai yksinkertaisesti vahva , jos sen kaikki kärjet ovat keskenään saavutettavissa ; yksisuuntainen yhdistetty tai yksinkertaisesti yksisuuntainen , jos jollekin kahdelle kärjelle vähintään toinen on saavutettavissa toisesta; heikosti kytketty , tai yksinkertaisesti heikko , jos kaarien suuntaa ei oteta huomioon, saadaan yhdistetty (moni)graafi;

Maksimivahvaa osagraafia kutsutaan vahvaksi komponentiksi ; yksipuolinen komponentti ja heikko komponentti määritellään samalla tavalla.

Digraafin kondensaatio on digraafi, jonka kärjet ovat vahvoja komponentteja ja kaari in osoittaa vähintään yhden kaaren olemassaolon vastaaviin komponentteihin sisältyvien kärkien välillä. $D$ $D^{\tähti }$ $D$ $D^{\tähti }$

Lisämääritelmät

Suunnattu asyklinen graafi tai pala on ääriviivaton digraafi.

Suunnattua graafia, joka saadaan annetusta graafista muuttamalla reunojen suuntaa vastakkaiseen suuntaan, kutsutaan käänteiseksi .

Kaikkien kolmen solmun digrafien kuva ja ominaisuudet

Selite: S on heikko, OC on yksipuolinen, SS on vahva, H on suunnattu graafi, G on riippumatto (asyklinen), T on turnaus

tyhjä, N, G	N, G		OS	CC	CC	täynnä, CC
0 kaaria	1 kaari	2 kaaria	3 kaaria	4 kaaria	5 kaaria	6 kaaria
		OS, N, G	CC, N, T	CC
		C, N, G	Käyttöjärjestelmä, N, G, T	OS
		C, N, G	OS	OS

Digrafien soveltaminen

Digrafeja käytetään laajalti ohjelmoinnissa tapana kuvata järjestelmiä, joissa on monimutkaisia yhteyksiä. Esimerkiksi yksi tärkeimmistä kääntäjien kehittämisessä ja yleensä tietokoneohjelmien esittämisessä käytetyistä rakenteista on tietovirtagraafi.

Binäärirelaatiot

Binäärirelaatio äärellisen kantoaallon yli voidaan esittää digraafina . Antirefleksiiviset suhteet voidaan esittää yksinkertaisella digraafilla ; yleensä tarvitaan silmukoilla varustettu digraafi. Jos relaatio on symmetrinen , niin se voidaan esittää suuntaamattomalla graafilla ja jos se on antisymmetrinen, niin suunnatulla graafilla .

Muut

Suurballen algoritmi on algoritmi kahden ei-leikkaavan (ilman yhteisiä reunoja) polun löytämiseksi suunnatusta graafista ei-negatiivisilla painoilla siten, että molemmat polut yhdistävät saman pisteparin ja niillä on vähimmäispituus.

Kirjallisuus

Harari F. Graafiteoria. — M .: URSS , 2003. — 300 s. — ISBN 5-354-00301-6 .
Malmi, Oistin . Graafiteoria. — M .: URSS , 2008. — 352 s. - ISBN 978-5-397-00044-4 .
Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Kääntäjät : Principles, Techniques ja Tools, 2. painos = Kääntäjät: Principles, Techniques ja Tools. - 2. painos - M .: "Williams" , 2008. - ISBN 978-5-8459-1349-4 .

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