22. Il commesso viaggiatore (staffetta)

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Anér
Messaggi: 722
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

22. Il commesso viaggiatore (staffetta)

Messaggio da Anér »

Abbiamo un grafo $ G $ connesso su $ n\geq 2 $ vertici, e sappiamo che in questo grafo due cicli non hanno mai un arco in comune. Siano $ l_1,\cdots,l_k $ le lunghezze dei $ k\geq 0 $ cicli del grafo.
Un commesso viaggiatore parte da un vertice $ P $ di $ G $ e deve camminare sugli archi del grafo in modo da visitare tutti i vertici e tornare alla fine in $ P $. Determinare il più piccolo intero $ M $ tale che con $ M $ passi il commesso viaggiatore può riuscire nell'impresa.
Sono il cuoco della nazionale!
Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Re: 22. Il commesso viaggiatore (staffetta)

Messaggio da Carlein »

Veramente carino questo problema. Visto che altrettanto vegliardi hanno partecipato alle staffette impunemente,e visto che sono passati un paio di giorni e poichè mi è piaciuto molto, provo a buttare giù quello che ho pensato :D Spero di non aver cannato :P
1) E' chiaro che i lati che non giacciono su cicli, li devo usare almeno 2 volte, perchè sono l'unico collegamento tra 2 componenti altrimenti sconnesse,è anche abbastanza chiaro che nei percorsi minimali lo userò 2 volte. Altrettanto chiaro che in un percrso minimale i lati che stanno sui cicli li uso tutti una volta sola. Quindi il totale cercato è 2T+S, dove $ S=\sum_{i=1}^{k}l_i $ e T è il numero di lati che non giacciono su cicli. D'altronde vale T+S=L, con L il numero di lati.
2)Il nostro obeittivo è trovare T. Qui entra in gioco l'osservazione che il grafo è un quasi albero. Difatti supponiamo di rimuovere da ogni ciclo un lato a caso, allora è chiaro che abbiamo un albero e dunque abbiamo che il numero di lati è n-1, d'altronde per l'ipotesi fatta sui cicli che non condividono lati abbiamo perso esattamente k lati, dunque si ha $ n-1=T+S-k $ da cui $ T=n-1-S+k $.
3) Unendo 1) e 2) si ha che $ M=2(n-1+k)-S $.
Uff...spero fili tuttoche non ho ancora ricontrollato bene(in particolare ammetto di essere stato vago in 1), ma spero sia sufficiente(è un pò una rottura a spiegarsi per bene il motivo un pò più esplicito che c'avrei) altrimenti se non è convincente chiedete che provo a spiegarmi,a patto sia giusto XD), di 2) sono più convinto.Fatemi sapere
Ciao! :D
p.s: scusate ancora per l'intromissione, ma la combinatoria mi piace, e tra gli universitari che conosco è altamente snobbata su scimat latita(tranne qualche comparsa di dario2994, appunto XD) e io mi sento un pò solo :oops: :P
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Avatar utente
Anér
Messaggi: 722
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Re: 22. Il commesso viaggiatore (staffetta)

Messaggio da Anér »

Mi pare che fili tutto, ma credo che dovresti spiegare meglio il punto 1, soprattutto perché nel caso migliore usi solo due volte i lati esterni ai cicli e una volta quelli interni (insomma dovresti costruire una strategia per il commesso viaggiatore). Inoltre non è chiaro perché devi usare almeno una volta ogni lato di un ciclo (che poi non è nemmeno vero, anche se non del tutto falso). Sistema queste cose prima di proporre il prossimo.
p.s.: figurati, fa sempre piacere quando qualcuno risponde alla staffetta di combinatoria!
Sono il cuoco della nazionale!
Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Re: 22. Il commesso viaggiatore (staffetta)

Messaggio da Carlein »

Hai ragione, ho trascurato di chiarire un bel pò di cosette, e devo dire che a chiarirle sono usciti un sacco di passaggi in più di quanto mi aspettavo al primo attacco intuitivo(o meglio barbaro).
Vado
0)Questa proprietà vale per tutti i grafi.Se un lato l non giace su un ciclo e lo rimuovo, allora il grafo restante è sconnesso in due componenti. Difatti se chiamo A e B gli estremi, allora se nel grafo senza l A e B restano connessi da un cammino, restano senza dubbio connessi da un cammino senza ripetizioni di vertici(che ottengo rimuovendo opportunamente pezzi inutili del cammino di prima), questo cammino con l dà un ciclo su cui giace l, assurdo. D'altronde è chiaro che ogni vertice deve conoscere in G-l uno tra A e B, difatti in G conosceva entrambi,prendo il cammino in G con cui conosceva per dire A,se il primo che conosco tra A e B in questo cammino è B, allora non ho ancora usato l (altrimenti conoscevo A prima), viceversa se è B.
1) Costruisco induttivamente il percorso con 2T+S passi. Per n=2, è ovvio. Suppongo che tutti i grafi ad al più n nodi con la proprietà data, abbiano un tale cammino. Prendo un grafo G a n+1 nodi con la data proprietà.Distinguo due casi:
a)C'è un lato l che non giace su nessun ciclo. Allora,tenendo presente 0), se parto da un vertice A di questo lato, la componente connessa di G-l in cui sta A, rispetta l'ipotesi induttiva, faccio lì il mio percorso, vado in B, di nuovo stesso discorso per lui, ritornato in B rifaccio l e sono in A con 2T+S passi.
b)Non c'è tale lato l.Distinguo due casi
b.1)Tutti i vertici hanno grado 2: in tal caso G è un ciclo, e la costruzione è ovvia
b.2)C'è un nodo N di grado più di 2. Allora G-N è sconnesso: difatti vi sono almeno due cicli C e D su cui sta N, i percorsi che connettono un vertice di C e uno di D passano sempre per N, altrimenti similmente a 0) riusciamo a costruire un ciclo che ha lati in comune con C e con D. Siano dunque $ H_1,...,H_j $ le componenti connesse di G-N. Consideriamo i vari grafi $ F_1=H_1+N,F_2=H_2+N...,F_j=H_j+N $ questi sono tutti grafi che rientrano nell'ipotesi induttiva, io dunque parto da N e attuo la strategia ottenuta al passo induttivo per $ F_1 $, ritornato ad N continuo con $ F_2 $ fino a fare $ F_j $ e questo è il percorso che ci va bene.
2)Dimostro che $ M\geq 2T+S $.
2.1)Per la proprietà 0) io ho che un lato l ,contato da T, se tolto sconnette il grafo in 2 componenti W e X. Allora è del tutto chiaro che ogni percorso che partendo da un vertice N che sta diciamo in W, conosce tutti e ritorna in W, dovrà prima passare da W a X e poi il contrario, in tutti e due i casi deve per forza usare l, quindi l è stato usato due volte, e abbiamo già così 2T passi.
2.2)In pratica ora usiamo un miscuglio di quello che abbiamo imparato in 2.1) e in 2) del mio post di sopra.
Dato un percorso generico metto i cicli in due categorie
c.1)Quelli i cui lati vengono usati tutti almeno una volta
c.2) gli altri
Questo corrisponde a fare un percorso sul grafo che otteniamo rimuovendo da ciascun $ z_1,...,z_h $ cicli classificati in c.2), un lato(di più non posso togliere perchè una volta tolto un lato quelli restanti sono lati che non giacciono più su cicli e quindi ho 0), in effetti togliere u lato a un pò di cicli qui come in 2) del mio post precedente comporta un'alberizzazione del grafo che in entrambi i casi mi fa contare bene le cose,qui per 2.1), a 2) del post di prima per il fatto che un'albero ha n-1 lati, in generale perchè l'albero è un caso estremo facile da gestire che dice molto al problema). Ma allora è chiaro che in totale ho almeno quelli contati da c.1 che sono $ \sum_{i=h+1}^{k}l_i $ e poi per quanto appreso in 2.1) $ \sum_{i=1}^{h}2(l_i-1) $ da c.2). Quindi in totale ho $ 2T+\sum_{i=h+1}^{k}l_i+\sum_{i=1}^{h}2(l_i-1)\geq 2T+S $ dal momento che la disuguaglianza vale addendo per addendo( dal momento che $ 2(n-1) > n $ per n>2)
Torna tutto? E' tutto abbastanza esplicito(in effetti prima,come si evince chiaramente dalla lunghezza del post e dalle 3 sdegnate righe usate in precedenza, volevo viaggiare in prima classe con un biglietto dello scompartimento merci-bestiame)?
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Avatar utente
Anér
Messaggi: 722
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Re: 22. Il commesso viaggiatore (staffetta)

Messaggio da Anér »

Ok, ora va benissimo, puoi procedere con il problema 23.
Sono il cuoco della nazionale!
Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Re: 22. Il commesso viaggiatore (staffetta)

Messaggio da Carlein »

Well,
ecco il 23) viewtopic.php?f=16&t=15673
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Rispondi