owned this note
owned this note
Published
Linked with GitHub
---
tags: vaje, or, grafi
hackmd: https://hackmd.io/zDeSwaW6SJWrVrjp0pV3cw
plugins: mathjax
---
# 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$
```python
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.
```python
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.
----
```python
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?
----
```python
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]]
```
```python
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?
```python
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.
```python
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
```
Sign in with Wallet
