Ciao a tutti. Qualcuno potrebbe aiutarmi nella risoluzione del seguente esercizio: Ad un tavolo circolare si siedono 2n persone; ognuno è amico di almeno n persone. Dimostrare che si possono sedere di modo che due posti vicini siano sempre occupati da due amici.
L'esercizio richiede una dimostrazione usando i grafi.
Vi ringrazio
Esercizio grafi
Re: Esercizio grafi
Costruiamo un grafo dove i vertici sono le persone e gli archi la relazione di amicizia.
Se trovassimo un cammino che visita tutti i nodi, una ed una sola volta, tornando al nodo iniziale allora avremmo la nostra disposizione. Infatti mettendo in cerchio le persone così come vengono attraversate dal cammino, otteniamo che due persone vicine sono due persone che erano collegate con un arco e cioè due amici.
Dobbiamo quindi dimostrare che esiste un cammino del genere, che viene detto ciclo hamiltoniano. Non sono un esperto di grafici ma mi sembra che le condizioni del problemi ci facciano rientrare nelle ipotesi di alcuni teoremi che dimostrano proprio questa cosa.
Vedi qui:
https://it.wikipedia.org/wiki/Cammino_hamiltoniano
Se trovassimo un cammino che visita tutti i nodi, una ed una sola volta, tornando al nodo iniziale allora avremmo la nostra disposizione. Infatti mettendo in cerchio le persone così come vengono attraversate dal cammino, otteniamo che due persone vicine sono due persone che erano collegate con un arco e cioè due amici.
Dobbiamo quindi dimostrare che esiste un cammino del genere, che viene detto ciclo hamiltoniano. Non sono un esperto di grafici ma mi sembra che le condizioni del problemi ci facciano rientrare nelle ipotesi di alcuni teoremi che dimostrano proprio questa cosa.
Vedi qui:
https://it.wikipedia.org/wiki/Cammino_hamiltoniano