Utente:SilsisScalaZarli/Connessione dei grafi

Grafo connesso

Un grafo G si dice connesso se due suoi vertici qualsiasi sono connessi in G, cioè se sono collegati da un cammino. Si dice componente connessa di un grafo G un sottografo connesso massimale di G, cioe' un sottografo di G che sia connesso e non sia propriamente contenuto in un sottografo connesso di G. (vedere figura da inserire).

File:Grafo1.bmp.jpg

G grafo connesso H grafo non connesso con tre componenti

Una pista tale che $v_{0}=v_{k}$ e $v_{1},v_{2},...,v_{k}$ (vertici) sono distinti dicesi ciclo elementare.

Si definisce vertice di taglio del grafo G un vertice v di G tale che il numero di componenti del grafo G-v è maggiore del numero di componenti di G.

Un sottografo di G che sia connesso e privo di vertici di taglio e che non sia propriamente contenuto in nessuno sottografo di G anch'esso connesso e privo di vertici di taglio si dice blocco. Gli spigoli $e_{1},e_{2},e_{3}$ del grafo G mostrato in figura, con i loro estremi, sono blocchi di G, mentre lo spigolo a non è un blocco essendo propriamente contenuto nel triangolo T( T è connesso e privo di vertici di taglio). I blocchi di G sono T, $e_{1},e_{2}$ , B, D, $e_{3}$.

La rappresentazione di un grafo in $\mathbb {R} ^{2}$ o in $\mathbb {R} ^{3}$ ha un significato differente. Ci sono grafi non rappresentabili nel piano in modo che due spigoli non si intersechino in punti diversi dai loro vertici comuni. Si possono fare costruzioni in modo da evitare questo, ciò è possibile se si ricorre al concetto di realizzazione topologica di un grafo. La coppia di insiemi ottenuta trasformando i vertici e gli spigoli di G in punti e archi è la sua rappresentazione geometrica. Si possono, quindi, costruire più rappresentazioni geometriche. Allora una rappresentazione topologica di un grafo G altro non è che una rappresentazione geometrica in $\mathbb {R} ^{3}$ in modo che agli spigoli corrispondono archi aperti a due a due disgiunti, e se agli archi consideriamo pure gli estremi essendo disgiunti si intersecano solo negli estremi comuni.

Quindi quando si parlerà di grafo, faremo sempre riferimento anche alla sua rappresentazione geometrica o topologica. Dato che ogni arco è un insieme di punti ogni realizzazione topologica di un grafo è dunque un insieme di punti. Allora due qualsiasi realizzazioni topologiche di uno stesso grafo sono tra loro omeomorfe. Due qualsiasi relizzazioni topologiche di grafi che siano suddivisioni di uno stesso grafo, sono omeomorfe.

Sia G un grafo ( pensiamo anche alla rappresentazione topologica) e sia E un sottospazio di $\mathbb {R} ^{3}$, allora diremo che G può essere immerso in E se esiste un omeomorfismo di G in un sottospazio di E. Un omeomorfismo di questo tipo dicesi immersione di G in E. Se un grafo ha un'immersione in $\mathbb {R} ^{2}$ diremo che esso è un grafo planare. Non tutti i grafi si possono immergere in $\mathbb {R} ^{2}$, mentre è sempre possibile in $\mathbb {R} ^{3}$.

Ricordiamo che si dice albero un grafo connesso e privo di cicli. Chiaramente un grafo è un albero se e solo per ogni coppia di suoi vertici esiste un solo cammino che li connette. Ogni grafo connesso G possiede un sottografo che è un albero.

Abbiamo visto che è sempre possibile immergere un grafo nello spazio $\mathbb {R} ^{3}$. Si consideri la superficie sferica S appoggiata sul piano euclideo $\mathbb {R} ^{2}$ e sia $z$ il punto di S che è diametralmente opposto al punto di contatto di S con $\mathbb {R} ^{2}$. La trasformazione $t:S-{z}\rightarrow$ $\mathbb {R} ^{2}$ dell'insieme dei punti di S dal quale è stato tolto il punto z, nell'insieme dei punti $\mathbb {R} ^{2}$ ed è definita da $t(x)=y$ se e soltanto se i punti $z,x,y$ sono allineati, dove x e y sono punti di $S-{z}$ e di $\mathbb {R} ^{2}$. Questa trasformazione prende il nome di proiezione stereografica di S sul piano $\mathbb {R} ^{2}$ dal punto(polo) z. La proiezione stereografica è un'applicazione invertibile dell'insieme dei punti della superficie sferica privata del punto z nell'insieme dei punti del piano euclideo. Ma è più in generale un omeomorfismo, e allora la sfera privata di un punto ed il piano sono topologicamente equivalenti.

Un grafo planare è per definizione un grafo avente immersione nel piano. Poiché il piano euclideo è omeomorfo alla sfera privata di un punto, possiamo dire che un grafo G è planare se si può immergere in una superficie sferica S. Il risultato si può invertire in generale, cioè se abbiamo un grafo su una superficie sferica esso è senz'altro planare.

Categoria:Teoria dei grafi