Inanellamento di grafi
-
MindFlyer
Inanellamento di grafi
Da ogni nodo di un grafo G non orientato partono 2k archi, con k intero positivo fissato. Dimostrare che è possibile eliminare degli archi da G in modo che da ogni nodo partano esattamente 2 archi.
Supponiamo che G sia connesso; se non lo fosse, ripetiamo il problema separatamente allo stesso identico modo per ogni sua componente connessa.
Il nostro grafo G ha tutti i nodi di grado pari, quindi è Euleriano, ed esiste un cammino che parte da un nodo e vi ritorna passando una e una volta per tutti gli archi. Quindi, fissando un verso di percorrenza di questo cammino, possiamo vedere ogni nodo come provvisto di k archi "che vi entrano" e k "che ne escono".
Sia N il numero di nodi.
Ora, immaginiamo di avere due insiemi A e B, ciascuno contenente gli N nodi del grafo; per gli elementi di A, però, consideriamo solo gli archi "uscenti"; per quelli di B solo gli archi "entranti". In questo modo avremo per ogni nodo in A k archi che ne escono, tali che ciascuno lo colleghi a un diverso elemento di B. (E ovviamente nessun arco collegherà un nodo di A al suo nodo "gemello" in B.)
Presi n elementi di A, n<=N, notiamo che a essi sono collegati tramite i nostri archi almeno n elementi distinti di B. Dai primi partiranno infatti kn archi; se questi non raggiungessero n nodi distinti in B, ce ne sarebbero per pigeonhole almeno k+1 che entrano in uno stesso nodo, impossibile.
Possiamo dunque applicare il Teorema di Hall, o lemma dei matrimoni, e "sposare" ogni elemento di A con un diverso elemento di B (due nodi "si piacciono" se hanno un arco che esce dal primo e entra nel secondo).
Adesso cancelliamo da G tutti gli archi tranne quelli che uniscono due nodi "sposati".
Otterremo un nuovo grafo in cui da ogni nodo partono esattamente due archi: uno che il nodo riceve in qualità di elemento di B, un altro (chiaramente diverso) che eredita come elemento di A.
(uhm, fatto con quaaaalche aiutino, lo ammetto
)
Il nostro grafo G ha tutti i nodi di grado pari, quindi è Euleriano, ed esiste un cammino che parte da un nodo e vi ritorna passando una e una volta per tutti gli archi. Quindi, fissando un verso di percorrenza di questo cammino, possiamo vedere ogni nodo come provvisto di k archi "che vi entrano" e k "che ne escono".
Sia N il numero di nodi.
Ora, immaginiamo di avere due insiemi A e B, ciascuno contenente gli N nodi del grafo; per gli elementi di A, però, consideriamo solo gli archi "uscenti"; per quelli di B solo gli archi "entranti". In questo modo avremo per ogni nodo in A k archi che ne escono, tali che ciascuno lo colleghi a un diverso elemento di B. (E ovviamente nessun arco collegherà un nodo di A al suo nodo "gemello" in B.)
Presi n elementi di A, n<=N, notiamo che a essi sono collegati tramite i nostri archi almeno n elementi distinti di B. Dai primi partiranno infatti kn archi; se questi non raggiungessero n nodi distinti in B, ce ne sarebbero per pigeonhole almeno k+1 che entrano in uno stesso nodo, impossibile.
Possiamo dunque applicare il Teorema di Hall, o lemma dei matrimoni, e "sposare" ogni elemento di A con un diverso elemento di B (due nodi "si piacciono" se hanno un arco che esce dal primo e entra nel secondo).
Adesso cancelliamo da G tutti gli archi tranne quelli che uniscono due nodi "sposati".
Otterremo un nuovo grafo in cui da ogni nodo partono esattamente due archi: uno che il nodo riceve in qualità di elemento di B, un altro (chiaramente diverso) che eredita come elemento di A.
(uhm, fatto con quaaaalche aiutino, lo ammetto
)-
MindFlyer
