Tre esercizi sui grafi

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

Il problema è un problema sui grafi (facile facile), ma dato che sono state giustamente esposte più volte \"lamentele\" da chi non ne sapeva una fava, ne do due versioni!!!
 
 Coi grafi:
 Costruire il più piccolo (minimo numero di vertici) grafo connesso in cui ogni vertice abbia grado 3 e non esista un ciclo di lunghezza inferiore od uguale a 3. (Con dimostrazione..., non solo costruzione).
 
 Senza grafi:
 In un isola ci sono n tribù. Ogni tribù ha esattamente 3 tribù amiche, le altre sono nemiche (nota: se A è amico di B allora B è amico di A) inoltre se A e B sono tribù amiche allora non esiste una tribù che sia amica sia di A che di B. Determinare il minimo n per cui tale situazione etnico-culturale è possibile...
 
 Un altro problema un poco più difficile...
 
 Coi grafi:
 Costruire il più piccolo (minimo numero di vertici) grafo connesso in cui ogni vertice abbia grado 3 e non esista un ciclo di lunghezza inferiore od uguale a 4. (Con dimostrazione..., non solo costruzione).
 
 Senza grafi:
 Non mi viene in mente...
 
 ancora più difficile...
 
 Coi grafi:
 Sia G un grafo connesso in cui ogni vertice abbia grado 3 e non esista un ciclo di lunghezza inferiore od uguale a k; per quali k tale grafo esiste? in caso di esistenza dare una procedura per costruirne uno. Quanti vertici ha il più piccolo grafo con tale caratteristica (sempre in caso di esistenza)?
 
 Senza grafi:
 Non saprei cosa inventarmi... (mi dispiace...<IMG SRC="images/forum/icons/icon_frown.gif"> )

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

Per quanto mi riguarda.. hai indovinato.
 Non ne so una fava!!

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

tento l\'1 senza avere nessuna conoscenza riguardo ai grafi <IMG SRC="images/forum/icons/icon_cool.gif">
 Se esiste almeno un atribu allora ne devono esistere almeno 4 dato che la prima ne deve conoscere tre; inoltre ciascuna di queste 3 ne deve conoscere altre due da prendersi al di fuori di quelle date, di queste nuove aggiunte nessuna ne può conoscere più di due tra quelle presenti e non possono conoscersi tra loro quindi ne vanno prese 3 (che portano il numero totale a 7). Ognuna di queste tre però deve conoscere ancora una tribù quindi aggiungiamo l\'ottava e ultima tribù chiudendo il grafo.
 <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif">
 Si effettivamente l\'ho detto molto male ma spero che il concetto sia giusto <IMG SRC="images/forum/icons/icon_smile.gif">

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-08-18 13:02, MASSO wrote:
 [...]
 Si effettivamente l\'ho detto molto male ma spero che il concetto sia giusto <IMG SRC="images/forum/icons/icon_smile.gif">
 [...]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Beh, insomma... bene, bene non l\'hai proprio detto <IMG SRC="images/forum/icons/icon_wink.gif"> .
 
 La tua costruzione credo funzioni (confesso di essermi un po\' smarrito). Di sicuro non è ottimale perché si può riuscire con 6 tribù.
 Comunque se volevi descriverla bene, bastavano 4 parole: gli spigoli di un cubo.
 
 Congetture/considerazioni sugli altri 2 pb.:
 
 k=4 Si riesce con 10 e con meno si vede che non si può.
 L\'idea del poliedro funziona ancora (gli spigoli di un dodecaedro). Però ha 20 vertici.
 
 k=5 Meno di 14 è impossibile. A naso, dovrebbe potersi costruire l\'esempio con 14 vertici.
 
 Mah, occhio e croce dovrebbe potersi sempre, basta andare su con il numero di vertici. [non dimostrato!! use at your own risk]
 
 Nel testo l\'ipotesi di connessione è superflua: se un grafo non connesso soddisfa tutte le altre ipotesi, allora le sue componenti connesse soddisfano le ipotesi, ma sicuramente con meno vertici.

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

Buongiorno a tutti. La notte ha portato consiglio. Devo smetterla di frequentare questo forum, altrimenti mia moglie chiederà il divorzo..., anyway, here it goes:
 
 Se qualcuno vuole provare a risolvere il terzo problema, è meglio che smetta di leggere perché da qui in giù...
 
 
 
 
 ***************************************************************
 SPOILER: non leggere se si vuole tentare in proprio l\'esercizio
 ***************************************************************
 
 
 
 
 Ok. Non ho né il tempo né la voglia di fare la dimostrazioncina per benino con tutti i suoi conticini a posto, abbiate pazienza. Comunque salvo granchi clamorosi del sottoscritto (e chi mi conosce sa che non sono poi così rari), più o meno dovrebbe filare liscia.
 
 Per ogni k esiste un grafo che soddisfa le ipotesi. A dirla giusta ho fatto solo il caso pari, ma quello dispari dovrebbe farsi +/- allo stesso modo. [la questione riguarda solo l\'ottimalità, dato che se un grafo soddisfa le ipotesi per k, le soddisfa anche per k-1].
 
 se k è pari, si può costruire con 3 * 2^(k/2) - 2 e tale numero è il minimo possibile.
 
 La parte di minimalità si fa così. Suppongo di avere un grafo che soddisfa le ipotesi. Costruisco un albero contenuto nel grafo nel seguente modo: fisso un vertice (livello 0, la radice dell\'albero). Esso ha 3 vicini (livello 1) ognuno ha altri 2 vicini (liv.2) ecc.. fino al livello k/2. Tutti i vertici che incontro sono distinti (altrimenti ho un ciclo di lunghezza <=k) e quindi si tratta effettivamente di un albero.
 
 In questo modo, se fate il conto avete appunto 3 * 2^(k/2) - 2 vertici. Quindi un grafo che soddisfa ha per lo meno quel numero di vertici.
 
 Ora cerco di collegare le foglie dell\'albero, in modo tale da costruire un grafo che soddisfa.
 
 Numero le foglie da 0 a <put the right number here> nel seguente modo: osservo il cammino che si compie dalla radice alla foglia e uso le seguenti regole:
 
 - parto da 0
 - aggiungo 0, 1, 2 risp. se scendendo al livello 1 sono andato a sinistra, centro, destra (risp).
 - agiungo 3 * 2^i se scendendo al livello i+2 sono andato a destra, 0 altrimenti.
 
 In questo modo ottengo tutti i totali possibili una e una sola volta (lo si dimostra per induzione sui livelli).
 
 Ok. Numerate le foglie, le collego con un percorso ciclico che segue la progressione numerica e torna a 0.
 
 Questo grafo secondo me funziona (anche se è una noia mortale fare tutte le verifiche...)
 
 Una parola anche sul caso k dispari: si parte con l\'albero di vertici distinti, come sopra e ci si ferma al livello (k-1)/2 (ossia albero identico al caso k-1). Il livello successivo è \"irregolare\" nel senso che deve contenere almeno 2/3 dei vertici dell\'ultimo livello (fate voi il conto di quanti sono). Questo sistema la minimalità. Con un trucco simile alla numerazione delle foglie è possibile collegare ogni foglia (penultimo livello) con esattamente due vertici dell\'ultimo strato in modo che questo riceva esattamente 3 archi. Anche questo grafo dovrebbe andare, ma occorre vedere bene i dettagli della numerazione. Boh, provateci e ditemi se funge.
 
 
 
 
 
 ***************************************************************
 \\SPOILER
 ***************************************************************
 
 
 
 
 Ciao a tutti.
 
 M.

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

Il problema è veramente bello!
 La soluzione di Marco del caso pari è giusta, ed arriva al mio stesso risultato.
 Per il caso dispari viene invece 2(k+3)/2-2, e lo si dimostra sempre con l\'alberello, per induzione.

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

Ah, per dimostrare che le foglie dell\'alberello si possono unire, anziché usare la successione proposta da Marco, si può usare l\'induzione, che secondo me è più intuitiva (anche se lunga da spiegare).
 
 Caso pari:
 Le foglie si possono suddividere in modo naturale in 3 insiemi A, B, C (generati dai 3 sottoalberi che partono dalla radice), ognuno con 2n foglie (per qualche n). Ogni foglia di A dev\'essere necessariamente collegata con una foglia di B ed una di C, e così per le foglie di B e C. Ma non basta, perché se si collega a con b, la sorella di a può essere collegata solo con una delle 2n-1 cugine più lontane di b, etc etc. Si partizionano allora A, B, C nei sottoinsiemi A\', A\'\', B\', B\'\', C\', C\'\', ognuno di 2n-1 foglie, in modo che per ogni coppia di foglie sorelle in A, una vada in A\' e l\'altra in A\'\', etc. Si può quindi usare l\'induzione e collegare A\', B\', C\' tra loro, e A\'\', B\'\', C\'\' tra loro.
 
 Caso dispari:
 Questa volta gli insiemi sono 2: A contiene le 2n foglie di livello più basso, e B le 2n foglie di livello più alto. Ogni foglia di A dev\'essere collegata con 2 foglie di B e viceversa, in modo che se si collega a con b e b\', allora b e b\' sono cugine il più lontane possibile; discorso analogo per la sorella di a, etc etc. Partizionando ancora A e B in A\', A\'\', B\', B\'\' come sopra, si può usare l\'induzione per collegare A\' e B\' tra loro, e A\'\' e B\'\' tra loro.

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-08-19 11:28, MindFlyer wrote:
 Il problema è veramente bello!
 La soluzione di Marco del caso pari è giusta, ed arriva al mio stesso risultato.
 Per il caso dispari viene invece 2(k+3)/2-2, e lo si dimostra sempre con l\'alberello, per induzione.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Ciao. Concordo: il problema è molto bello. Il tuo ultimo intervento però mi ha costretto a fare i conti (quelli che NON volevo fare: sentiti pure in colpa, MindFlyer).
 
 Sono costretto ad una precisazione: se dici che il mio risultato per k pari è corretto e il numero per k dispari invece è bla, bla, bla, sembra che il mio risultato per il caso dispari non torna.
 
 Tuttavia anche il numero per il caso dispari è corretto. Infatti l\'ultimo livello del caso pari ha 3/2 2(k-1)/2. Quindi il livello (k+1)/2 del caso dispari ha 2(k-1)/2 vertici. Perciò il caso k dispari ha 3 2(k-1)/2 - 2 + 2(k-1)/2 = 2(k+3)/2 - 2.
 
 Ok. Amici come prima?
 
 Ciao.
 
 M.
 
 P.S.: è la prima volta che uso i tags. Se non si leggono gli esponenti, non flagellatemi e limitatevi a compatirmi. Grazie.

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-19 12:26, marco wrote:
 Sono costretto ad una precisazione: se dici che il mio risultato per k pari è corretto e il numero per k dispari invece è bla, bla, bla, sembra che il mio risultato per il caso dispari non torna.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Assolutamente non intendevo quello, visto che non avevi esplicitato alcunché di concreto per il caso dispari. L\'onore è salvo... <IMG SRC="images/forum/icons/icon_wink.gif">

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

La soluzione è molto buona e molto interessante.
 Sono molto lusingato dal fatto che il problema vi sia piaciuto, dato che è una mia creazione originale <IMG SRC="images/forum/icons/icon_biggrin.gif"> ...
 E noto con piacere che c\'è qualcuno che si interessa dei grafi (tanto per dire quanto sia bistrattata in Italia la combinatoria e la teoria dei grafi...)...
 
 Ps: la teoria dei grafi è una droga mentale, oltre che la causa per me di notti insonni...quindi marco stai attento <IMG SRC="images/forum/icons/icon_wink.gif"> .

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

Effettivamente l\'1 si può fare con soli sei vertici; e siccome ho capito la lezione di marco lo dimostro in cinque parole: esagono con le diagonali maggiori <IMG SRC="images/forum/icons/icon_wink.gif">

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

Ciao a tutti.
 
 Caspita: tre menzioni negli ultimi 3 messaggi!
 
 Rispondo a MindFlyer: di quale onore si parla? Ho sbagliato calcoli che voi umani non potete neanche immaginare... [fuor di celia: mi rendo conto nel mio ultimo di essere stato un po\' pedante. Chiedo scusa a te e agli altri].
 
 Rispondo a Catraga: grazie, ma è solo una bozza. Il problema è, come detto, molto gradevole e ci ha portato via qualche ora di CPU time...
 
 La cosa interessante da raccontare, secondo me in questi casi, non è tanto la soluzione in sé e per sé, ma tutto il train of thoughts che vi ha condotto. Tanto per darti un\'idea: il grafo per k = 5 (14 vertici) mi è venuto per caso, cercando di costruire l\'esempio per k = 4 (troppa grazia!!). Ed era un grafo tutto diverso (almeno nella descrizione): numero i vertici e collego il vertice V con V+1, V-1 e V+5 se V è pari. Poi però si è dimostrato un filone sterile per i casi più alti.
 
 Per quanto riguarda il bistrattaggio di combinatoria e grafologia (quanti punti vale la parola \"grafologia\"?) sì e no: nella scuola 2aria sono semplicemente inesistenti. Tuttavia nelle Olimpiadi di Matematica, combinatoria e cavolatine simili sono uno dei cavalli di battaglia (o almeno, lo erano una dozzina di anni fa) dei ragazzi italiani. Almeno per quanto mi riguarda, sicuramente meglio di geometria piana e diseguaglianze!!
 
 Droga mentale: ebbene devo confessare anch\'io un discreto numero di notti insonni. Grazie per l\'avvertimento, ma temo che tu sia arrivato tardi...
 
 Rispondo a Masso: devi scusarmi, ma con il cubo mi avevi fatto un assist troppo ghiotto per lasciarlo passare liscio. Per l\'esagono bravo!! Per la cronaca quel grafo (6 v.) ha un nome ed un cognome: grafo bipartito (3,3).
 
 Ciao.
 
 M.

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

Uhm, il mio metodo per induzione ha bisogno di un piccolo ritocco, perché collega le foglie formando 2n cicli, mentre noi ne vorremmo uno solo. Sono convinto che si possa sistemare tutto permutando le foglie di un ciclo, e quindi tagliando ed unendo tra loro i 2 cicli. Ma non ho molto tempo per pensarci adesso, e comunque c\'è sempre il metodo di Marco, che pare funzionare.

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

Pardon, ritiro quello che ho detto: il metodo di Marco non funge. Infatti corrisponde al mio metodo per induzione, semplicemente con l\'aggiunta di 2 tagli e reincollamenti. E questo crea sempre cicli lunghi 6.

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

Ciao.
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-08-20 09:52, MindFlyer wrote:
 Pardon, ritiro quello che ho detto: il metodo di Marco non funge. Infatti corrisponde al mio metodo per induzione, semplicemente con l\'aggiunta di 2 tagli e reincollamenti. E questo crea sempre cicli lunghi 6.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Ehm... non ho capito. <IMG SRC="images/forum/icons/icon_confused.gif"> Quale pezzo non torna?
 a) la procedura per il caso pari
 b) per il caso dispari
 c) l\'idea +1-1+5?
 
 Se a) non lo vedo, puoi spiegarmelo?
 
 Se b) non è possibile: non ho dato sufficienti dettagli per affermare una cosa del genere (e a dire il vero non li ho nemmeno io: ci dovrei pensare per mettere a puntino la costruzione).
 
 Se c) sono d\'accordo: è quello che intendevo con \"filone sterile\". Quell\'idea era solo per k=5 v=14.
 
 Ciao.
 
 M.[addsig]