Lista degli argomenti relativi ai grafi (per esame ASD)

Posted by On Filed under Algoritmi e strutture dati, Grafi
  • 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:
      δ=mn2
    • non orientato:
      δ=mnn-12
  • 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(n2) / O(n2)
    • con heap binario O(m log n) ⇒ O(n log n) / O(n2 log n)
    • Dijkstra per problemi di massimizzazione
  • Bellman-Ford O(n2) / O(n3)
    • verifica di proprietà di cicli, per esempio
      Πi=1qwxi-1xi<1
  • Floyd-Warshall O(n3)
  • Clique