32. Grafy

Terminológia

Graf je dátová štruktúra, ktorá sa skladá

  • z množiny vrcholov V = {V1, V2, …}
  • z množiny hrán H, pričom každá hrana je dvojica (v, w), kde v, w in V
    • ak sú to neusporiadané dvojice, hovoríme tomu neorientovaný graf
    • ak sú to usporiadané dvojica, hovoríme tomu orientovaný graf

Graf budeme znázorňovať takto:

  • vrcholy sú kolieska
  • hrany sú spojovníky medzi vrcholmi, pričom, ak je graf orientovaný, tak spojovníkmi sú šípky

Graf najčastejšie používame, keď potrebujeme vyjadriť takéto situácie:

  • mestá spojené cestami (najčastejšie je to neorientovaný graf: mestá sú vrcholy, hrany označujú cesty medzi mestami)
  • križovatky a ulice v meste (križovatky sú vrcholy, hrany sú ulice medzi križovatkami)
  • susediace štáty alebo nejaké oblasti (štáty sú vrcholy, hrany označujú, že nejaké štáty susedia)
  • mestská verejná doprava (zastávky sú vrcholy, hrany označujú, že existuje linka, ktorá má tieto dve susediace zastávky)
  • skupina ľudí, ktorí sa navzájom poznajú (ľudia sú vrcholy, hrany označujú, že nejaké konkrétne dve osoby sa poznajú)

Rôzne príklady využitia typu graf:

_images/32_0.png _images/32_1.png _images/32_2.png _images/32_3.png _images/32_4.png _images/32_5.png _images/32_6.png

Dôležité pojmy

  • ak existuje hrana (v, w) - tak hovoríme, že v a w sú susediace vrcholy
  • v grafe môžeme mať uchované rôzne informácie:
    • v každom vrchole (podobne ako v strome) napr. meno, súradnice v ploche (na mape), …
    • každá hrana môže mať nejakú hodnotu (tzv. váha), vtedy tomu hovoríme ohodnotený graf, napr. vzdialenosť dvoch miest, cena cestovného lístka, linky, ktoré spájajú dve zastávky, …
  • cesta je postupnosť vrcholov, ktoré sú spojené hranami
    • dĺžka cesty pre neohodnotený graf počet hrán na ceste, t.j. počet vrcholov cesty - 1
    • dĺžka cesty v ohodnotenom grafe je súčet váh na hranách cesty
  • cyklus je taká cesta, pre ktorú prvý a posledný vrchol sú rovnaké
    • ak graf neobsahuje ani jeden cyklus, hovoríme že je acyklický
  • hovoríme, že graf je súvislý (spojitý), ak pre každé dva vrcholy v, w in V, existuje cesta z v do w
  • niekedy bude pre nás dôležité, keď nejaký graf bude súvislý/nesúvislý bez cyklov, ale aj súvislý/nesúvislý s cyklom
  • hrane (v, v) hovoríme slučka (toto bude veľmi zriedkavé, ak sa to niekedy objaví, upozorníme na to)
  • pojem komponent označuje súvislý podgraf, ktorý je disjunktný so zvyškom grafu (neexistuje hrana ku vrcholom vo zvyšku grafu)

Ďalej ukážeme najčastejšie spôsoby reprezentácie grafov. Konkrétna reprezentácia sa potom zvolí väčšinou podľa problémovej oblasti a rôznych obmedzení v zadaní.

32.1. Reprezentácie

Tento konkrétny graf postupne ukážeme v rôznych reprezentáciách

_images/32_7.png

Na rozdiel od dátových štruktúr spájaný zoznam a binárny strom, pri ktorých sme si ukázali jedinú reprezentáciu pomocou smerníkov, pri dátovej štruktúre graf si väčšinou zvolíte tú reprezentáciu, s ktorou sa vám pri tej ktorej konkrétnej úlohe najlepšie pracuje. Nižšie uvedieme niekoľko bežných reprezentácií, v ktorých sa využívajú pythonovské typy list, set a dict. Neskôr uvidíte aj iné spôsoby reprezentácie grafov.

32.1.1. Pole množín susedností

Aby sme nemuseli pracovať s jednoznakovými reťazcami ‚a‘, ‚b‘, …, očíslujeme vrcholy číslami 0, 1, 2, …

Pre čitateľnosť zápisu najprv vytvoríme 8 konštánt a=0, b=1, c=2, … a pomocou nich zadefinujeme celý graf ako pole množín, kde i-ta množina reprezentuje všetkých susedov i-teho vrcholu:

a,b,c,d,e,f,g,h = range(8)
graf = [{b,c,d,e,f},  #a
        {c,e},        #b
        {d},          #c
        {e},          #d
        {f},          #e
        {c,g,h},      #f
        {f,h},        #g
        {f,g},        #h
        ]

Pre túto štruktúru vieme zistiť, počet vrcholov, počet všetkých hrán, stupeň konkrétneho vrcholu a či medzi dvoma konkrétnymi vrcholmi je hrana:

>>> print('pocet vrcholov:', len(graf))
pocet vrcholov: 8
>>> print('pocet hran:', sum(map(len, graf)))
pocet hran: 17
>>> print('stupen vrcholu f:', len(graf[f]))
stupen vrcholu f: 3
>>> print('hrana medzi b,e:', e in graf[b])
hrana medzi b,e: True
>>> print('hrana medzi c,a:', a in graf[c])
hrana medzi c,a: False

Túto reprezentáciu môžeme „zabaliť“ do triedy napr. takto:

class Graf:
    def __init__(self, pole=None):
        if pole is None:
            self.pole = []
        else:
            self.pole = pole

    def pridaj_hranu(self, v1, v2):
        while len(self.pole)-1 < max(v1, v2):
            self.pole.append(set())
        self.pole[v1].add(v2)

    def je_hrana(self, v1, v2):
        return v2 in self.pole[v1]

    def daj_vrcholy(self):
        return list(range(len(self.pole)))

    def daj_hrany(self):
        return [(v1, v2) for v1 in range(len(self.pole)) for v2 in self.pole[v1]]

    def stupen(self, v=None):
        if v is not None:
            return len(self.pole[v])
        return max(map(len, self.pole))

    def __str__(self):
        return 'vrcholy: {}\nhrany: {}'.format(self.daj_vrcholy(), self.daj_hrany())

    def __repr__(self):
        return 'Graf({})'.format(self.pole)

a graf môžeme teraz vytvoriť napr. takto:

>>> graf = Graf()
>>> graf.pridaj_hranu(a,b)
>>> graf.pridaj_hranu(b,e)
>>> graf.pridaj_hranu(f,h)
>>> graf.pridaj_hranu(g,f)
>>> graf
Graf([{1}, {4}, set(), set(), set(), {7}, {5}, set()])
>>> print(graf)
vrcholy: [0, 1, 2, 3, 4, 5, 6, 7]
hrany: [(0, 1), (1, 4), (5, 7), (6, 5)]

Všimnite si, že sme vyrobili dve rôzne metódy __repr__() a __str__(). Metóda __repr__() sa zavolá, napr. keď v dialógovom režime zapíšeme >>> graf. Metóda __str__() sa zavolá, napr. keď budeme graf vypisovať príkazom print().

Tak ako sme túto triedu Graf definovali, je trochu komplikované vytvoriť izolovaný vrchol, t.j. taký, z ktorého nevychádza žiadna hrana (asi by pomohla metóda pridaj_vrchol()).

Ak máme vyrobenú štruktúru grafu graf, vieme z nej priamo vytvoriť triedu graf:

>>> graf = Graf(G)
>>> print(graf)
vrcholy: [0, 1, 2, 3, 4, 5, 6, 7]
hrany: [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 4), (2, 3), (3, 4), (4, 5), (5, 2), (5, 6), (5, 7), (6, 5), (6, 7), (7, 5), (7, 6)]
>>> graf.je_hrana(b, e)
True
>>> graf.je_hrana(c, a)
False
>>> print('stupen vrcholu f:', graf.stupen(f))
stupen vrcholu f: 3

V tejto reprezentácii grafu triedou Graf o samotnom vrchole nemáme žiadnu špeciálnu informáciu okrem jeho poradového čísla a prislúchajúcej množiny susedov.

Zadefinujeme novú triedu Graf, ktorá bude uchovávať pole vrcholov, t.j. pole objektov typu Vrchol:

class Graf:

    class Vrchol:
        def __init__(self, meno):
            self.meno = meno
            self.sus = set()

    #-------

    def __init__(self):
        self.pole = []

    def pridaj_vrchol(self, meno):      # vrati instanciu Vrchol
        for v in self.pole:
            if v.meno == meno:
                return v                # uz existuje
        novy = self.Vrchol(meno)
        self.pole.append(novy)
        return novy

    def hladaj_vrchol(self, meno):      # vrati instanciu Vrchol
        for v in self.pole:
            if v.meno == meno:
                return v
        return None

    def pridaj_hranu(self, v1, v2):
        self.pridaj_vrchol(v1).sus.add(v2)

    def je_hrana(self, v1, v2):
        return v2 in self.hladaj_vrchol(v1).sus

    def daj_vrcholy(self):
        return [v.meno for v in self.pole]

    def daj_hrany(self):
        return [(v.meno, v2) for v in self.pole for v2 in v.sus]

    def stupen(self, v=None):
        if v is not None:
            return len(self.hladaj_vrchol(v).sus)
        return max(len(v.sus) for v in self.pole)

    def __str__(self):
        return 'vrcholy: {}\nhrany: {}'.format(self.daj_vrcholy(), self.daj_hrany())

S vrcholmi teraz musíme pracovať prostredníctvom ich mien, t.j. jednoznakých reťazcov, napr.

>>> graf = Graf()
>>> for v1, v2 in 'ab ac ad ae af bc be cd de ef fc fg fh gf gh hf hg'.split():
        graf.pridaj_hranu(v1, v2)
>>> print(graf)
vrcholy: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
hrany: [('a', 'c'), ('a', 'b'), ('a', 'e'), ('a', 'd'), ('a', 'f'), ('b', 'c'),
('b', 'e'), ('c', 'd'), ('d', 'e'), ('e', 'f'), ('f', 'g'), ('f', 'c'), ('f', 'h'),
('g', 'h'), ('g', 'f'), ('h', 'g'), ('h', 'f')]
>>> print('stupen vrcholu f:', graf.stupen('f'))
stupen vrcholu f: 3
>>> print('stupen grafu:', graf.stupen())
stupen grafu: 5
>>> print('hrana medzi b,e:', graf.je_hrana('b','e'))    # alebo graf.je_hrana(*'be')
hrana medzi b,e: True
>>> print('hrana medzi c,a:', graf.je_hrana('c','a'))
hrana medzi c,a: False
>>> print('pocet hran:', len(graf.daj_hrany()))
pocet hran: 17

Zrejme efektívnejšie by sa táto definícia realizovala nie poľom vrcholov, ale asociatívnym poľom (typ dict) vrcholov, v ktorom kľúčom by bol identifikátor vrcholu.

32.1.2. Asociatívne pole množín susedností

Pri realizácii reprezentácie množiny susedností pomocou tried Graf a Vrchol sa ukázalo nešikovné, keď sme mali všetky vrcholy (inštancie triedy Vrchol) uložené v poli. Pri práci s takýmito vrcholmi sme museli veľakrát preliezať celé pole a hľadať vrchol s daným identifikátorom. Ak by sme namiesto toho použili asociatívne pole, výrazne by sa to zjednodušilo, napr.

graf = {'a': set('bcdef'),   # {'b','c','d','e','f'}
        'b': set('ce'),
        'c': set('d'),
        'd': set('e'),
        'e': set('f'),
        'f': set('cgh'),
        'g': set('fh'),
        'h': set('fg'),
       }

Zapíšeme to pomocou tried Graf a Vrchol:

class Graf:

    class Vrchol:
        def __init__(self, meno):
            self.meno = meno
            self.sus = set()

        def pridaj_hranu(self, v2):
            self.sus.add(v2)

        def __contains__(self, v2):
            return v2 in self.sus

    #-------

    def __init__(self):
        self.pole = {}

    def pridaj_vrchol(self, meno):
        if meno not in self.pole:
            self.pole[meno] = self.Vrchol(meno)

    def pridaj_hranu(self, v1, v2):
        self.pridaj_vrchol(v1)
        self.pole[v1].pridaj_hranu(v2)

    def je_hrana(self, v1, v2):
        return v2 in self.pole[v1]

    def daj_vrcholy(self):
        return list(self.pole.keys())

    def daj_hrany(self):
        return [(v1, v2) for v1, v in self.pole.items() for v2 in v.sus]

    def stupen(self, v=None):
        if v  is not None:
            return len(self.pole[v].sus)
        return max(len(v.sus) for v in self.pole.values())

    def __str__(self):
        return 'vrcholy: {}\nhrany: {}'.format(self.daj_vrcholy(), self.daj_hrany())

32.1.3. Pole asociatívnych polí susedností

Ak máme napr. takýto ohodnotený graf:

_images/32_8.png

tak namiesto množiny susedností (prvá reprezentácia grafu) použijeme asociatívne pole (typ dict), v ktorom si pri každom susedovi budeme pamätať aj číslo na hrane, t.j. váhu:

a,b,c,d,e,f,g,h = range(8)

graf = [{b:2,c:1,d:3,e:9,f:4},     #a
        {c:4,e:3},                 #b
        {d:8},                     #c
        {e:7},                     #d
        {f:5},                     #e
        {c:2,g:2,h:9},             #f
        {f:2,h:6},                 #g
        {f:9,g:6},                 #h
        ]

Mohli by sme tu využiť aj reprezentáciu asociatívne pole množín susedností, v ktorej by sme množiny opäť nahradili asociatívnymi poľami, napr.

a,b,c,d,e,f,g,h = range(8)

graf = {a: {b:2,c:1,d:3,e:9,f:4},
        b: {c:4,e:3},
        c: {d:8},
        d: {e:7},
        e: {f:5},
        f: {c:2,g:2,h:9},
        g: {f:2,h:6},
        h: {f:9,g:6},
        }

Zrejme túto reprezentáciu by sme mali volať asociatívne pole asociatívnych polí susedností. Aj tu môžeme čísla vrcholov nahradiť reťazcami:

graf = {'a': {'b':2,'c':1,'d':3,'e':9,'f':4},
        'b': {'c':4,'e':3},
        'c': {'d':8},
        'd': {'e':7},
        'e': {'f':5},
        'f': {'c':2,'g':2,'h':9},
        'g': {'f':2,'h':6},
        'h': {'f':9,'g':6},
        }

32.1.4. Matica susedností

Graf zapíšeme do dvojrozmerného poľa veľkosti n x n, kde n je počet vrcholov:

a,b,c,d,e,f,g,h = range(8)

graf = [[0,1,1,1,1,1,0,0],
        [0,0,1,0,1,0,0,0],
        [0,0,0,1,0,0,0,0],
        [0,0,0,0,1,0,0,0],
        [0,0,0,0,0,1,0,0],
        [0,0,1,0,0,0,1,1],
        [0,0,0,0,0,1,0,1],
        [0,0,0,0,0,1,1,0],
        ]

Často sa namiesto 0 a 1 píšu False a True.

Otestujme, ako sa zapisuje práca s takouto reprezentáciou:

>>> print('pocet vrcholov:', len(graf))
pocet vrcholov: 8
>>> print('pocet hran:', sum(map(sum,graf)))
pocet hran: 17
>>> print('stupen vrcholu f:', sum(graf[f]))
stupen vrcholu f: 3
>>> print('hrana medzi b,e:', graf[b][e]==1)
hrana medzi b,e: True
>>> print('hrana medzi c,a:', graf[c][a]==1)
hrana medzi c,a: False

32.1.5. Matica susedností s váhami

Namiesto 0 a 1 v dvojrozmernom poli zapisujeme priamo váhy na príslušných hranách, pričom treba nejako označiť hodnotu, ktorá reprezentuje, že tu nie je hrana, napr.

a,b,c,d,e,f,g,h = range(8)
_ = -1       # oznacuje, ze tu nie je hrana, mohla tu byt aj hocijaka ina hodnota napr. None

graf = [[_,2,1,3,9,4,_,_],
        [_,_,4,_,3,_,_,_],
        [_,_,_,8,_,_,_,_],
        [_,_,_,_,7,_,_,_],
        [_,_,_,_,_,5,_,_],
        [_,_,2,_,_,_,2,9],
        [_,_,_,_,_,2,_,6],
        [_,_,_,_,_,9,6,_],
        ]

Otestujme, ako sa zapisuje práca s takouto reprezentáciou:

>>> print('pocet vrcholov:', len(graf))
pocet vrcholov: 8
>>> print('pocet hran:', sum(1 for r in graf for x in r if x!=_))
pocet hran: 17
>>> print('stupen vrcholu f:', sum(1 for x in graf[f] if x!=_))
stupen vrcholu f: 3
>>> print('hrana medzi b,e:', graf[b][e]!=_)
hrana medzi b,e: True
>>> print('hrana medzi c,a:', graf[c][a]!=_)
hrana medzi c,a: False
>>> print('vaha na hrane medzi b,e:', graf[b][e])
vaha na hrane medzi b,e: 3

32.2. Cvičenie

  1. Pre tento daný graf (ručne) zapíšte množinu vrcholov a množinu hrán
  • graf
_images/32_9.png
  • odpovedzte áno/nie:
    • je tento graf orientovaný?
    • je tento graf súvislý?
    • je tento graf ohodnotený?
    • je tento graf acyklický?
  • ručne zapíšte nejakú cestu (postupnosť vrcholov) z vrcholu 0 do vrcholu 3
  1. Zapíšte graf z úlohy (1) v zadanej reprezentácii
  • pole množín susedností
graf = [...]
  • asociatívne pole množín susedností
graf = {...}
  1. Nakreslite graf (na papieri), ktorý zodpovedá tejto reprezentácii:
  • tabuľka susedností:
A B C D E F
A   7 5     1
B 2     7 3  
C   2       8
D 1       2 4
E 6     5    
F   1     8  
  • koľko vrcholov a koľko hrán má tento graf?
  1. Zapíšte graf z úlohy (3) v reprezentácii
  • asociatívne pole asociatívnych polí susedností
graf = {...}
  1. Označte vrcholy grafu na obrázku, ak poznáme jeho reprezentáciu
  • graf
_images/32_10.png
  • reprezentácia
graf = [{2, 3, 4}, {3, 4}, {0, 3, 4}, {0, 1, 2}, {0, 1, 2, 5}, {4}]
  • odpovedzte áno/nie:
    • je tento graf orientovaný?
    • je tento graf súvislý?
    • je tento graf ohodnotený?
    • je tento graf acyklický?
  1. Prepíšte graf z úlohy (5) do reprezentácie
  • matica susedností:
graf = [[...], ...]
  1. Podľa vzoru triedy Graf pre jednu z reprezentácií (napr. „pole množín susedností“) zapíšte metódy pre reprezentáciu
  • matica susedností:
class Graf:

    def __init__(self, n):              # n je pocet vrcholov, t.j. velkost matice
        self.pole = [...]               # zadefinuje prazdny graf (v matici su same 0)

    def pridaj_hranu(self, v1, v2):
        ...

    def je_hrana(self, v1, v2):
        return ...

    def daj_vrcholy(self):              # vrati mnozinu cisel vrcholov
        return ...

    def daj_hrany(self):                # vrati mnozinu usporiadanych dvojic
        return ...

    def stupen(self, v=None):           # zisti stupen vrcholu alebo celeho grafu
        if v is not None:
            return ...
        return ...

    def __str__(self):
        return 'vrcholy: {}\nhrany: {}'.format(self.daj_vrcholy(), self.daj_hrany())
  1. Zadefinujte inštanciu triedy z úlohy (7) tak, aby zodpovedala grafu z úloh (5) a (6)
  • napr.
graf = Graf(...)
graf.pridaj_hranu(...)
...
for i in range(len(graf.daj_vrcholy())):
    print('stupen vrcholu', i, 'je', graf.stupen(i))
  1. Do triedy Graf z úlohy (7) dopíšte zadané metódy a otestujte ich na grafe z úlohy (8)
  • je_neorientovany() zistí, či je graf orientovaný (vtedy vráti True):
class Graf:
    ...

    def je_neorientovany(self):
        return ...
  • trojuholniky() vypíše všetky také trojice vrcholov, ktoré sú navzájom spojené hranami oboma smermi každý s každým
class Graf:
    ...

    def trojuholniky(self):
        print(...)
  1. Do triedy Graf z prednášky, ktorá definuje reprezentáciu asociatívne pole množín susedností dodefinujte metódy na vykreslenie grafu
  • napr.
class Graf:
    canvas = None

    class Vrchol:
        def __init__(self, meno, x, y):
            self.meno = meno
            self.sus = set()
            self.x, self.y = x, y

        ...

        def kresli(self):           # vykresli vrchol ako kruh s textom
            ...

        def kresli_hranu(self, vrchol2):           # vykresli hranu k vrchol2
            ...                                    # netreba kreslit sipky

    #-------

    def __init__(self):
        self.pole = {}

    def pridaj_vrchol(self, meno, x, y):
        ...

    ...

    def kresli(self):               # vykresli cely graf
        ...
  1. Do triedy z úlohy (10) doprogramujte inicializáciu __init__() tak, aby sa popis grafu mohol prečítať z textového súboru
  • inicializácia grafu
class Graf:
    ...

    #-------

    def __init__(self, meno_suboru=None):
        self.pole = {...}
  • textový súbor by mohol mať napr. takýto formát - každý riadok popisuje jeden vrchol:
meno x y zoznam_mien_susedov
  • zadefinujte 2 súbory pre grafy z úloh (1) a (5) tak, aby sa výsledné obrázky čo najviac podobali, napr. súbor pre graf z úlohy (5) môže začínať týmito dvoma riadkami:
0 130 130 2 3 4
1 50 50 3 4

32.3. Domáce zadanie

Vytvoriť dátovú štruktúru Graf, ktorá bude implementovať graf reprezentovaný ako množina hrán:

class Graf:
    def __init__(self, meno_suboru):
        self.graf = set()
        ...

    def pridaj_hranu(self, v1, v2):
        ...

    def je_hrana(self, v1, v2):
        return False

    def daj_vrcholy(self):
        return set()

    def daj_hrany(self):
        return set()

    def uloz(self, meno_suboru, typ=1):
        ...

V triede môžete dodefinovať ďalšie pomocné metódy ale nie ďalšie atribúty s hodnotami. Trieda dokáže pracovať s týmito tromi typmi súborov:

  • typ=1 označuje takýto tvar: …

    • súbor začína riadkom: #1
    • každý ďalší riadok popisuje jeden vrchol: meno vrcholu a zoznam mien jeho susedov
    • riadky môžu nasledovať v ľubovoľnom poradí a aj zoznam mien susedov môže byť v ľubovoľnom poradí
    • meno vrcholu je ľubovoľný reťazec, ktorý neobsahuje medzeru
    • napr.
    #1
    a b c d e f
    b c e
    c d
    d e
    e f
    f c g h
    g f h
    h f g
    
  • typ=2 označuje takýto tvar: …

    • súbor začína riadkom: #2
    • každý ďalší riadok popisuje jednu hranu ako dvojicu mien vrcholov oddelených medzerou
    • riadky môžu nasledovať v ľubovoľnom poradí
    • meno vrcholu je ľubovoľný reťazec, ktorý neobsahuje medzeru
    • napr.
    #2
    a c
    a b
    a e
    a d
    a f
    b c
    b e
    c d
    d e
    e f
    f g
    f c
    f h
    g h
    g f
    h g
    h f
    
  • typ=3 označuje takýto tvar: …

    • súbor začína riadkom: #3
    • ďalší riadok obsahuje zoznam mien všetkých vrcholov v nejakom poradí
    • všetky ďalšie riadky popisujú maticu susedností, pričom poradie vrcholov je dané prvým riadkom súboru
    • meno vrcholu je ľubovoľný reťazec, ktorý neobsahuje medzeru
    • napr.
    #3
    a b c d e f g h
    0 1 1 1 1 1 0 0
    0 0 1 0 1 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 0 1 0 0 0
    0 0 0 0 0 1 0 0
    0 0 1 0 0 0 1 1
    0 0 0 0 0 1 0 1
    0 0 0 0 0 1 1 0
    

Graf sa inicializuje ľubovoľným z týchto formátov (rozpozná sa z prvého riadku súboru). Graf sa dokáže zapísať do súboru ľubovoľným z týchto formátov.

Všetky 3 ukážkové súbory vytvoria rovnaký graf.

Obmedzenia

  • vaše riešenie odovzdajte v súbore uloha9.py, pričom sa v ňom bude nachádzať len jedna definícia triedy Graf.

  • prvé dva riadky tohto súboru budú obsahovať:

    # autor: Janko Hrasko
    # uloha: 9. domace zadanie graf
    
  • zrejme ako autora uvediete svoje meno

  • atribút graf v triede Graf musí obsahovať reprezentáciu grafu množinou hrán (typu set, pričom hrany sú dvojice mien vrcholov, t.j. tuple)

  • váš program by nemal počas testovania testovačom nič vypisovať (žiadne vaše testovacie print())

  • testovač bude spúšťať vašu definíciu triedy s rôznymi textovými súbormi, ktoré si môžete stiahnuť z L.I.S.T.u