lunedì, dicembre 10, 2007

grafi connessi e numerabili

ho scoperto un fenomeno veramente sorprendente. ricordo che un grafo è localmente numerabile se l'insieme di lati che connettono due nodi è numerabile per ogni coppia di nodi. ricordo anche che un grafo è connesso se fra ogni due nodi esiste un cammino di lunghezza finita.

Teorema
Sia G un grafo. Se G è localmente numerabile e connesso, allora G è numerabile.

Dimostrazione
Si fissi un nodo arbitrario v e si definisca V_n l'insieme dei nodi distanti n da v.

A causa della locale numerabilità, V_n stesso è numerabile, e dato che G è connesso, allora

V=\bigcup_{n \in \mathbb N} V_n

è un insieme numerabile in quanto unione numerabile di insiemi numerabili.

Dato che G è localmente numerabile, allora fra ogni due lati ci sono al massimo un insieme numerabile di lati. Quindi G ha al massimo NxNxN lati, e quindi G è numerabile, q.e.d..

domanda di oggi:

Si può usare un argomento simile per dedurre la numerabilità dall'irridicubilità?

secondo me, si.

ps: il concetto di connessione per cammini e di connessione topologica sono equivalenti per un grafo!

Nessun commento: