Kas ir virziena grafiks un kādas ir tā īpašības?

Virzienots grafs ir grafs, kurā ir virsotnes (mezgli) un malas (līknes), kur katrai malai ir virziens.

Īpašības:

• Virzienotas malas: Pārvietošana pa malu ir iespējama tikai vienā virzienā, ko norāda bultiņa.
• Virsotnes pakāpe: Virzienotā grafā tiek definēta ieejošā pakāpe (skaits malām, kas beidzas virsotnē) un izejošā pakāpe (skaits malām, kas sākas virsotnē).
• Ceļi un cikli: Ceļš ir virsotņu secība, kas savienota ar malām pareizajā virzienā. Cikls ir ceļš, kas sākas un beidzas tajā pašā virsotnē. Virzienotie grafi var saturēt virzienotus ciklus.
• Savienojamība: Atšķirība starp vāju savienojamību (ignorējot malu virzienus, graf ir nesavienots kā nesavienots) un stipru savienojamību (kādas divas virsotnes A un B ir virzienots ceļš no A uz B un no B uz A).
• Attēlojums: Tos var attēlot ar blakus esošo sarakstu vai blakus esošo matricu, kurā priekš virzienota grafu matrica parasti nav simetriska.

Piemērs ar blakus esošo sarakstu:

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

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

Piemērs ar blakus esošo matricu:

# Graf 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]   # nav izejošo malu no 2
]