Torna a Matematica
Teoria dei grafi e algoritmi
I grafi rappresentano oggetti collegati: reti, mappe, dipendenze, amicizie, percorsi e flussi.
Interattivo
Prova subito
Modifica i dati e controlla risultato e passaggi senza aspettare il server.
- Con 6 nodi un grafo semplice puo avere al massimo 15 archi.
- Densita = archi / massimo = 8 / 15.
- Potrebbe essere connesso, serve controllare come sono disposti gli archi.
Teoria
- Teoria dei grafi e algoritmi
- Matematica Concetto Idea Algoritmo collegato Nodo Un oggetto del grafo.
- Persona, server, pagina.
- Arco Collegamento tra nodi.
- Cammino minimo Percorso meno costoso.
- Flusso Quanto puo passare in una rete.
- In un grafo non orientato, un arco A-B si puo percorrere in entrambe le direzioni.
- BFS trova cammini minimi quando tutti gli archi hanno lo stesso costo.
Esempi
- Un nodo ha archi verso 4 altri nodi.
- Qual e il suo grado
- In un grafo orientato, A -> B implica sempre B -> A
- Un albero con 6 nodi quanti archi ha