Strutture connesse ottimali
Mi sono venuti in mente svariati problemi (che non reputo facilissimi) di ottimizzazione in $3$ e più dimensioni, basati su cubi e strutture connesse... ve ne propongo giusto uno tra i tanti, nella speranza che faccia appassionare qualche giovane in più alla teoria dei grafi.
Problema "semplice": Si consideri il cubo unitario ${0,1}^3$ nel consueto spazio euclideo e si assuma che un "albero" sia una qualsiasi struttura rigida, connessa, formata da segmenti rettilinei tra loro collegati (in pratica, un albero ha la caratteristica che prendendone un qualsiasi ramo e muovendolo, il resto dovrà seguirlo... non possono esserci pezzi staccati, per intenderci).
Domanda "semplice": Si determini la minima lunghezza che possa avere un albero che colleghi tutti gli $8$ vertici del cubo (indizio, la soluzione che ho trovato non è né $7$ e nemmeno qualcosa che sta sopra $6+\frac{2}{3}$).
Generalizzazione "difficile": Si consideri la famiglia degli (iper)cubi $k$ dimensionali ${0,1}^k \subset \mathbb{R}^k$ (con $k=2, 3, 4, \ldots$), sempre assumendo metrica euclidea come sopra... ma questa volta si determini la minima lunghezza (euclidea) per ciascun albero $k$-dimensionale ottimale che unisca tutti i $2^k$ vertici del relativo ipercubo (esempio, se $k=2$, possiamo facilmente concludere che la lunghezza minima è $2 \cdot \sqrt{2}$ che si ottiene unendo i vertici opposti del quadrato unitario... questa tecnica però è poco utile all'aumentare delle dimensioni, perché già per $k=4$ peggioreremmo una qualsiasi soluzione banalmente ottenibile tramite "spanning path" di $2^k-1$ segmenti unitari).
Buon divertimento!
Marco
Problema "semplice": Si consideri il cubo unitario ${0,1}^3$ nel consueto spazio euclideo e si assuma che un "albero" sia una qualsiasi struttura rigida, connessa, formata da segmenti rettilinei tra loro collegati (in pratica, un albero ha la caratteristica che prendendone un qualsiasi ramo e muovendolo, il resto dovrà seguirlo... non possono esserci pezzi staccati, per intenderci).
Domanda "semplice": Si determini la minima lunghezza che possa avere un albero che colleghi tutti gli $8$ vertici del cubo (indizio, la soluzione che ho trovato non è né $7$ e nemmeno qualcosa che sta sopra $6+\frac{2}{3}$).
Generalizzazione "difficile": Si consideri la famiglia degli (iper)cubi $k$ dimensionali ${0,1}^k \subset \mathbb{R}^k$ (con $k=2, 3, 4, \ldots$), sempre assumendo metrica euclidea come sopra... ma questa volta si determini la minima lunghezza (euclidea) per ciascun albero $k$-dimensionale ottimale che unisca tutti i $2^k$ vertici del relativo ipercubo (esempio, se $k=2$, possiamo facilmente concludere che la lunghezza minima è $2 \cdot \sqrt{2}$ che si ottiene unendo i vertici opposti del quadrato unitario... questa tecnica però è poco utile all'aumentare delle dimensioni, perché già per $k=4$ peggioreremmo una qualsiasi soluzione banalmente ottenibile tramite "spanning path" di $2^k-1$ segmenti unitari).
Buon divertimento!
Marco
Risposte
Ho postato il problema generale anche su MO e ne è nata una discussione che ha rivelato qualcosa che non mi sarei proprio aspettato... senza ragionarci su, avevo postato questo quesito dando per scontato che la soluzione del caso $2$D fosse ottimale unendo i vertici opposti del quadrato, ma mi sbagliavo... basti guardare la Figura 2 di questo paper (che ha come co-autore il mitico Martin Gardner): https://mathweb.ucsd.edu/~ronspubs/89_02_steiner.pdf
Dunque, abbiamo che il caso planare ha come miglior soluzione possibile un albero con $5$ rami la cui lunghezza totale è $1+sqrt{3}$, mentre il caso $3$D di sicuro ha come upper bound $6.197$ che discende da quest'altro paper di Bridges https://www.jstor.org/stable/3618571.
La teoria dei grafi è proprio un mondo tutto da scoprire e in cui non si può mai dare nulla di scontato prima di averlo dimostrato in modo rigoroso.
Dunque, abbiamo che il caso planare ha come miglior soluzione possibile un albero con $5$ rami la cui lunghezza totale è $1+sqrt{3}$, mentre il caso $3$D di sicuro ha come upper bound $6.197$ che discende da quest'altro paper di Bridges https://www.jstor.org/stable/3618571.
La teoria dei grafi è proprio un mondo tutto da scoprire e in cui non si può mai dare nulla di scontato prima di averlo dimostrato in modo rigoroso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo