Sottografo
Il sottografo di un grafo G è un altro grafo che contiene solo nodi e archi presenti in G.
Più formalmente, se G è un grafo, allora un sottografo di G è un grafo S tale che ogni nodo di S è anche un nodo di G, e ogni arco di S è anche un arco di G.
Ciò significa che un sottografo rappresenta una porzione del grafo originale.
Ci sono diversi tipi di sottografi, inclusi sottografi indotti, sottografi sparsi, e sottografi completi, ciascuno con le proprie specifiche proprietà e applicazioni.
Ad esempio, un sottografo indotto è ottenuto prendendo un sottoinsieme dei nodi di G e tutti gli archi di G che collegano questi nodi. Questo tipo di sottografo è particolarmente importante per studiare le proprietà locali di un grafo.
La nozione di sottografo è utile in molte applicazioni pratiche, dove i sottografi possono essere utilizzati per semplificare i problemi o trovare strutture significative all'interno di reti più grandi.
Esempio
Immaginiamo di avere un grafo G che rappresenta le città di un paese, dove ogni città è un nodo e ogni strada che collega due città è un arco.
L'insieme dei vertici V(G) e degli archi E(G) del grafo G sono i seguenti:
$$ V(G) = \{ A,B,C,D,E,F,G,H \} $$
$$ E(G) = \{ AB, AD, BC, CG, EG, EF, ED, DF, DH, FH \} $$
Supponiamo di voler analizzare solo un'area specifica di questo paese, diciamo il nord.
Se selezioniamo solo le città situate nel nord e le strade che le collegano, otteniamo un sottografo S del grafo originale.
Questo sottografo contiene meno nodi e archi rispetto al grafo completo, ma mantiene le relazioni esistenti tra le città selezionate.
$$ V(S) = \{ A, D, E, F, H \} $$
$$ E(G) = \{ AE, AD, ED, EF, DF, DH, FH \} $$
Nel sottografo l'insieme dei vertici V(S) e degli archi E(G) sono sottoinsiemi del grafo iniziale.
$$ V(S) \subseteq V(G) $$
$$ E(S) \subseteq E(G) $$
Questo esempio illustra come un sottografo possa essere utilizzato per concentrarsi su una porzione specifica di una rete più grande, semplificando l'analisi senza perdere le informazioni cruciali sulle connessioni tra gli elementi selezionati.
