algoritmi per la planarità di grafi
disegni planari di grafi
disegno non planare di
un grafo
disegno planare dello
stesso grafo
1
un grafo “non planare”
(che cioè non ammette un disegno planare)
due (famosi) grafi non planari
K3,3
grafo completo bipartito
di sei nodi
K5
grafo completo di
cinque nodi
2
(tutti) i grafi non planari
kuratowsky (1930): un grafo non planare contiene al suo
interno un sottografo “riconducibile” ad un
K5 o ad un K3,3
cosa vuol dire “riconducibile”?
K5
trova il K3,3
1
2
3
2
4
5
3
6
7
4
5
K3,3
6
7
3
perché ci piacciono i grafi planari (1)
le intersezioni generano equivoci
perché ci piacciono i grafi planari (2)
eulero: se un grafo con n nodi ed m archi è planare,
allora m ≤ 3n-6
se il grafo è planare, fare una operazione su ogni arco
costa* quanto fare una operazione su ogni nodo
* = in termini di complessità asintotica
esempi di operazioni che vorremmo poter eseguire sugli archi:
•
•
•
•
etichettare ogni arco con un valore
percorrere ogni arco
memorizzare tutti gli archi in una lista
...
4
problemi sulla planarità
(1) test di planarità: dato un grafo, dire se è planare
(2) disegno planare: dato un grafo, trovare (ammesso
che esista) un suo disegno planare
ovviamente risolvere (2) equivale ad aver trovato una
risposta anche ad (1)
vorremmo poter risolvere questi problemi
economizzando le risorse di calcolo
un po’ di storia del test di planarità
• auslander e parter (1961): algoritmo quadratico
• hopcroft tarjan (1974): primo algoritmo a complessità
lineare
• lempel, even e cederbaum (1966) + booth e luecker
(1976): algoritmo complessivamente lineare, usa delle
strutture dati dette pq-trees
• de fraisseix e rosenstiehl (mai pubblicato): costruttivo
basato sulla visita in profondità del grafo (dfs)
• shih e hsu (1993): costruttivo, lineare, basato sulla dfs
• boyer e myrvold (1999): costruttivo, lineare basato
sulla dfs
5
side effects
• primi lavori fondamentali sulla complessità
computazionale asintotica
• strutture di dati
• vari problemi fondamentali risolti:
ü connettività
ü 2-connettività
ü 3-connettività
algoritmo di auslander e parter
problema:
planarità
istanza:
grafo G
predicato:
G è planare?
6
C
7
P1
P2
8
P3
P4
9
P5
P6
10
v
C
γ
π
u
P3
C
P4
P1
P5
P6
P2
11
P3
P1
P4
P5
P6
P2
P7
P3
C
P4
P1
P5
P6
P2
12
P7
P3
P4
P1
P5
P6
P2
P1
13
C
14
grafi biconnessi
cut-vertex
grafo non biconnesso
(ha un cut-vertex)
blocchi = sottografi biconnessi
(privi di cut-vertex)
block cut-vertex tree
block
cut-vertex
tree
determiniamo la planarità di ogni blocco (componente
biconnessa) indipendentemente
15
algoritmo complessivo
1) decomporre un grafo arbitrario nelle sue componenti
biconnesse (possiamo farlo in tempo lineare, come?)
2) planarizzare ogni componente biconnessa
algoritmo di boyer e myrvold
un metodo per trovare (se esiste) un disegno planare di
un grafo in tempo lineare
che cosa significa praticamente “tempo lineare”?
significa che posso compiere operazioni sugli oggetti in
input (nodi ed archi) un numero limitato di volte
(1,2,3,…,k)
intuitivamente: quando ho già considerato un oggetto
non posso più tornare sui miei passi
16
ci basta un “embedding”
è facile trovare un disegno planare di un grafo una volta
noto l’ordine circolare di incidenza degli archi sui nodi
(detto “embedding”)
d
3
d
b 1
1
3
e
a
2
b
a
c
e
5
4
f
2
5
embedding
1:
2:
3:
4:
5:
c
4
f
a, b, d
b, c
d, e
c, f
f, a, e
ingredienti
dfs = depth first search = visita in profondità del grafo
ci aiuterà a dare una struttura al grafo
struttura dati efficiente per rappresentare componenti
biconnesse (ed i loro embedding)
17
dfs - depth first search
a
a
ee
f
d
d
d
cc
c
f
b
b
e
gg
g
proprietà del dfs-tree
a
d
c
b
g
f
e
una fronda collega un nodo con un suo antenato
18
dfs-tree e connettività
root
a
c
root
a
b
c
biforcazione alla radice
⇓
⇓
b
il nodo a è sicuramente
un cut-vertex
il grafo non sarebbe biconnesso
etichettatura dei nodi
1
2
3
4
5
6
8
9
7
10
19
sketch dell’algoritmo (1)
1
1
2
2
3
4
3
8
3
9
7
5
10
3
8
4
8
4
5
6
2
9
5
9
5
6
10
7
sketch dell’algoritmo (2)
1
1
2
2
3
4
3
8
3
9
7
5
10
6
3
8
4
8
4
5
6
2
9
5
5
9
10
7
20
sketch dell’algoritmo (3)
1
1
2
2
2
3
3
4
3
8
9
7
6
5
10
8
8
4
5
3
9
5
9
10
7
6
sketch dell’algoritmo (4)
1
1
2
2
2
3
3
4
6
3
8
4
5
9
7
3
5
10
8
8
9
5
7
9
10
6
21
sketch dell’algoritmo (5)
1
1
2
2
2
3
3
4
3
8
8
4
5
9
7
6
3
5
10
9
9
5
10
7
6
sketch dell’algoritmo (6)
1
1
2
2
2
3
3
4
4
5
6
3
8
9
7
5
10
3
8
9
9
5
7
10
6
22
sketch dell’algoritmo (7)
1
1
2
2
2
3
3
4
4
8
5
8
9
5
9
7
6
3
5
10
9
7
10
6
sketch dell’algoritmo (8)
1
1
2
2
2
3
3
4
5
6
4
8
7
5
10
8
9
5
9
3
7
9
10
6
23
sketch dell’algoritmo (9)
1
1
2
2
2
3
3
4
10
5
9
7
6
9
4
8
5
8
7
5
10
6
sketch dell’algoritmo (10)
1
1
2
2
2
3
3
4
5
6
4
8
9
10
5
9
7
8
5
10
7
6
24
sketch dell’algoritmo (11)
1
1
2
2
3
3
4
6
4
8
5
9
10
5
9
7
8
10
6
7
fusione delle componenti biconnesse
1
1
2
2
3
3
3
4
5
4
7
5
7
6
6
25
fusione non leggittima
1
1
2
2
3
3
3
4
5
4
7
5
7
6
6
ribaltamento di una componente
1
1
2
2
3
3
3
4
5
7
7
5
4
6
6
26
problemi
• determinare (in tempo costante) se un nodo sia
“attivo”, cioè debba rimanere sul bordo esterno della
componente biconnessa (pena la perdita della
planarità)
• trovare il modo di ribaltare una componente
biconnessa in tempo costante
h(v) e lowpoint(v)
1 1
h(v) = minimo adiacente
2 1
lowpoint(v) =
min {h(v), lowpoint figli}
2 3
1
2 4
1
41 5
1
6
3 8
2
3 9
2
7 3
2
10
27
interpretazione intuitiva del lowpoint
lowpoint(v) =
min {h(v), lowpoint figli}
1 1
2 1
1 3
1 4
1 5
1
6
2 8
2 9
7 3
2
10
nodi attivi
supponiamo di aggiungere al disegno le fronde che
entrano nel nodo w
quali sono i nodi attivi?
1) i nodi che hanno una fronda diretta ad un antenato
di w (come faccio a capirlo? non posso controllare tutte
le fronde uscenti dal nodo)
2) i nodi a cui si attaccherà una componente
biconnessa, il cui primo nodo ha lowpoint minore di w
(come faccio a capirlo in tempo costante?)
28
ribaltamento inefficiente
supponiamo di avere l’ordinamento circolare di
incidenza degli archi sui nodi
a
1
2
b
3
d
c
4
f
1:
2:
3:
4:
5:
b
3
e
5
b, d, a
a, c
b, e
c, f
f, d, e
1:
2:
3:
4:
5:
2
d
e
5
a
1
c
4
f
a, d, b
c, a
e, b
f, c
e, d, f
lista circolare
5
2
3
4
1
0
29
rappresentazione di una componente
0
0
(0,1)
1
2
(1,0)
(0,2)
1
(1,0)
(1,2)
(2,0)
(2,1)
1
2
rappresentazione di una componente
1
1
2
(1,2)
(2,1)
2
30
rappresentazione di una componente
2
3
2
(2,3)
4
(2,6)
(2,4)
(3,2)
6
(6,2)
(4,2)
5
(4,
3)
(4,
6)
4
(6,
4)
6
(4,5)
2
6
(3,
4)
3
(3,5)
4
3
(6,5)
(5,4)
(5,3)
(5,6)
5
5
ribaltamento di una componente
0
0
1
1
2
2
2
3
4
6
6
4
3
5
5
31
ribaltamento di una componente
0
(0,1)
(1,0)
(0,2)
1
2
(2,3)
(1,2)
(2,0)
(2,4)
(3,2)
(2,1)
(2,6)
(6,2)
(4,2)
2
(3,
4)
3
(4,
3)
(3,5)
4
(4,5)
(4,
6)
(6,
4)
6
(6,5)
(5,4)
(5,3)
(5,6)
5
fusione di due componenti
0
(0,1)
(1,0)
(0,5)
(0,2)
(2,3)
1
(1,2)
(3,2)
(2,0)
3
2
(3,
4)
(4,
3)
(3,5)
1
2
5
4
(5,4)
(5,3)
3
(4,
6)
(6,
4)
6
(4,5)
0
4
(6,2)
(4,2)
(2,1)
6
(2,6)
(2,4)
(5,0)
(6,5)
(5,6)
5
32