algoritmi per la planaritàdi grafitorlone.dia.uniroma3.it/sistelab/Patrignani1.pdf · • hopcroft...
32
1 algoritmi per la planarità di grafi algoritmi per la planarità di grafi disegni planari di grafi disegno non planare di un grafo disegno planare dello stesso grafo
Transcript of algoritmi per la planaritàdi grafitorlone.dia.uniroma3.it/sistelab/Patrignani1.pdf · • hopcroft...
1
algoritmi per la planarità di grafialgoritmi per la planarità di grafi
disegni planari di grafi
disegno non planare di un grafo
disegno planare dello stesso grafo
2
un grafo “non planare”(che cioè non ammette un disegno planare)
due (famosi) grafi non planari
K5grafo completo di
cinque nodi
K3,3
grafo completo bipartito di sei nodi
3
(tutti) i grafi non planarikuratowsky (1930): un grafo non planare contiene al suo
interno un sottografo “riconducibile” ad unK5 o ad un K3,3
K5
cosa vuol dire “riconducibile”?
trova il K3,31
6
5
7
2 4
3
2
4
6 7
5
3
K3,3
4
perché ci piacciono i grafi planari (1)
le intersezioni generano equivoci
perché ci piacciono i grafi planari (2)
se il grafo è planare, fare una operazione su ogni arco costa* quanto fare una operazione su ogni nodo
* = in termini di complessità asintotica
eulero: se un grafo con n nodi ed m archi è planare, allora m ≤ 3n-6
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• ...
5
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
6
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 parterproblema:
planarità
istanza:grafo G
predicato:G è planare?
7
C
8
P1
P2
9
P3
P4
10
P5
P6
11
C
v
u
γπ
C
P2
P1P4
P3
P5
P6
12
P2
P1P4
P3
P5
P6
C
P2
P1P4
P3
P5
P6
P7
13
P3P7
P2
P1P4
P5
P6
P1
14
C
15
grafi biconnessi
grafo non biconnesso(ha un cut-vertex)
cut-vertex
blocchi = sottografi biconnessi(privi di cut-vertex)
block cut-vertex tree
determiniamo la planarità di ogni blocco (componente biconnessa) indipendentemente
block cut-vertextree
16
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 myrvoldun 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
17
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”)
4
32
1
5
b d
ca
e
f
1: a, b, d2: b, c3: d, e4: c, f5: f, a, e
4
3
2
1
5
f
a
c
be
d
embedding
ingredientidfs = depth first search = visita in profondità del grafoci aiuterà a dare una struttura al grafo
struttura dati efficiente per rappresentare componenti biconnesse (ed i loro embedding)
18
a
f
d
a
dfs - depth first search
c
g
e
b
dd
b
g
f
e
c
bb
gg
f
e
cc
a
d
b
g
f
e
c
a
b
g
c
bb
eeed
f
a
cf c
a
de
proprietà del dfs-tree
a
d
b
g
f
e
c
una fronda collega un nodo con un suo antenato
19
dfs-tree e connettività
bc
a
biforcazione alla radice
root
⇓
bc
a
root
il nodo a è sicuramente un cut-vertex
il grafo non sarebbe biconnesso
⇓
etichettatura dei nodi
9
10
1
2
8
5
3
76
4
20
sketch dell’algoritmo (1)
9
10
1
2
8
5
3
76
4
1
2
9
8
5
3
4
6
5
7
5
4
10
9
8
33
2
sketch dell’algoritmo (2)
9
10
1
2
8
5
3
76
4
9
8
5
3
4
6
5
7
5
4
10
9
8
33
2
1
2
21
7
sketch dell’algoritmo (3)
9
10
1
2
8
5
3
76
4
9
8
5
3
4
6
510
9
8
33
2
1
2
7
sketch dell’algoritmo (4)
9
10
1
2
8
5
3
76
4
9
8
5
3
4
6
510
9
8
33
2
1
2
22
7
sketch dell’algoritmo (5)
9
10
1
2
8
5
3
76
4
9
5
3
4
6
510
9
8
33
2
1
2
7
sketch dell’algoritmo (6)
9
10
1
2
8
5
3
76
4
9
5
3
4
6
510
9
8
33
2
1
2
23
7
sketch dell’algoritmo (7)
9
10
1
2
8
5
3
76
4
95
3
4
6
510
9
8
3
2
1
2
7
sketch dell’algoritmo (8)
9
10
1
2
8
5
3
76
4
95
3
4
6
510
9
8
3
2
1
2
24
7
sketch dell’algoritmo (9)
9
10
1
2
8
5
3
76
4
5
3
4
6
5
10
8
2
9
1
2
7
sketch dell’algoritmo (10)
9
10
1
2
8
5
3
76
4
5
3
4
6
5
10
8
2
9
1
2
25
1
7
sketch dell’algoritmo (11)
9
10
1
2
8
5
3
76
4
5
3
4
6
10
8
2
9
1
75
3
4
6
2
3
1
754
6
2
3
fusione delle componenti biconnesse
26
1
75
3
4
6
2
3
1
754
6
2
3
fusione non leggittima
1
7
ribaltamento di una componente
5
3
4
6
2
3
1
457
6
2
3
27
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
1
1
2
2 3
3
23
4
1
h(v) e lowpoint(v)
h(v) = minimo adiacente
lowpoint(v) = min {h(v), lowpoint figli}
1
1
1
1 2
2
23
1
1
9
10
1
2
8
5
3
76
4
28
interpretazione intuitiva del lowpoint
lowpoint(v) = min {h(v), lowpoint figli}
1
1
1
1 2
2
23
1
1
9
10
1
2
8
5
3
76
4
nodi attivisupponiamo 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?)
29
ribaltamento inefficientesupponiamo di avere l’ordinamento circolare di incidenza degli archi sui nodi
4
32
1
54
32
1
5
a b
cd
e
f
ab
cd
e
f
1: b, d, a2: a, c3: b, e4: c, f5: f, d, e
1: a, d, b2: c, a3: e, b4: f, c5: e, d, f
lista circolare
25
4
01
3
30
0
rappresentazione di una componente
2
1(0,1)
2
(2,0)
(2,1)
(1,2)
(1,0)
0
(0,2)
1
1
(1,0)
1
rappresentazione di una componente
2
2
(2,1)
1
(1,2)
31
rappresentazione di una componente
643
5
2 (2,3)
3
5
2(2,6)
(2,4)
(4,2)
4 (4,6)
(3,2) (6,2)
(4,5)
(6,4)
(3,4)
(4,3)
(5,4)(3,5)
(5,3)
6
(6,5)
(5,6)346
5
2
0
6
ribaltamento di una componente
4
2
3
5
1
2
0
346
5
1
2
32
ribaltamento di una componente
(0,1)
2
(2,0)
(2,1)
(1,2)
(1,0)
0
(0,2)
1(2,3)
3
5
2(2,6)
(2,4)
(4,2)
4 (4,6)
(3,2) (6,2)
(4,5)
(6,4)
(3,4)
(4,3)
(5,4)(3,5)
(5,3)
6
(6,5)
(5,6)
fusione di due componenti
(0,1)
2
(2,0)
(2,1)
(1,2)
(1,0)
0
(0,2)
1(2,3)
3
5
(2,6)(2,4)
(4,2)
4 (4,6)
(3,2) (6,2)
(4,5)
(6,4)
(3,4)
(4,3)
(5,4)(3,5)
(5,3)
6
(6,5)
(5,6)
(5,0)
(0,5)
0
346
5
1
2
