Tre esercizi sui grafi

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Intendevo il caso a).
 Infatti il metodo che hai descritto collega sempre foglie sorelle con foglie sorelle, generando cicli da 6 a bizzeffe. Vero?

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Btw, Marco, cos\'è la citazione nella tua firma??

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Ok, fermi tutti: ho dimostrato che con k=6 il grafo minimo ha più di 22 nodi. Quindi sia la mia dimostrazione che quella di Marco sono errate, ed il problema rimane aperto.
 Allegria!! <IMG SRC="images/forum/icons/icon_wink.gif">
 
 
 EDIT:
 Dò un accenno di dimostrazione che per k=6 la nostra congettura sul minimo fallisce.
 Per k pari l\'albero è formato da 3 sottoalberelli A, B, C, le cui radici si uniscono nella radice principale. Ogni foglia di A va unita con una foglia di B ed una di C, ed analogamente per le foglie di B e C, altrimenti si creerebbero cicli troppo corti. Quindi, senza perdita di generalità, possiamo numerare con 0, 1, 2 le foglie più a sinistra di A, B, C.
 Per k=4 esiste un solo modo di collegare tra loro le foglie, a meno di isomorfismi. Dopo aver numerato le foglie 0, 1, 2 come sopra, necessariamente la 3 dev\'essere la sorella della 0, la 4 dev\'essere la sorella della 1, e la 5 sorella della 2. Collegando le foglie secondo la numerazione, si ottiene il grafo che risolve il problema per k=4.
 Per k=6 i sottografi A, B, C hanno il doppio delle foglie rispetto a prima, e ci si rende conto facilmente che, senza perdita di generalità, possiamo numerare le 6 sorelle di sinistra come per il caso k=4. Quindi, le foglie hanno per il momento questi numeri (* indica che la foglia non è ancora stata numerata):
 0, *, 3, *, 1, *, 4, *, 2, *, 5, *.
 La foglia 6 dev\'essere scelta nel sottografo A, perché la 4 sta in B e la 5 in C. Se fosse la sorella della 3, si creerebbe un ciclo lungo 5, perciò deve necessariamente essere sorella della 0:
 0, 6, 3, *, 1, *, 4, *, 2, *, 5, *.
 Ora, la 7 dev\'essere scelta in B, e può essere sorella di 1 o di 4. Nel primo caso si crea un ciclo lungo 6, nel secondo caso un ciclo lungo 5.
 Ergo, per k=6 il minimo grafo ha più di 22 nodi. [ Questo Messaggio è stato Modificato da: MindFlyer il 20-08-2004 14:03 ]

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

Ciao.
 
 The Two Towers, IV, 1 \"The Taming of Sméagol\". Lo dice Samwise Gamgee a Frodo Baggins, mentre si trovano sugli Emyn Muil. E\' la battuta che apre il quarto libro ed è quella che preferisco.
 
 Beh, un\'altra che mi piace molto dice
 
 \"There\'s only one Dragon in Bywater, and that\'s Green.\"
 
 (The Fellowship of The Ring, I, 2 \"The Shadow of the Past\"). Questa la dice Ted a Sam in una delle scene assolutamente più gustose dell\'opera.
 
 [purtroppo non ho sottomano il libro per controllare l\'esattezza delle citazioni, ma sono quasi certo della loro attendibilità].
 
 Ok. Torniamo al grafo.
 
 Ho visto i percorsi di sei. <IMG SRC="images/forum/icons/icon_frown.gif"> E la dimostrazione che smentisce k=6 v=22 è da 7 punti. Doppio <IMG SRC="images/forum/icons/icon_frown.gif"> .
 
 Boh, adesso parto per il campeggio e ho da fare. Ci risentiamo martedì.
 
 Ciao.
 
 M.
 
 
 [addsig]

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Lol, ho letto solo alcune parti di quel tomo in inglese, e quando avevo molto più tempo libero di adesso sapevo troppo poco l\'inglese per poter fare a meno di leggerlo in italiano.
 Per questo, ricordo la metà dei dettagli di quel libro soltanto a metà, e nutro, per meno della metà di ciò che è contenuto nel libro, metà dell\'affetto che meriterebbe.
 Sono andato a rileggere quella frase del libro IV in italiano, ed è un laconico \"Ebbene, padrone, siamo indubbiamente in un bel guaio.\". Ad ogni modo, non capisco la battuta nè in inglese, nè tantomeno in italiano... <IMG SRC="images/forum/icons/icon_wink.gif">

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

Comunque l\'idea di marco è quella giusta...basta ritoccare un poco...
 
 Quando sarà risolto questo problema ne posto un altro un poco più interessante...
 
 P.s. Anche all\'università combinatoria e teoria dei grafi sono bistrattate - purtroppo... (meglio, meno gente capisce ciò che dico alla mia laurea, meno puntigliosi possono essere...ehehe...).

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-08-20 20:19, Catraga wrote:
 Comunque l\'idea di marco è quella giusta...basta ritoccare un poco...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Basta ritoccare un poco?!? A me sembra che a questo punto il problema abbia perso tutta la sua regolarità!
 
 Per k=6 ho dimostrato che v>22, e va bene.
 Ora, v=23 non va, per una questione di parità degli archi.
 v=24 non va bene perché renderebbe sbilanciati i 3 sottoalberi.
 v=25 non va, ancora per la parità.
 v=26 non va per lo sbilanciamento, ma è più complicato da dimostrare rispetto al caso v=24.
 v=27 non va per la parità.
 v=28 dovrei aver dimostrato che non funziona, dopo aver lungamente penato.
 v=29 niente, per la parità.
 v=30 non ho la forza di provarlo: troppi casi!
 
 Ora, Catraga, mi spieghi come cappero hai fatto a generalizzare un ragionamento simile? Da quello che hai detto mi è parso che tu il problema l\'abbia risolto...

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

Non sono riuscito a dimostrarne l\'esistenza e mi sono bloccato un poco più avanti rispetto a voi, poi dopo aver apportato quella \"modifica\" vaneggiata nel prec. msg. ho cambiato direzione... lavorando per l\'inesistenza (senza successo, cercavo di uccidere con operazioni chirurgiche quei 6-cicli che rompevano le scatole...e sfruttavo il fatto che l\'alberello poteva essere costruito per ogni nodo); poi l\'ho postato, sperando che venisse fuori qualche buona idea... ma....
 
 Cercando qualche cosa che mi potesse aiutare...
 Ho appena scoperto che il problema proposto mi è stato plagiato!!
 Un caso di plagio anticipato: il problema non è ancora risolto, è stato posto dal prof Tutte verso il 1950...
 Si tratta del cosiddetto (3,n) cage-problem...acc..speravo che la mia idea fosse originale...
 
 Quindi le ricerche sono state vane ed inutili... sigh..
 <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif">
 
 [ Questo Messaggio è stato Modificato da: Catraga il 21-08-2004 16:52 ]

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Guarda un po\' <A HREF="http://mathworld.wolfram.com/CageGraph.html" TARGET="_blank">QUA</A>!

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

Dove pensi abbia cercato?
 Wolfram ha una risposta per tutto...o quasi...

Vasya · Messaggio da **Vasya** » 01 gen 1970, 01:33

Ciao, Catraga, ma si tratta di Tutte che lavorava a Bletchley Park per decifrare la cosidetta macchina FISH?

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Uhm, la (3,7)-cage ha 24 nodi, evidentemente sbagliavo qualcosa nel dire che i sottoalberi erano sbilanciati. <IMG SRC="images/forum/icons/icon_eek.gif">

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Oh, sì, ho supposto che vi fosse un solo ciclo tra i nodi foglie! Damn <IMG SRC="images/forum/icons/icon_mad.gif">