Riešenie úloh 9. cvičenia


  1. Riešenie:

    • graf je orientovaný, súvislý, neohodnotený, cyklický

    • cesta z 0 do 3: [0, 1, 5, 4, 6, 3]

    • cykly: [5, 4, 7, 8, 5], [5, 4, 7, 0, 1, 5], [3, 1, 5, 4, 6, 3]


  1. Riešenie:

    # zoznam množín susedností
    graf = [{1}, {5}, {5}, {1}, {6, 7}, {4, 2}, {3}, {0, 8}, {5}]
    # asociatívne pole množín susedností
    graf = {0: {1}, 1: {5}, 2: {5}, 3: {1}, 4: {6, 7}, 5: {2, 4}, 6: {3}, 7: {0, 8}, 8: {5}}
    

  1. Riešenie:

    ../../_images/l09_11.png
    • graf je orientovaný, má 6 vrcholov a 15 hrán


  1. Riešenie:

    graf = {'A': {'B': 7, 'C': 5, 'F': 1},
            'B': {'A': 2, 'D': 7, 'E': 3},
            'C': {'B': 2, 'F': 8},
            'D': {'A': 1, 'E': 2, 'F': 4},
            'E': {'A': 6, 'D': 5},
            'F': {'B': 1, 'E': 8}}
    

  1. Riešenie (jedno z dvoch možných):

    ../../_images/l09_12.png
    • graf je neorientovaný, súvislý, neohodnotený, cyklický


  1. Riešenie:

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

  1. Riešenie:

    class Graf:
    
        def __init__(self, n):                          # n je počet vrcholov, t.j. veľkosť matice
            self.matica = [[0] * n for _ in range(n)]   # zadefinuje prázdny graf (v matici sú samé 0)
    
        def pridaj_hranu(self, v1, v2):
            self.matica[v1][v2] = 1
    
        def je_hrana(self, v1, v2):
            return self.matica[v1][v2] == 1
    
        def daj_vrcholy(self):              # vráti množinu čísel vrcholov
            return set(range(len(self.matica)))
    
        def daj_hrany(self):                # vráti množinu usporiadaných dvojíc
            return {(i, j) for i in self.vrcholy() for j in self.vrcholy() if self.je_hrana(i, j)}
    
        def stupen(self, v1=None):          # zistí stupeň vrcholu alebo celého grafu
            if v1 is not None:
                return sum(self.matica[v1])
            return sum([sum(riadok) for riadok in self.matica])
    
        def __str__(self):
            return f'vrcholy: {self.daj_vrcholy()}\nhrany: {self.daj_hrany()}'
    

  1. Riešenie:

    graf = Graf(6)
    hrany = ((0, 2), (0, 3), (0, 4), (1, 3), (1, 4), (2, 0),
             (2, 3), (2, 4), (3, 0), (3, 1), (3, 2), (4, 0),
             (4, 1), (4, 2), (4, 5), (5, 4))
    for i, j in hrany:
        graf.pridaj_hranu(i, j)
    

  1. Riešenie:

    class Graf:
        ...
    
        def je_neorientovany(self):
            hrany = self.daj_hrany()
            for i, j in hrany:
                if (j, i) not in hrany:
                    return False
            return True
    
        def trojuholniky(self):
            hrany = self.daj_hrany()
            for i, j in hrany:
                if i < j and (j, i) in hrany:
                    for k in self.daj_vrcholy():
                        if j < k and {(i, k), (k, i), (j, k), (k, j)} <= hrany:
                            print(i, j, k)
    

  1. Riešenie:

    import tkinter
    
    class Graf:
    
        class Vrchol:
            canvas = None
    
            def __init__(self, meno, x, y):
                self.meno = meno
                self.sus = set()
                self.xy = x, y
    
            def kresli(self):
                x, y = self.xy
                self.canvas.create_oval(x-10, y-10, x+10, y+10, fill='lightgray')
                self.canvas.create_text(x, y, text=self.meno)
    
        #----------------------------------------------
    
        def __init__(self):
            self.vrcholy = {}
            self.canvas = tkinter.Canvas(bg='white', width=600, height=600)
            self.canvas.pack()
            self.Vrchol.canvas = self.canvas
    
        def pridaj_vrchol(self, meno, x, y):
            self.vrcholy[meno] = self.Vrchol(meno, x, y)
    
        def pridaj_hranu(self, meno1, meno2):
            self.vrcholy[meno1].sus.add(meno2)
            self.vrcholy[meno2].sus.add(meno1)
    
        def je_hrana(self, meno1, meno2):
            return meno2 in self.vrcholy[meno1].sus
    
        def kresli_hranu(self, meno1, meno2):
            self.canvas.create_line(self.vrcholy[meno1].xy, self.vrcholy[meno2].xy, width=3, fill='gray')
    
        def kresli(self):
            for meno1, vrchol in self.vrcholy.items():
                for meno2 in vrchol.sus:
                    self.kresli_hranu(meno1, meno2)
            for vrchol in self.vrcholy.values():
                vrchol.kresli()
    

    Otestujeme s grafom z (5) úlohy:

    graf = Graf()
    graf.pridaj_vrchol(0, 130, 130)
    graf.pridaj_vrchol(1, 50, 50)
    graf.pridaj_vrchol(2, 200, 200)
    graf.pridaj_vrchol(3, 40, 160)
    graf.pridaj_vrchol(4, 140, 50)
    graf.pridaj_vrchol(5, 220, 50)
    for i, j in ((0, 2), (0, 3), (0, 4), (1, 3),
                 (1, 4), (2, 3), (2, 4), (4, 5)):
        graf.pridaj_hranu(i, j)
    graf.kresli()
    

  1. Riešenie:

    class Graf:
    
        class Vrchol:
            ...
    
        #----------------------------------------------
    
        def __init__(self, meno_suboru=None):
            self.vrcholy = {}
            if meno_suboru is not None:
                with open(meno_suboru, 'r') as txt:
                    for riadok in txt.readlines():
                        meno, x, y, *sus = riadok.split()
                        self.vrcholy[meno] = self.Vrchol(meno, int(x), int(y))
                        self.vrcholy[meno].sus = set(sus)
            self.canvas = tkinter.Canvas(bg='white', width=600, height=600)
            self.canvas.pack()
            self.Vrchol.canvas = self.canvas
    

    Pre graf z úlohy (5) vytvoríme, napríklad takýto textový súbor:

    0 130 130 2 3 4
    1 50 50 3 4
    2 200 200 0 3 4
    3 40 160 0 1 2
    4 140 50 0 1 2 5
    5 220 50 4
    

    a spustíme:

    graf = Graf('graf5.txt')
    graf.kresli()
    

    Ak by sme chceli pre graf z úlohy (1) kresliť aj šípky, môžeme opraviť metódy:

    class Graf:
    
        ...
    
        def kresli_hranu(self, meno1, meno2, sipka=False):
            if sipka:
                r = 20
                x1, y1, x2, y2 = *self.vrcholy[meno1].xy, *self.vrcholy[meno2].xy
                d = ((x1-x2)**2+(y1-y2)**2)**.5
                xx, yy = (x2-x1)*r/d, (y2-y1)*r/d
                self.canvas.create_line(x1+xx, y1+yy, x2-xx, y2-yy, width=3, fill='gray', arrow='last', arrowshape=(10, 16, 5))
            else:
                self.canvas.create_line(self.vrcholy[meno1].xy, self.vrcholy[meno2].xy, width=3, fill='gray')
    
        def kresli(self, sipka=False):
            for meno1, vrchol in self.vrcholy.items():
                for meno2 in vrchol.sus:
                    self.kresli_hranu(meno1, meno2, sipka)
            for vrchol in self.vrcholy.values():
                vrchol.kresli()
    

    Teraz môžeme vytvoriť, napríklad takýto textový súbor:

    0 50 50 1
    1 130 50 5
    2 210 50 5
    3 50 130 1
    4 130 130 6 7
    5 210 130 4 2
    6 50 210 3
    7 130 210 0 8
    8 210 210 5
    

    a po otestovaní:

    graf = Graf('graf1.txt')
    graf.kresli(True)
    

    dostaneme obrázok:

    ../../_images/l09_13.png