Teorema Dilworth-like per i grafi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Teorema Dilworth-like per i grafi

Messaggio da Tibor Gallai » 02 apr 2009, 16:50

Dato un grafo G, sia $ ~\alpha (G) $ il massimo numero di suoi nodi a due a due non adiacenti.
Mostrare che i nodi di G possono essere partizionati in al più $ ~\alpha (G) $ classi in modo che, se una classe ha più di 2 elementi, questi formino un ciclo in G. Inoltre, se una classe ha esattamente 2 elementi, essi devono essere adiacenti in G.

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 07 apr 2009, 21:09

Forse la parola "Dilworth-like" ha spaventato qualcuno... In realtà non serve sapere il teorema di Dilworth per risolvere il problema, né è molto utile sapere la sua dimostrazione. E' solo che le tesi si somigliano un pochino, ma la somiglianza finisce qua.

Dò un hint: mostrare che G contiene un sottografo H della forma voluta (un ciclo, una coppia di nodi uniti, un nodo isolato), in modo che esista un nodo di H che ha vicini solo in H e non nel resto del grafo.

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 22 apr 2009, 17:01

Uhm, il mio iniziale proposito di farlo senza guardare l'hint è fallito miseramente: a questo punto, tanto vale scrivere la dimostrazione l'esistenza di H...

Prendo un punto a caso nel grafo. Lo chiamo $ P_1 $ e lo coloro di rosso. Poi passo a un vicino a caso di $ P_1 $ (che non sia già rosso), lo coloro di rosso e lo chiamo $ P_2 $. Poi passo a un vicino di $ P_2 $ (che non sia già rosso), lo coloro di rosso e lo chiamo $ P_3 $ e così via...

A un certo punto arriverò a un $ P_n $ tutti i vicini del quale sono rossi. Sia $ P_k $ il suo vicino con l'indice più piccolo. L'insieme $ H=\{ P_k,\dots ,P_n\} $ funziona (il punto che non ha vicini esterni è $ P_n $)
"Sei la Barbara della situazione!" (Tap)

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 22 apr 2009, 17:21

Yesss! 8)
Hai ragione sull'hint, volevo darne uno meno incisivo, ma non avevo idee.

Rispondi