Operacijske raziskave

« nazaj

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

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.