Úvod do

teorie grafů

Grafy

Zadání mnoha úloh v programátorských soutěžích, jako je Kasiopea, obsahuje dva typy věcí:

  • nějaké bodů,
  • spojnice mezi nimi.

Například body mohou reprezentovat spolužáky a spojnice mohou reprezentovat ty dvojice, které spolu kamarádí. A nebo body mohou reprezentovat města a spojnice jsou mezi těmi dvojicemi měst, mezi nimiž vede přímá cesta.

Bodům v takovém schématu obvykle říkáme vrcholy (nebo uzly), spojnicím hrany a vrcholům spojeným hranou zase sousedi. Celému schématu pak říkáme graf.

V tomto krátkém textu ti přiblížíme, jak s takovými grafy pracovat. Ukážeme ti to na konkrétním příkladu úlohy Světýlka, která byla v roce 2016 v domácím kole soutěže. Pojďme si přečíst zadání:

Na domácí kolo se těší nejeden organizátor Kasiopey. Někteří z nich mají dokonce barevná světýlka, která chtějí připevnit na zdi Matfyzu. Chtějí tak každému připomenout, že se koná domácí kolo.

Světýlka jsou různě propojena dráty, některá vytváří písmena, další složitější obrázky. Obecně tato světýlka a drátky nazveme útvary, dvě světýlka patří do stejného útvaru, pokud mezi nimi vede posloupnost drátků a světýlek. Bohužel, v různých útvarech se vyskytují různé barvy světýlek, což snižuje čitelnost.

Organizátoři mají naštěstí na skladě dostatek světýlek každé barvy, mohou proto vzít každý útvar a vyměnit některá světýlka za ty ve skladu tak, aby měla všechna jeho světýlka stejnou barvu. Jelikož organizátoři neradi dělají zbytečnou práci, obrátili se na vás, abyste jim spočítali, kolik nejméně světýlek musí vyměnit.

Určitě sis všiml(a), že se v této úloze bavíme o grafu: vrcholy jsou v tomto případě světýlka a hrany jsou dráty, kterými jsou světýlka propojená. Graf v úloze je tvořen několika útvary (na obrázku dvěma), tedy skupinami vrcholů takovými, že různé útvary nejsou propojeny hranami a zároveň v každém útvaru se lze po hranách dostat mezi libovolnými dvěma světýlky. Obecně takovým útvarům říkáme komponenty souvislosti.

V úloze má každý vrchol na začátku nějakou barvu a my chceme změnit barvu některých vrcholů tak, aby všechny vrcholy v dané komponentě měly stejnou barvu. Zároveň chceme, aby změn barev bylo co nejméně. Úlohu vyřešíme následujícím způsobem. Pro každou komponentu si spočítáme, kolikrát se v ní vyskytuje každá barva. Následně nalezneme tu barvu, která se v dané komponentě vyskytuje nejčastěji a jinak zbarvené vrcholy komponenty přebarvíme touto nejčastější barvou. Výsledkem je pak celkový počet vrcholů, které jsme přebarvili.

Nyní se dejme do programování! Nejprve musíme vymyslet, jak graf reprezentovat a jak načíst potřebné údaje ze vzorového vstupu. Začněme s reprezentací grafu. Vrcholy grafu jsou obvykle očíslovány čísly 1N, kde N je počet vrcholů grafu. Počet hran se obvykle značí písmenkem M. Graf v programu často reprezentujeme jako seznam délky N, kde indexy seznamu odpovídají vrcholům grafu. Pro každý vrchol si musíme pamatovat, se kterými dalšími vrcholy je spojen hranou, a proto je na každém indexu našeho seznamu další seznam čísel přiřazených sousedům daného vrcholu.

Světýlka Světýlka

Prvním krokem při řešení úlohy je načíst si graf ze vstupního souboru, nebo konzole. Graf je zde obvykle reprezentován následovně. Na první řádce máme napsaná čísla N a M, tedy počet vrcholů grafu a počet hran mezi vrcholy. Následuje M řádek a na každé jsou dvě čísla u a v, jejichž hodnoty jsou mezi 1 a N. Jedná se o dva vrcholy, které jsou spojeny hranou. Klasicky máme v zadání zaručeno, že u ≠ v (jinak by se nejednalo o hranu) a že se ta samá dvojice u, v nevyskytuje dvakrát. Graf výše na obrázku by tak byl reprezentován takto:

9 8
1 2
2 3
3 4
4 5
6 7
8 6
6 9
9 8

Následuje kód, který načte data ve výše popsaném formátu a vytvoří pro každý vrchol seznam jeho sousedů.

# celý graf je reprezentovaný jako seznam seznamů
# přečtení počtu vrcholů n a počtů hran grafu m
n, m = input().split()  # přiřadí prvky seznamu více proměnným
n = int(n)
m = int(m)

# inicializace grafu
graf = []
for i in range(n):
    graf.append([])

# přečtení hran
for i in range(m):
    u, v = input().split()
    u = int(u)
    v = int(v)
    graf[u-1].append(v-1)
    graf[v-1].append(u-1)

Teď, když máme pro každý vrchol uložen seznam jeho sousedů, musíme umět projít vrcholy každé komponenty a zapamatovat si, kolikrát se v komponentě vyskytuje která barva. Zde vám popíšeme asi nejjednodušší způsob, jak projít vrcholy jedné komponenty. Budeme potřebovat pomocné pole navstiveno, kde si pro každý vrchol pamatujeme, zda jsme jej již navštívili. Na začátku jsou všechny hodnoty v tomto poli nastavíme na False. Dále naprogramujeme funkci projdi, která jako parametr dostane vrchol grafu reprezentovaný číslem u v rozmezí od 1 do N. Cílem této funkce je projít všechny vrcholy komponenty obsahující vrchol u. To se udělá následovně: začneme tím, že hodnotu v poli navstiveno na indexu u nastavíme na True. Tím zajistíme, že ten samý vrchol nebudeme procházet vícekrát. Následně projdeme všechny sousedy vrcholu u pomocí for cyklu a ty vrcholy, které jsme ještě nenavštívili, projdeme pomocí volání funkce projdi.

# inicializujeme pole navstiveno na n hodnot False
navstiveno = []
for i range(n):
    navstiveno.append(False)

def projdi(u):
    # nastav vrchol u na navštívený
    navstiveno[u] = True
    # projdi všechny jeho nenavštívené sousedy
    for v in graf[u]:
        if not navstiveno[v]:
            projdi(v)

Do těla funkce projdi můžeme přidat libovolné další funkce zpracovávající vrcholy. Například, kdybychom přidali výpis čísla u, po skončení funkce projdi dostaneme výpis všech vrcholů komponenty, do které u patří.

navstiveno = []
for i range(n):
    navstiveno.append(False)

def projdi(u):
    navstiveno[u] = True
    # přidaný výpis
    print(u)
    for v in graf[u]:
        if not navstiveno[v]:
            projdi(v)

Na projití všech komponent použijeme obyčejný for cyklus přes vrcholy v poli navstiveno. Pokud u vrcholu máme v tomto poli údaj False, zavoláme na něj funkci projdi, jinak se posuneme na další vrchol.

navstiveno = []
for i range(n):
    navstiveno.append(False)

# projití všech komponent
for u in range(len(navstiveno)):
    # pokud vrchol není navštívený, projdi komponentu, ve které leží
    if not navstiveno[u]:
        projdi(u)

A jak to všechno použijeme v naší úloze? Potřebujeme počítat výskyty jednotlivých barev a na to si budeme udržovat pole barvy. Ve funkci projdi se vždy podíváme na barvu vrcholu a zvýšíme na odpovídajícím místě v poli barvy počet jejích výskytů o jedna. Po projití každé komponenty si najdeme barvu s nejvyšším výskytem a dopočítáme z pole barvy celkový počet vrcholů komponenty. Z těchto informací spočítáme počet vrcholů, které je třeba přebarvit. Než začneme procházet další komponentu, potřebujeme ještě vynulovat pole barvy, abychom počty pro různé komponenty nemíchali.

''' úloha Světýlka
Kromě grafu zadaného pomocí hran dostaneme i seznam čísel
délky n, který pro každý vrchol udává, která barva je mu přiřazena
'''

t = int(input())
for test in range(t):

    # načtení grafu ze vstupu
    n, m = input().split()
    n = int(n)
    m = int(m)

    graf = []
    for i in range(n):
        graf.append([])

    for i in range(m):
        u, v = input().split()
        u = int(u)
        v = int(v)
        graf[u-1].append(v-1)
        graf[v-1].append(u-1)

    # načtení barev přiřazených jednotlivým vrcholům:
    # načteme celý řádek jako string, na který poté zavoláme funkci split(),
    # jež rozdělí string podle mezer a výsledné části uloží do pole barvy_vrcholu_pom
    barvy_vrcholu_pom = input().split()
    # všechny hodnoty převedeme na čísla
    barvy_vrcholu = []
    for barva in barvy_vrcholu_pom:
        barvy_vrcholu.append(int(barva))

    # zavedeme si pomocná pole navstiveno a barvy
    # velikost pole navstiveno je nastavena na n
    # délku pole barvy dle parametru lehčí varianty úlohy nastavíme na 1000
    navstiveno = []
    for i in range(n):
        navstiveno.append(False)
    pocty_barev = []
    for i in range(1000):
        pocty_barev.append(0)

    # počet vrcholů, jež je třeba obarvit, si budeme pamatovat v proměnné obarvit
    obarvit = 0

    # upravíme funkci projdi tak, aby navíc počítala barvy
    def projdi(u):
        # nastav vrchol u na navštívený
        navstiveno[u] = True
        # zjisti barvu vrcholu
        barva_u = barvy_vrcholu[u]
        # zvyš počet výskytů dané barvy
        pocty_barev[barva_u] += 1
        # projdi všechny jeho nenavštívené sousedy
        for v in graf[u]:
            if not navstiveno[v]:
                projdi(v)

    # projdeme nyní všechny komponenty
    for i in range(len(navstiveno)):
        # pokud vrchol není navštívený, projdi komponentu, ve které leží
        if not navstiveno[i]:
            projdi(i)
            # najdeme barvu s nejvyšším výskytem
            # nepotřebujeme ale přímo index barvy, stačí nám pouze počet výskytů
            # na to můžeme použít vestavěnou funkci max()
            max_barva = max(pocty_barev)
            # dále sečteme všechny počty barev pomocí funkce sum(),
            # čímž získáme počet všech vrcholů v komponentě;
            # od tohoto čísla odečteme počet vrcholů s nejvíce se vyskytující barvou
            pocet_vrcholu_komponenty = sum(pocty_barev)
            nove_obarvene = pocet_vrcholu_komponenty - max_barva
            # přičteme počet k proměnné obarvit
            obarvit += nove_obarvene
            # vynulujeme pole pocty_barev
            for j in range(1000):
                pocty_barev[j] = 0

    # prošli jsme všechny komponenty, zbývá už jen vypsat výsledek
    print(obarvit)

Kód výše je schopný vyřešit jednodušší variantu úlohy se Světýlky. To, jestli jsi pochopil(a), jak se pracuje s grafy, si můžeš vyzkoušet například na úloze Obyvatelé (svůj kód můžeš na stránce odevzdat a dovědět se, jestli je správně).

Speciálním případem grafů jsou tzv. stromy, což jsou grafy, kde existuje cesta mezi libovolnými dvěma vrcholy a navíc neobsahují tzv. cyklus (graf nakreslený nahoře není strom, protože se z vrcholu 1 nelze dostat do vrcholu 7 a navíc mezi vrcholy 6, 8, 9 vede cyklus). Občas se stane, že máš danou úlohu vyřešit jen pro graf, který je strom, ale i pokud tvé řešení má fungovat pro všechny grafy, vyplatí se často nejdřív vymyslet, jak úlohu vyřešit pro strom, a následně své řešení zobecnit pro všechny grafy.

S grafy se toho samozřejmě dá dělat mnohem více. Například pokud někde narazíš na pojmy jako prohledávání do šířky, prohledávání do hloubky nebo rekurze bude to vše souviset právě s grafy. Pokud by tě toto téma zaujalo, můžeš se podívat třeba do KSP kuchařky, kde se dozvíš více nejenom o grafech samotných, ale i různých algoritmech, ve kterých se používají.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)