Operacijske raziskave

« nazaj

Operacijske raziskave - vaje 20.4.2020

---

Algoritmi na grafih

Graf: $G = (V, E)$

\[\begin{aligned} n &= |V| \\ m &= |E| + |V| \\ d(u) &= |\{\{u, v\} \in E \mid v \in V\}| \\ d^+(u) &= |\{(u, v) \in E \mid v \in V\}| \\ d^-(u) &= |\{(u, v) \in E \mid v \in V\}| \end{aligned}\]

Predstavitev grafa:

• seznami sosedov
• matrika sosednosti

class Graf:
    pass

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

G = Graf()

---

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)"
        G.A[u][v] = 1
        G.A[v][u] = 1

    def brisiPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        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):
        "Časovna zahtevnost pregleda: O(n)"
        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)"
        G.S[u].add(v)
        G.S[v].add(u)

    def brisiPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        if v not in 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):
        "Časovna zahtevnost pregleda: O(n)"
        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(Digraf, MatricniGraf):
    "Prostorska zahtevnost: O(n^2)"

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

    def brisiPovezavo(G, u, v):
        "Časovna zahtevnost: O(1)"
        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(Digraf, MnozicniGraf):
    "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)"
        G.S[u].add(v)
        G.T[v].add(u)

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

    def brisiVozlisce(G, u):
        "Časovna zahtevnost: O(d+(u) + 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] == 1:
                    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 G
        """
        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) # hitreje: beleži 
            if len(s) == n - 1:    # število sosedov
                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.