Operacijske raziskave - vaje 19.4.2021

Podatkovne strukture za grafe

  • Graf \(G = (V, E)\)

    • \(n = \vert V \vert\)
    • \(m = \vert E \vert + \vert V \vert\)
    • neusmerjen graf: \(E \subseteq {V \choose 2} = \lbrace \lbrace u, v \rbrace \mid u, v \in V, u \ne v \rbrace\), za \(\lbrace u, v \rbrace \in E\) pišemo \(uv\)
      • \(d(u) = \vert \lbrace v \in V \mid uv \in E \rbrace \vert\)
    • usmerjen graf: \(E \subseteq V^2 = \lbrace (u, v) \mid u, v \in V\rbrace\), za \((u, v) \in E\) pišemo \(uv\)
      • \(d^+(u) = \vert \lbrace v \in V \mid uv \in E \rbrace \vert\)
      • \(d^-(u) = \vert \lbrace v \in V \mid vu \in E \rbrace \vert\)

  • Predstavitev v računalniku:

    • matrika sosednosti: \(A \in \lbrace 0, 1 \rbrace^{n \times n}\)
      • \(V = \lbrace u_1, u_2, \dots, u_n \rbrace\)
      • \(A_{ij} = 1 \iff u_i u_j \in E\)
    • slovar množic: \(\lbrace u: \lbrace v \mid uv \in E \rbrace \mid u \in V \rbrace\)
class Graf:
    pass

class Digraf(Graf):
    def izhodniSosedi(G, u):
        return G.sosedi(u)

Naloga 1

Zasnuj podatkovno strukturo za grafe, ki temelji na matrični predstavitvi. Podatkovna struktura naj ima sledeče metode:

  • __init__(G): ustvarjanje praznega grafa
  • dodajVozlisce(G, u): dodajanje novega vozlišča
  • dodajPovezavo(G, u, v): dodajanje nove povezave
  • brisiPovezavo(G, u, v): brisanje povezave
  • brisiVozlisce(G, u): brisanje vozlišča
  • sosedi(G, u): seznam sosedov danega vozlišča

Za vsako od naštetih metod podaj tudi njeno časovno zahtevnost v odvisnosti od števila vozlišč, števila povezav in stopenj vhodnih vozlišč. Oceni tudi prostorsko zahtevnost celotne strukture.

class MatricniGraf(Graf):
    "Prostorska zahtevnost: O(n^2)"

    def __init__(G):
        "Časovna zahtevnost: O(1)"
        G.A = {}
        
    def dodajVozlisce(G, u):
        "Časovna zahtevnost: O(n)"
        if u in G.A:
            return
        G.A[u] = {w: 0 for w in G.A}
        for w in G.A:
            G.A[w][u] = 0

    def dodajPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        assert u in G.A and v in G.A
        G.A[u][v] = 1
        G.A[v][u] = 1

    def brisiPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        assert u in G.A and v in G.A
        G.A[u][v] = 0
        G.A[v][u] = 0

    def brisiVozlisce(G, u):
        "Časovna zahtevnost: O(n)"
        del G.A[u]
        for w in G.A:
            del G.A[w][u]

    def vozlisca(G, u):
        return G.A.keys()

    def sosedi(G, u):
        "Časovna zahtevnost: O(n)"
        return [w for w in G.A if G.A[u][w]]

Naloga 2

Zasnuj podatkovno strukturo za grafe, ki temelji na seznamih sosedov. Zapiši metode kot pri prejšnji strukturi ter oceni njihovo časovno zahtevnost in prostorsko zahtevnost celotne strukture.

class MnozicniGraf(Graf):
    "Prostorska zahtevnost: O(m)"

    def __init__(G):
        "Časovna zahtevnost: O(1)"
        G.S = {}

    def dodajVozlisce(G, u):
        "Časovna zahtevnost: O(1)"
        if u in G.S:
            return
        G.S[u] = set()

    def dodajPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        assert u in G.S and v in G.S
        G.S[u].add(v)
        G.S[v].add(u)
        
    def brisiPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        assert u in G.S and v in G.S
        if v not G.S[u]:
            return
        G.S[u].remove(v)
        G.S[v].remove(u)

    def brisiVozlisce(G, u):
        "Časovna zahtevnost: O(d(u))"
        for w in G.S[u]:
            if w != u:
                G.S[w].remove(u)
        del G.S[u]

    def vozlisca(G, u):
        return G.S.keys()

    def sosedi(G, u):
        "Časovna zahtevnost: O(d(u))"
        return list(G.S[u])

Naloga 3

Kako moramo spremeniti prejšnji strukturi, da bosta predstavljali digrafe?

class MatricniDigraf(MatricniGraf, Digraf):
    "Prostorska zahtevnost: O(n^2)"

    def dodajPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        assert u in G.A and v in G.A
        G.A[u][v] = 1

    def brisiPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        assert u in G.A and v in G.A
        G.A[u][v] = 0
        
    def vhodniSosedi(G, u):
        "Časovna zahtevnost: O(n)"
        return [w for w in G.A if G.A[w][u]]

class MnozicniDigraf(MnozicniGraf, Digraf):
    "Prostorska zahtevnost: O(m)"

    def __init__(G):
        "Časovna zahtevnost: O(1)"
        G.S = {} # izhodni sosedi
        G.T = {} # vhodni sosedi

    def dodajVozlisce(G, u):
        "Časovna zahtevnost: O(1)"
        if u in G.S:
            return
        G.S[u] = set()
        G.T[u] = set()

    def dodajPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        assert u in G.S and v in G.S
        G.S[u].add(v)
        G.T[v].add(u)
        
    def brisiPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        assert u in G.S and v in G.S
        if v not G.S[u]:
            return
        G.S[u].remove(v)
        G.T[v].remove(u)

    def brisiVozlisce(G, u):
        "Časovna zahtevnost: O(d(u))"
        for w in G.S[u]:
            G.T[w].remove(u)
        for w in G.T[u]:
            G.S[w].remove(u)
        del G.S[u]
        del G.T[u]

    def vhodniSosedi(G, u):
        "Časovna zahtevnost: O(d-(u))"
        return list(G.T[u])

Naloga 4

Napiši algoritem, ki za vhodni graf \(G\) določi, ali ima trikotnik. Katero podatkovno strukturo za grafe boš uporabil?

class MatricniGraf(Graf):
    ...
    
    def trikotnik(G):
        "Časovna zahtevnost: O(mn)"
        for u in G.A:
            for v in G.A:
                if G.A[u][v]:
                    for w in G.A:
                        if G.A[v][w] and G.A[w][u]:
                            return True
        return False

class MnozicniGraf(Graf):
    ...
    
    def trikotnik(G):
        """
        Časovna zahtevnost: O(sum_v d(v)^2) = O(Dm),
        kjer je D največja stopnja vozlišča v grafu
        """
        for u in G.S:
            for v in G.S[u]:
                for w in G.S[v]:
                    if u in G.S[w]:
                        return True
        return False

Naloga 5

Dan je digraf \(D = (V, E)\). Pravimo, da je vozlišče \(v \in V\) zvezda digrafa \(D\), če ima izhodno povezavo do vseh ostalih vozlišč in v digrafu \(D\) ni drugih povezav. Napiši algoritem, ki poišče zvezdo danega digrafa, če ta obstaja.

class Digraf(Graf):
    ...
    
    def zvezda(G):
        n = len(G.vozlisca())
        z = None
        for u in G.vozlisca():
            s = G.izhodniSosedi(u)
            if len(s) == n-1:
                if z is not None or u in s:
                    return None
                z = u
            elif len(s) > 0:
                return None
        return z
Select a repo