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.
22. Il commesso viaggiatore (staffetta)
22. Il commesso viaggiatore (staffetta)
Sono il cuoco della nazionale!
Re: 22. Il commesso viaggiatore (staffetta)
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 Spero di non aver cannato
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!
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
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!
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
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"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Re: 22. Il commesso viaggiatore (staffetta)
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!
p.s.: figurati, fa sempre piacere quando qualcuno risponde alla staffetta di combinatoria!
Sono il cuoco della nazionale!
Re: 22. Il commesso viaggiatore (staffetta)
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)?
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"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Re: 22. Il commesso viaggiatore (staffetta)
Ok, ora va benissimo, puoi procedere con il problema 23.
Sono il cuoco della nazionale!
Re: 22. Il commesso viaggiatore (staffetta)
Well,
ecco il 23) viewtopic.php?f=16&t=15673
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"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"