Az irányítatlan gráfok esetén az él két végpontjának sorrendje nem releváns. Az él nem egyikből a másikba megy, hanem csak egy összeköttetés a kettő között. Ha az élekhez irányításokat is rendelünk, irányított gráfot kapunk.

Irányított gráfok

Románul: graf orientat, angolul: directed graph (vagy röviden: digraph)

Cikk pbinfo-n: https://www.pbinfo.ro/articole/509/grafuri-orientate

Értelmezés

A G = (X, U) halmazpárt irányított gráfnak nevezzük, ahol:

• X – a csúcsok / csomópontok halmaza (a csúcs románul vârf, angolul vertex; csomópont románul nod, angolul node)
• U – az élek / ívek (románul arce, angolul arcs) halmaza, melynek elemei az X elemeiből alkotott (rendezett) számpárok

Általában a csomópontokat 1-től n-ig terjedő egész számokkal címkézzük, ahol n = |X|, az éleket pedig (x,y) jelöléssel írjuk le, ahol x és y csomópontok.

Egyszerű gráf: két csomópont között legfeljebb két él lehet, egy oda, egy vissza, és nincsenek hurokélek – bucle (azaz egy csomópontból önmagába menő élek).

További fogalmak:

• a.m.h. („azt mondjuk, hogy”) az x és y csúcsok szomszédosak, ha létezik az (x,y) él, vagy az (y,x) él, vagy mindkettő.
• az (x,y) élnek x a „kezdőpontja” (kiindulópontja), y a „végpontja”.

Példa

    G = (X,U)
    X = {1, 2, 3, 4, 5, 6}
    U = {(1,2) (2,1), (1,3), (3,4), (4, 1), (4, 6), (5,4) }

Fokszámok

Értelmezés: Egy csomópont bejövő fokszáma (röviden „befoka”) azon élek számát jelenti, amelyek ide érkeznek (tehát ez a csomópont a végpontjuk). Románul grad interior, angolul in-degree.

Értelmezés: Egy csomópont kimenő fokszáma (röviden „kifoka”) azon élek számát jelenti, amelyek innen indulnak (tehát ez a csomópont a kezdőpontjuk). Románul grad exterior, angolul out-degree.

Megjegyzések: - egy csomópont be- és kifoka egy 0 és |X|-1 közötti egész; - egy 0 fokszámú csomópontra a.m.h. „izolált”.

Tétel

Egy irányítatlan gráfban a bejövő fokszámok összege egyenlő az élek számával. A kimenő fokszámok összege szintén egyenlő az élek számával.

Irányított gráfok ábrázolása (memóriában)

1. Éllistával (listă de arce / muchii)

Kell a csomópontok száma + az élek listája:

    X = {1, 2, 3, 4, 5, 6}
    U = { (1,2), (2,3), (3,2), (3,5) (5,6) }

2. Szomszédsági mátrix-szal (matrice de adiacență)

Ha n csomópont van a gráfban, akkor a szomszédsági mátrix n x n-es és az i. sor j. oszlopában levő elem megmondja, hogy i-ből j-be van-e ív (irányított él): 1-ha igen, 0 ha nem.

    0  1  0  0  0  0    (sorindex – kiinduló pont)
    0  0  1  0  0  0    (oszlopindex – végpont)
    0  1  0  0  1  0
    0  0  0  0  0  0 
    0  0  0  0  0  1 
    0  0  0  0  0  0 

Irányított gráfok esetén a szomszédsági mátrix nem feltétlenül szimmetrikus a főátlóra nézve.

3. Szomszédsági listákkal (liste de adiacență)

Minden csomópont esetén eltároljuk, hogy hova indul innen él (hol van a végpontja azoknak az éleknek, amiknek az aktuális pont a kezdőpontja).

    1:  2
    2:  3
    3:  2, 5
    4:  üres
    5:  6
    6:  üres
    7:  üres

Sajátos gráfok:

• teljes gráf: bármely két pont között van benne él legalább az egyik irányban (más helyeken: akkor teljes ha minkét irányban van él a pontok között);
• turnégráf (graf turneu): bármely két pont között van él pontosan egy irányban.

Séta, vonal, út

• séta (drum): pontok sorozata, két-két pont között él van (fontos az irányítása is)
• lánc (lanț): pontok sorozata, ahol két-két egymás melletti pont szomszédos, de az élek irányítását nem figyeljük
• vonal (drum simplu): séta, amin nem ismétlődnek élek
• út (drum elementar): séta, amin nem ismétlődnek pontok
• zárt vonal – circuit
• kör (zárt út) – circuit elementar

Egy út hossza egyenlő az őt alkotó élek számával.

Példa:

• séta: 2 4 5 1 4 5
• lánc, de nem séta: 5 4 1
• vonal: 2 4 5 1 4
• út: 2 4 5 1
• kör: 4 5 1 4

Összefüggőség

• erősen összefüggő komponens (tare conex): tetszőleges A,B pontjaira van út A-ból B-be és B-ből A-ba is.
• gyengén összefüggő komponens: ha elhagynánk az irányításokat, akkor a megfelelő nemirányított gráfban összefüggőek lennének.

Példa:

Erősen összefüggő komponensei: {1,3,4}, {2}, {5,6,7,8}.

Az egész gráf gyengén öszefüggő.

Hamiltoni és euleri gráf:

• egy irányított gráf hamiltoni, ha van olyan (irányított) köre, amely minden pontot pontosan egyszer tartalmaz;
• egy irányított gráf euleri, ha van olyan zárt vonala (irányított), amely minden élet pontosan egyszer érint;
• tétel: egy izolált pontokat nem tartalmazó irányított gráf euleri, ha erősen összefüggő és minden pont kimenő fokszáma egyenlő a bejövő fokszámával.

Gyakorlatok

1.

Hány n-pontú irányított gráf létezik (a pontjai {1,2, … n})?

Megoldás:

    2^variációk(n,2)

2.

Rajzoljuk le azt az irányított gráfot, melynek szomszédsági mátrixa:

    0  1  0  1  0  1
    1  0  0  0  0  0
    0  0  0  1  0  0
    1  0  0  0  0  1
    1  0  0  0  0  0
    1  0  0  1  1  0

Írjuk le a szomszédsági listákat!

    1: 2, 4, 6
    2: 1
    3: 4
    4: 1, 6
    5: 1
    6: 1, 4, 5

3.

Írjuk le a szomszédsági mátrixát annak a 8 pontú irányított gráfnak, melynek élei:

    (1,2), (2,4), (4,3), (3,4), (4,5), (1,5), (7,8), (6,7)

Megoldás:

        1. 2. 3. 4. 5. 6. 7. 8
    1.  0  1  0  0  1  0  0  0
    2.  0  0  0  1  0  0  0  0
    3.  0  0  0  1  0  0  0  0
    4.  0  0  1  0  1  0  0  0
    5.  0  0  0  0  0  0  0  0
    6.  0  0  0  0  0  0  1  0
    7.  0  0  0  0  0  0  0  1
    8.  0  0  0  0  0  0  0  0