mercoledì, 22 gennaio 2020
Nessuna intersezione I
Ci sono tre punti A B C, ciascuno dei quali deve venire connesso ad altri tre punti X Y Z.
Come si può farlo senza che nessuna riga delle connessioni si intersechi (e facendo in modo che tutti i 6 punti giacciano sullo stesso piano)?
Soluzione
Non si può. Per dimostrarlo, si cominci a collegare solo A e B: il grafo ottenibile è topologicamente equivalente a questo:
La casa C può trovarsi in una delle tre regioni contrassegnate con i numeri 1, 2 o 3; in ogni caso, non si potrà raggiungere una delle altre regioni.
Dario Uri mi segnala che tale collegamento è possibile su una superficie toroidale.
Fabio Capoccetti mi segnala che se le due terne di punti si trovano allineati su due rette sghembe nello spazio 3D, il collegamento è possibile.
Nota: In teoria dei grafi, il fatto che ci siano tre punti collegati ad altri tre punti come descritto nel testo del problema costituisce una condizione sufficiente alla non planarità di un grafo.
Questo sito non rappresenta una testata giornalistica in quanto non viene aggiornato con cadenza periodica
né è da considerarsi un mezzo di informazione o un prodotto editoriale ai sensi della legge n.62/2001.
|
|
