Problema di Alex\'

[Azarus]

è da un po\' che non mi facevo vedere..
<BR>
<BR>ok, problema di alex\' posto ieri sera nell\'uscita pisana:
<BR>
<BR>Abbiamo un grafo di diametro 3 e massimo grado 3, quale è il massimo numero di vertici?
<BR>
<BR>
<BR>
<BR>

[Kalidor]

una parentesi di disarmante semi OT... dove si può trovare qualche nozione (almeno quelle sufficienti per i problemi delle olimpiadi ) di teoria dei grafi?

[Azarus]

mi sa che fra poco scriverò una piccola dispensa sull\'argomento

[psion_metacreativo]

ne ordino 1 copia!

[FrancescoVeneziano]

Il limite teorico è di 22 vertici, ma non può essere raggiunto; invece ne ho appena trovato uno da 16 (il precedente record era 12), e credo si possa salire ancora.
<BR><!-- BBCode Start --><IMG SRC="https://mail.sns.it/~f.veneziano/grafo.gif"><!-- BBCode End -->
<BR>
<BR>
<BR>CaO (ossido di calcio)
<BR>
<BR>[ Questo Messaggio è stato Modificato da: FrancescoVeneziano il 04-09-2003 15:49 ]<BR><BR>[ Questo Messaggio è stato Modificato da: FrancescoVeneziano il 04-09-2003 15:52 ]

[ReKaio]

idem (il mio non ha simmetria centrale, solo assiale, quindi è più brutto)
<BR>
<BR><!-- BBCode Start --><IMG SRC="http://kayo.altervista.org/grafo2.gif"><!-- BBCode End -->

[FrancescoVeneziano]

Ne ho uno da 20 !!
<BR>Però è troppo brutto da disegnare col paint di windows e non facile da descrivere.
<BR>CaO (ossido di calcio)

[ReKaio]

<!-- BBCode Start --><IMG SRC="http://kayo.altervista.org/grafo20_ter.gif"><!-- BBCode End -->
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>Ossido> prendi un blocco da 4 vertici fatto così
<BR>Ossido> un vertice centrale e gli altri 3 collegati a lui
<BR>Ossido> e disponi a pentagono 5 di questi blocchi
<BR>Ossido> ora collega ognuna delle punte esterne con quella più vicina del blocco adiacente
<BR>Ossido> i 5 vertici centrali collegali a pentagono o a stella pentagonale
<BR>Ossido> e poi fai delle diagonali esterneche scavalchino un blocco
<BR>Ossido> un punto di sinistra va collegato col punto di destra dei due blocchi adiacenti
<BR>
<BR>[...] -mentre non c\'ero-
<BR>Perossido> poi collega la punta di destra di ogni blocco con le punte di sinistra dei 2 blocchi opposti
<BR>Perossido> come kayo non ha fatto
<BR>Perossido> e idem con la punta sinistra collegata a quelle destre
<BR>***> Non c\'è il disegno sul forum?
<BR>Perossido> no
<BR>Perossido> non ancora, kayo è andato senza aggiustarlo
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>visto che mi si sta criticando alla grande e non mi piace essere criticato, ecco le istruzioni che ho ricevuto per fare il disegno, se riuscite ad interpretare il crittogramma meglio di me allora buona fortuna<BR><BR>[ Questo Messaggio è stato Modificato da: ReKaio il 05-09-2003 06:08 ]

[Alex85]

Ehm... mi accorgo solo ora che si stava parlando di tutto ciò mentre non avevo possibilità di rispondere... volevo aggiungere, per azarus e tutti coloro che lo hanno letto:
<BR>NON mi chiamo alex\' [97.108.101.120.39]
<BR>bensì alex` [97.108.101.120.96]
<BR>talvolta anche alex85, ma preferisco ignorare il mio anno di nascita... eh, un tempo, quando scelsi il nick, allora sì potevo pregiarmi di essere dell\'85, ora sono grande... <IMG SRC="images/forum/icons/icon27.gif">
<BR>
<BR>alex`
<BR>
<BR>ps. se vi aspettavate un commento sul problema... bè, non ho proprio nulla da dire, non ho la più pallida idea di come si risolva <IMG SRC="images/forum/icons/icon_smile.gif"> , è semplicemente un problema che mi era venuto in mente quando ho letto che i blog hanno come obiettivo il poter passare da un qualsiasi blog a un altro in 3 soli click [grafo orientato]. mi ero posto addirittura il problema di sostituire a quei 3 e 3 dei bei parametri a e b <IMG SRC="images/forum/icons/icon_biggrin.gif"> , e cercare di trovare una formula per avere il num. max. di vertici... invano