OliForum Matematico

Allora, c\'è un grafo (non orientato) in cui ogni nodo ha esattamente 3 archi. Si vogliono colorare i suoi nodi con 2 colori, in modo che ad ogni nodo sia collegato al massimo un altro nodo dello stesso colore. Dimostrare che la colorazione è possibile.[addsig]

si può usare l\'induzione sul numero di nodi, forse...?

rettifico...
 mi sembra che il numero di nodi sia necessariamente multiplo di 4... forse, dimostrato questo, si potrà usare l\'induzione...

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-12-09 19:45, talpuz wrote:
 rettifico...
 mi sembra che il numero di nodi sia necessariamente multiplo di 4... forse, dimostrato questo, si potrà usare l\'induzione...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 multiplo di 2

già già...
 infatti in un grafo il numero di vertici di valenza dispari deve essere pari, e da questo segue che nel nostro grafo i nodi sono in numero pari.

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-12-09 20:31, talpuz wrote:
 già già...
 infatti in un grafo il numero di vertici di valenza dispari deve essere pari, e da questo segue che nel nostro grafo i nodi sono in numero pari.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Sì, ma questo non esclude che debbano essere anche multipli di 4, e non basta per confutare quello che dicevi nel primo post!

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-12-09 21:05, Antimateria wrote:
 Sì, ma questo non esclude che debbano essere anche multipli di 4
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 beh, non è difficile costruirne uno con 6 nodi (che hanno 3 archi ciascuno)
 che quindi fa da controesempio...

e comunque l\'idea è questa: con 4 si può fare, e bon
 supponiamo che per un grafo con 2n nodi la colorazione sia possibile;
 prendiamo un grafo con 2n+2 nodi, ne scegliamo 2 collegati e li stacchiamo brutalmente dal grafo, tagliando anche gli archi corrispondenti (che sono 5); il grafo che rimane ricollegando adeguatamente tra loro gli n nodi superstiti è colorabile per ipotesi induttiva.
 
 resta da dimostrare che ricomponendo il tutto la colorazione funziona...

Fra tutte le possibili colorazioni del grafo con due colori, consideriamo quella che minimizza il numero di lati (o archi) che hanno i due vertici dello stesso colore (ogni arco collega 2 vertici). questa colarazione risolve il problema ed è sempre possibile.
 Poniamo per assurdo che questa colorazione non risolva il problema, avremo almeno un vertice collegato a due o tre vertici del medesimo colore.
 vissiamo l\'attenzione su questo vertice: se è collegato a due vertici dello stesso colore il numero di lati con i vertici uguali = 2. Se questo vertice fosse dell\'altro colore i lati sarebbero = 1 (i numero di lati uguali nn collegati al vertice considerato non cambiano). per la minimalità della colorazione il vertice in questione deve essere dell\'altro colore e perciòsarà collegato ad un solo vertice dello stesso colore e non a due.
 Se invece un vertice fosse collegato a 3 uguali, è sempre assurdo (il numero di lati \"uguali\" = 3, mentre se fosse del colore inverso sarebbe =0. Per la min. deve essere per forza dell\'altro colore --> è collegato a tre vertici di colore diverso dal suo).
 Con un disegno sarebbe tutto moolto più chiaro...
 cmq, va bene?? <IMG SRC="images/forum/icons/icon_cool.gif"> <IMG SRC="images/forum/icons/icon_cool.gif">
 Ciao,Daniele!!
 
 
 [ Questo Messaggio è stato Modificato da: Shoma85 il 12-12-2003 21:23 ]

Va bene, ed è molto elegante!
 Anche per induzione si poteva fare, ma non con altrettanta immediatezza.

OliForum Matematico

Che belli i problemi sui grafi!