Графи равшанӣ чист ва хусусиятҳои он чӣҳост?

Ёндаро граф — гэта граф, які мае набор вяршыняў (вузлоў) і набор рёбер (стрэлак), пры гэтым кожная стрэлка мае кірунак.

Асаблівасці:

• Кіраваныя рёбра: Перасоўванне па роўбі магчыма толькі ў адным кірунку, паказаным стрэлкай.
• Ступень вяршыні: Для кіраванага графа вызначаюць уводную ступень (колькасць рёбер, якія заканчваюцца ў вяршыні) і выхадную ступень (колькасць рёбер, якія пачынаюцца з вяршыні).
• Шляху і цыклы: Шлях — гэта паслядоўнасць вяршынь, злучаных рёбрами ў правільным кірунку. Цыкл — гэта шлях, які пачынаецца і заканчваецца ў адным і тым жа вяршыні. Кіраваныя графы могуць утрымліваць кіраваныя цыклы.
• Злучнасць: Адрозніваюць слабую злучнасць (ігнаруючы кірункі рёбер, граф з'яўляецца неарыентаваным звязаным) і моцную злучнасць (для любых двух вяршынь A і B існуе кіраваны шлях з A у B і з B у A).
• Прадстаўленне: Могуць быць прадстаўлены спісам суседства або матрыцай суседства, дзе для кіраванага графа матрыца звычайна не сімметрычная.

Прыклад прадстаўлення з дапамогай спісу суседства:

# Граф G = (V, E), дзе V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

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

Прыклад прадстаўлення з дапамогай матрыцы суседства:

# Граф G = (V, E), дзе V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matрыца = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # няма выхадных рёбер з 2
]