Mis on suunatud graaf ja millised on selle omadused?

Suundgraaf on graaf, millel on tippude (sõlmede) ja servade (nooled), kus iga nool omab suunda.

Omadused:

• Suunatud servad: Serva mööda liikumine on võimalik ainult ühes suunas, mis on näidatud noolega.
• Võrgu aste: Suunatud graafi puhul määratletakse siseneva aste (servade arv, mis lõpevad tipus) ja väljuva aste (servade arv, mis algavad tipust).
• Tee ja tsüklid: Tee on tipudest koosnev järjestus, mis on ühendatud servadega õiges suunas. Tsükkel on tee, mis algab ja lõpeb samas tipus. Suunatud graafid võivad sisaldada suunatud tsükleid.
• Ühendatus: Eristatakse nõrka ühendatust (ignoorides servade suunad, on graaf ühendatud nagu mitte-suundgraaf) ja tugevat ühendatust (iga kahe tipu A ja B vahel on suunatud tee A-st B-sse ja B-st A-sse).
• Esitus: Neid saab esitada naabrite loendi või naabrite maatriksi abil, kus suunatud graafi puhul ei ole maatriks tavaliselt sümmeetriline.

Näide naabrite loendi kasutamisest:

# Graaf G = (V, E), kus V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

graaf = {
    0: [1],
    1: [2],
    2: [0]
}

Näide naabrite maatriksi kasutamisest:

# Graaf G = (V, E), kus V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

maatriks = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # puuduvad väljundeid servad 2-st
]