Lunghezza cammini in grafi connessi

[Tibor Gallai]

Sia G un grafo connesso, in cui ogni nodo ha almeno d vicini. Mostrare che in G vi è un cammino che tocca tutti i nodi, oppure un cammino di lunghezza 2d.

[Rosinaldo]

Sia G un grafo connesso, in cui ogni nodo ha almeno d vicini. Mostrare che in G vi è un cammino che tocca tutti i nodi, oppure un cammino di lunghezza 2d.

Puoi spiegare meglio il testo,please?

[Tibor Gallai]

Uhm, penso di sì... A questo punto devo definire ogni parola.

Un grafo è un insieme finito di puntini chiamati nodi, e tra ogni coppia di nodi distinti può esserci un collegamento, o arco (un arco non può collegare un nodo con sé stesso, e tra 2 nodi può esserci al più un arco). Se tra 2 nodi vi è un collegamento, i nodi si dicono vicini, o adiacenti. Un cammino in un grafo è una sequenza di nodi distinti, ognuno dei quali è adiacente al precedente. Un grafo è connesso se, per ogni coppia di nodi distinti, vi è un cammino che li unisce.

Per vedere se hai capito, puoi provare a dimostrare un teorema più debole:
Sia G un grafo (non necessariamente connesso), in cui ogni nodo ha almeno d vicini. Mostrare che in G vi è un cammino di lunghezza d.

[federiko97]

Uhm, interessante. Una domanda: un cammino di lunghezza 2d, vuol dire che è un cammino di 2d nodi e 2d-1 archi oppure un cammino di 2d+1 nodi e 2d archi?
Perché nel primo caso penso che la tesi possa essere migliorata.

[Tibor Gallai]

Infatti intendo un cammino di 2d archi e 2d+1 nodi: la lunghezza è il numero di "passi" nel cammino. Grazie per aver sollevato la questione.
Se hai una dimostrazione, scrivila!

[federiko97]

Chiamo C il cammino di lunghezza massima. Chiamo $ v $ il numero di vertici che ne fanno parte. Invece x è, tra i vertici del cammino che sono collegati a un vertice non del cammino (o esiste o la tesi è banale), quello che più si avvicina a un'estremità. Chiamo y un vertice scelto a caso tra quelli che non appartengono a C e sono vicini a x. Ora chiamo D il grafo ottenuto cancellando i vertici di C (e gli spigoli che li toccano) al grafo di partenza. Sia E il cammino di D che parte da y di lunghezza massima. Tutti i vertici di D hanno almeno $ d+b-\lceil \frac{a}{2}\rceil $ vicini (perché sennò sarebbero vicini a due vertici consecutivi del cammino C e quindi potrei inserirli nel cammino allungandolo), quindi questo cammino contiene almeno $ d+b-\lceil \frac{a}{2}\rceil +1 $ vertici. Se io parto dal vertice del cammino di partenza "più lontano da x", poi arrivo a x, vado direttamente a y e poi faccio il cammino E, ottengo un cammino che ha $ (a-b)+(d+b-\lceil \frac{a}{2}\rceil +1) $ vertici. Visto che, essendo C il cammino più lungo, $ a\ge (a-b)+(d+b-\lceil \frac{a}{2}\rceil +1) $ cioè $ \lceil\frac{a}{2}\rceil\ge d+1 $ e quindi $ a > 2d $ da cui C ha almeno 2d spigoli.

[Tibor Gallai]

i vertici di D hanno almeno $ d+b-\lceil \frac{a}{2}\rceil $ vicini

Non so cosa sono a e b.

[federiko97]

Uhm, hai anche ragione in effetti. Comunque $ a $ è il numero di vertici di C, mentre $ b $ è la lunghezza del "sottocammino" di C che va da x all'estremo di C più vicino a x. Si capisce ora?

[Tibor Gallai]

Sì, ho capito e funziona. Bravo!!

Scrivo una soluzione alternativa, forse leggermente più contenuta.

Sia $ ~\displaystyle x_i $ l'$ ~\displaystyle i $-esimo nodo di un cammino di lunghezza massima $ ~\displaystyle P $, con $ ~\displaystyle 0\leq i \leq k $. Se $ ~\displaystyle P $ non tocca tutti i nodi, per la connessione di $ ~\displaystyle G $ esiste un nodo $ ~\displaystyle y $ distinto da ogni $ ~\displaystyle x_i $, ed adiacente ad uno di essi. Supponiamo per assurdo che $ ~\displaystyle k\leq 2d $, e mostriamo che esiste un ciclo formato da tutti gli $ ~\displaystyle x_i $. Questo accade se $ ~\displaystyle x_0 $ e $ ~\displaystyle x_k $ sono adiacenti, quindi assumiamo che non lo siano. Poiché $ ~\displaystyle P $ non è estendibile dalla parte di $ ~\displaystyle x_0 $ (o non sarebbe massimale), esso ha almeno $ ~\displaystyle d-1 $ vicini (distinti) tra gli $ ~\displaystyle x_i $, con $ ~\displaystyle 2\leq i\leq k-1 $ (che sono al più $ ~\displaystyle 2d-2 $ nodi). Similmente, $ ~\displaystyle x_k $ ha almeno $ ~\displaystyle d-1 $ vicini (distinti) tra gli $ ~\displaystyle x_i $, con $ ~\displaystyle 1\leq i\leq k-2 $ (che sono al più $ ~\displaystyle 2d-2 $ nodi). Quindi esiste un $ ~\displaystyle j $ tale che $ ~\displaystyle x_{j+1} $ è collegato a $ ~\displaystyle x_0 $, e $ ~\displaystyle x_j $ è collegato a $ ~\displaystyle x_k $: anche in questo caso, gli $ ~\displaystyle x_i $ fanno parte di un ciclo. Possiamo allora costruire un cammino più lungo di $ ~\displaystyle P $ partendo da $ ~\displaystyle y $, e seguendo tutto il ciclo: assurdo.

[federiko97]

Uhm, è un miracolo che sei riuscito a capire la mia soluzione, era scritta malissimo ...

Comunque la tua è decisamente elegante . Per curiosità: come la hai trovata?

[Tibor Gallai]

Mi sono ispirato alla dimostrazione del teorema di Dirac per i cicli Hamiltoniani.