Triplette convergenti II. La vendetta

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Triplette convergenti II. La vendetta

Messaggio da giobimbo »

Bene Alessandro B, mi piace il tuo entusiasmo. La tua soluzione corrisponde a un grafo non planare; probabilmente aumentando il numero di punti aumentano anche le soluzioni possibili. Se riesci a trovare una etichettatura per il grafo qui sotto sarei davvero interessato a conoscerla. Senza impegno, grazie.
5-prisma.png
5-prisma.png (21.6 KiB) Visto 7632 volte

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Triplette convergenti II. La vendetta

Messaggio da Gianfranco »

Potrebbe andare questo?
giobimbopenta1tab.png
giobimbopenta1tab.png (25.38 KiB) Visto 7629 volte
giobimbopenta1.png
giobimbopenta1.png (60.29 KiB) Visto 7629 volte
P.S. Se è sbagliato, cancellerò questo messaggio.
Pace e bene a tutti.
Gianfranco

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Triplette convergenti II. La vendetta

Messaggio da giobimbo »

Proprio quello che volevo, NON cancellare. Bene Gianfranco, l’allenamento fatto in precedenza non è andato sprecato.
Adesso ho un 3-prisma, un 4-prisma, un 5-prisma e un 6-prisma, vedrò se riesco a ricavarne qualcosa di buono.

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Triplette convergenti II. La vendetta

Messaggio da Gianfranco »

Bene, grazie Giobimbo!
Allora c'è anche un prisma esagonale, salvo errori,
giobimboesatab.png
giobimboesatab.png (35.35 KiB) Visto 7616 volte
giobimboesa.png
giobimboesa.png (25.05 KiB) Visto 7616 volte
Pace e bene a tutti.
Gianfranco

Alessandro B
Livello 2
Livello 2
Messaggi: 26
Iscritto il: dom mag 14, 2023 11:17 am

Re: Triplette convergenti II. La vendetta

Messaggio da Alessandro B »

Mi sorprende vedere come Gianfranco riesca a trovare facilmente le soluzioni corrispondenti a grafi planari,
nonostante che queste soluzioni risultano assai più difficili da trovare
rispetto a quelle corrispondenti a grafi non planari.

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Triplette convergenti II. La vendetta

Messaggio da Gianfranco »

Alessandro B ha scritto:
gio mag 25, 2023 9:33 pm
... trovare facilmente le soluzioni corrispondenti a grafi planari,
nonostante che queste soluzioni risultano assai più difficili da trovare
rispetto a quelle corrispondenti a grafi non planari.
Ciao Alessandro, benvenuto nel Forum!

Ho scritto un programmino (brute force vergognoso) che cerca le soluzioni: praticamente una serie di cicli FOR annidati.
Ma oltre i 6+6 punti (prisma) i tempi di calcolo diventano troppo lunghi.
Sto cercando di migliorarlo ma non so se ci riuscirò.
In effetti, cercare un grafo planare che deriva da una struttura a forma di prisma è più facile che cercare un grafo generico perché ci sono molti meno casi da esaminare e la struttura è pre-determinata: infatti basta cercare due catene chiuse indipendenti (le basi) e verificare i possibili collegamenti paralleli fra i loro vertici. Però tutto ciò si basa sulla presupposizione che un tale grafo esista.
Pace e bene a tutti.
Gianfranco

Alessandro B
Livello 2
Livello 2
Messaggi: 26
Iscritto il: dom mag 14, 2023 11:17 am

Re: Triplette convergenti II. La vendetta

Messaggio da Alessandro B »

Ciao Gianfranco,
io ritengo invece che sia più semplice trovare la soluzione se non viene aggiunta la condizione di avere un grafo planare.

Infatti, senza questa condizione, posso procedere così:
Divido l’insieme dei vertici del grafo in due sottoinsiemi aventi n/2 punti ciascuno.
Ogni vertice di un sottoinsieme si collega con 3 vertici dell’altro sottoinsieme.
In tal modo mi risulta possibile assegnare in modo arbitrario i numeri associati ad ogni vertice di un sottoinsieme e limitarmi a cercare quali numeri associare ai vertici dell’altro sottoinsieme per ottenere una soluzione valida.

Questa è la mia strategia:
1) Divido l’insieme dei vertici del grafo in due sottoinsiemi aventi n/2 punti ciascuno
2) Ogni vertice di un sottoinsieme si collega con 3 vertici dell’altro sottoinsieme
3) Associo ai vertici di un sottoinsieme i numeri compresi tra (n+2) e (3n/2+1)
4) Associo a due vertici dell’altro sottoinsieme i valori 1 e (n+1)
5) Collego il vertice 1 al vertice (3n/2+1) ed al vertice (3n/2)
6) Collego il vertice (n+1) al vertice (n+2)
7) Cerco a tentativi quali numeri associare ai vertici rimasti e quali vertici collegare

Lo scopo del punto 5) è garantire la presenza del “peso”= (3n/2) e del “peso”= (3n/2-1)
Lo scopo del punto 6) è garantire la presenza del “peso”=1

Il punto 7) risulta molto semplice da fare, dopo aver fatto i punti precedenti della strategia; in quanto al crescere di n aumenta il numero di soluzioni possibili; per cui risulta sempre basso il numero di tentativi da compiere.

N.B.
La condizione di avere un grafo planare non mi permette di applicare i primi 2 punti della strategia, rendendo in tal modo molto più difficile trovare una soluzione.

Rispondi