Kas yra orientuotas grafas ir kokios yra jo savybės?

Orientuotas grafas yra grafas, turintis viršūnių (mazgų) ir kraštų (strėlių), kur kiekviena strėlė turi kryptį.

Savybės:

• Kryptingos kraštinės: Judėjimas palei kraštinę įmanomas tik viena kryptimi, nurodyta strėlės.
• Viršūnės laipsnis: Orientuotame grafe apibrėžiami įeinantis laipsnis (kiekis kraštinių, kurios baigiasi viršūnėje) ir išeinantis laipsnis (kiekis kraštinių, kurios prasideda viršūnėje).
• Keliai ir ciklai: Kelias yra viršūnių seka, sujungta kraštinėmis teisinga kryptimi. Ciklas yra kelias, kuris prasideda ir baigiasi tame pačiame viršūnėje. Orientuoti grafai gali turėti kryptinius ciklus.
• Sujungimas: Skiriama silpna sujungimas (neatsižvelgiant į kraštinių kryptis, grafas yra nesusijęs kaip nesukryptas) ir stipri sujungimas (bet kuriose dviejose viršūnėse A ir B yra kryptinis kelias iš A į B ir iš B į A).
• Atvaizdavimas: Jie gali būti pateikti naudojant susietųjų sąrašų arba susietųjų matricų formą, kur orientuotam grafui matrica dažniausiai nėra simetriška.

Pavyzdys, naudojant susietųjų sąrašų atvaizdavimą:

# Grafas G = (V, E), kur V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

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

Pavyzdys, naudojant susietųjų matricų atvaizdavimą:

# Grafas G = (V, E), kur V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matrica = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # nėra išeinančių kraštinių iš 2
]