Diario di Marco Pagnin

definizione di grafo
grafo orientato e non orientato
sottografi
grafi aciclici
cammino
ciclo
cammino semplice
cappi
grado di un vertice
- lemma della stretta di mano
grafi regolari
- 2-reg: |V| = |E|
- 3-reg: |V| pari
- 4-reg: |E| pari
- 6-reg: |V| pari ⇒ |E| pari, |V| dispari ⇒ |E| dispari
rappresentazione di grafi con matrici di adiacenza
- indici di colonna = da, di riga = a
rappresentazione di grafi con liste di adiacenza
densità di un grafo (denso/sparso)
- orientato:
  $δ = \frac{m}{n^{2}}$
- non orientato:
  $δ = \frac{m}{\frac{n (n - 1)}{2}}$
prodotto di matrici di adiacenza
- diagonale del risultato come grado del vertice
- altri valori come numero di cicli con grado k (k = numero di volte che si moltiplica la matrice)
grafo pesato
isomorfismo di grafi
grafo complementare
grafo aciclico
grafi connessi
albero
grafo completo
grafo vuoto
grafo bipartito
albero di copertura minimo (MST)
taglio
arco leggero
teorema fondamentale degli MST
1. A ⊆ E, A ⊆ MST
2. t = (S, S/V) un taglio che rispetta A
3. l'arco a che attraversa t è leggero
4. → l'arco a è sicuro per A
taglia e cuci
1. abbiamo un albero
2. aggiungiamo un arco leggero
3. otteniamo sicuramente un ciclo
4. siccome l'arco precedente è più pesante di quello appena aggiunto se lo rimuovo ottengo un MST
corollario del teorema fondamentale degli MST
1. A ⊆ E, A ⊆ MST
2. C è una componente connessa di A
3. l'arco a che collega C a un'altra componente connessa di A è leggero
4. → l'arco a è sicuro per A
Kruskal O(m logm)
- implementazione di MAKE_SET(x)
- implementazione di UNION(x, y)
- implementazione di FIND_SET(x)
Prim O(m logn)
- implementazione della coda di vertici e della funzione EXTRACT_MIN
Funzioni INIT_SINGLE_SOURCE e RELAX
Dijkstra
- con array O(n²) / O(n²)
- con heap binario O(m log n) ⇒ O(n log n) / O(n² log n)
- Dijkstra per problemi di massimizzazione
Bellman-Ford O(n²) / O(n³)
- verifica di proprietà di cicli, per esempio
  $Π_{i = 1}^{q} w (x_{i - 1}, x_{i}) < 1$
Floyd-Warshall O(n³)
Clique

Settembre 2018 Archive

NP completezza

Lista degli argomenti relativi ai grafi (per esame ASD)