Triplette convergenti II. La vendetta

[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 (21.6 KiB) Visto 26016 volte

[Gianfranco]

Potrebbe andare questo?

giobimbopenta1tab.png (25.38 KiB) Visto 26013 volte

giobimbopenta1.png (60.29 KiB) Visto 26013 volte

P.S. Se è sbagliato, cancellerò questo messaggio.

[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]

Bene, grazie Giobimbo!
Allora c'è anche un prisma esagonale, salvo errori,

giobimboesatab.png (35.35 KiB) Visto 26000 volte

giobimboesa.png (25.05 KiB) Visto 26000 volte

[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]

... 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.

[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.