Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafi - Coggle Diagram

- - - - si possono avere massimo
        n(n-1)/2 archi
  - - - rappresenta relazioni di tipo asimmetrico
        tra coppie di vertici.
        
        x è adiacente a y
    - - formato da archi che
        non hanno un orientazione
        
        relazione simmetrica
        
        x e y legati da (x,y)
        sono adiacenti
        (x,y) incidente a x e y
  - - - hamiltoniano se attraversa tutti i vertici del grafo esattamente una volta
      - eureliano se visita tutti i vertici e gli archi del grafo, attraversando gli archi esattamente una volta
      - semplice se v0,v_k-1 sono tutti distinti
  - - - ci sono almeno n-1 archi
  - - - ha esattamente n-1 archi
    - - G aciclico con n-1 archi
      - 2 vertici di G connessi da un unico cammino
      - G connesso con n-1 archi
      - G connesso minimale
      - G aciclico massimale
  - - - ciascun vertice è connesso a tutti gli altri vertici
  - - - se vi sono pochi archi,
        è detto sparso
- - - - simmetria
      - transitività
      - riflessività
  - - - per ogni coppia di vertici esiste un percorso fra loro in entrambe le direzioni
        
        relazione di equivalenza
    - - il suo corrispettivo grafo non orientato è connesso
- - - - u = F.dequeue()
        per tutti gli archi (u,v) in G
        se v non è ancora marcato
        F.enqueue(v)
        marca v
        rendi u padre di vi in T
        
        ripeti mentre F non è vuoto
  - - - backtrack per esplorare
        gli archi non visitati
        da cui v era stato ottenuto
        
        continua fino a che non vengono
        visitati tutti i vertici raggiungibili
        dal vertice sorgente s
        
        ripetuto fino a che tutti
        i vertici connessi vengono trovati
        
        ricorsione
  - - - estrai un qualsiasi vertice u da F
        visita il vertice u
        per ogni arco (u,v) in G
        se v non è ancora marcato
        marca v e aggiungi a F
        rendi u padre di v in T
        altrimenti
        eventualmente rendi u nuovo padre di di v in T
        
        ripeti mentre F!=insieme vuoto