Irányított grafikon

Az irányított gráf (vagy röviden digráf ) olyan (többszörös) gráf , amelynek élei irányt rendelnek. Az irányított éleket ívnek is nevezik , egyes forrásokban pedig egyszerűen éleknek. Az olyan gráfot, amelyben nincs élhez rendelve irány, irányítatlan gráfnak vagy nem digráfnak nevezzük .

Alapfogalmak

Formálisan a digráf egy halmazból áll, amelynek elemeit csúcsoknak nevezzük , és egy rendezett csúcspárok halmazából .

Az ív beesik a csúcsokra és . Ebben az esetben azt mondják, hogy  ez az ív kezdeti csúcsa , és  a végső csúcs .

Egy egyszerű gráfból az élek orientálásával kapott digráfot irányítottnak nevezzük . Ez utóbbival ellentétben egy tetszőleges egyszerű digráfban két csúcsot két különböző irányú ív köthet össze.

Az irányított teljes gráfot versenynek nevezzük .

Kapcsolati lehetőségek

A digráfban szereplő útvonal csúcsok és ívek váltakozó sorozata , amelynek alakja (a csúcsok megismételhetők). Az útvonal hossza a  benne lévő ívek száma.

Az útvonal egy útvonal egy digráfban ismétlődő ívek nélkül, az egyszerű útvonal  pedig ismétlődő csúcsok nélkül. Ha van egy út az egyik csúcsból a másikba, akkor a második csúcs elérhető az elsőből.

A körvonal egy zárt út .

Félútvonal esetén az ívek irányának korlátozása megszűnik, és egy félút és egy félkontúr hasonlóképpen kerül meghatározásra .

Egy digráf akkor erősen összefüggő , vagy egyszerűen erős , ha minden csúcsa kölcsönösen elérhető ; egyirányú kapcsolt , vagy egyszerűen egyirányú , ha bármelyik két csúcshoz legalább az egyik elérhető a másikból; gyengén kapcsolt , vagy egyszerűen gyenge , ha figyelmen kívül hagyjuk az ívek irányát, összefüggő (multi)gráfot kapunk;

A maximális erős részgráfot erős komponensnek nevezzük ; az egyoldalú és a gyenge komponenst hasonlóképpen határozzuk meg.

A digráf kondenzációja olyan digráf, amelynek csúcsai erős komponensek , és az in ív azt mutatja, hogy legalább egy ív van a megfelelő komponensekben lévő csúcsok között.

További definíciók

Az irányított aciklikus gráf vagy csomó egy kontúr nélküli digráf.

Inverznek nevezzük azt az irányított gráfot, amelyet egy adott gráfból kapunk, ha az élek irányát ellenkezőre változtatjuk .

Az összes háromcsomópontos digráf képe és tulajdonságai

Jelmagyarázat: S  gyenge, OC  egyoldalú, SS  erős, H  irányított gráf, G  függőágy (aciklikus), T  verseny

Digráfok alkalmazása

A digráfokat széles körben használják a programozásban az összetett kapcsolatokkal rendelkező rendszerek leírására. Például a fordítóprogramok fejlesztésében és általában a számítógépes programok megjelenítésében használt egyik fő struktúra az adatfolyam-gráf.

Bináris relációk

Egy véges vivő feletti bináris relációt digráfként is ábrázolhatjuk . Az antireflexív relációk egyszerű digráfokkal ábrázolhatók, általános esetben hurkokkal ellátott digráfra van szükség. Ha a reláció szimmetrikus , akkor irányítatlan gráfgal , ha pedig antiszimmetrikus, akkor irányított gráfgal ábrázolható .

Vegyes

Suurballe algoritmusa egy olyan algoritmus, amely két nem metsző (közös élek nélküli) utat keres egy irányított gráfban, nem negatív súllyal úgy, hogy mindkét út ugyanazt a csúcspárt köti össze, és minimális közös hosszúságú legyen.

Irodalom

• Harari F. Gráfelmélet. — M .: URSS , 2003. — 300 p. — ISBN 5-354-00301-6 .
• Érc, Oistin . Gráfelmélet. — M .: URSS , 2008. — 352 p. - ISBN 978-5-397-00044-4 .
• Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Fordítók : Alapelvek, Technikák és Eszközök, 2. kiadás = Fordítók: Alapelvek, Technikák és Eszközök. - 2. kiadás - M .: "Williams" , 2008. - ISBN 978-5-8459-1349-4 .