Chiedo se qualcuno può gentilmente spiegarmi come si risolve questo problema, il testo è su un altro topic viewtopic.php?t=11737,
però lì si dà un indizio non molto chiaro.
SNS 2008/2009 es. 3
A parte qualche imprecisione nel problema originario (il quadrato ha lato n, poi viene diviso in quadratini di lato 1 cm; cos'è la lunghezza del labirinto? La somma delle lunghezze delle pareti? Il percorso più lungo che si può fare da un quadratino a un altro (e qui si sconfina nella geometria)? Visto che la tesi deve essere vera, la prima, ma andrebbe specificato).
Fondamentalmente tu hai due alberi:
- il quasi-albero che ha come nodi i vertici dei quadratini e come lati le pareti del labirinto
(e devi dimostrare che è per l'appunto un grafo connesso, con la quarta ipotesi che assicura una parete per ogni vertice e la seconda che assicura un collegamento al bordo per ogni parete e dunque per ogni vertice; e devi dimostrare che non contiene cicli, a parte il ciclo del bordo esterno, con la terza ipotesi)
- l'albero che ha come vertici i quadrati (o se preferisci i centri dei quadrati) e come archi i lati (non "parietali") che due quadrati hanno in comune (o se preferisci i segmenti che collegano i centri di cdue quadrati adiacenti non separati da una parete). Questo è connesso per la terza ipotesi e non contiene cicli per la seconda e la quarta messe insieme.
Un albero con n vertici ha esattamente n-1 archi (come dice edriv, scegli una radice e associ ad ogni altro vertice il primo arco del percorso che lo collega alla radice, così hai altri n-1 vertici oltre alla radice, dunque n-1 archi); un quasi-albero con un solo ciclo con n vertici ha esattamente n archi, perché togliendo un arco del ciclo otteini un albero.
Fondamentalmente tu hai due alberi:
- il quasi-albero che ha come nodi i vertici dei quadratini e come lati le pareti del labirinto
(e devi dimostrare che è per l'appunto un grafo connesso, con la quarta ipotesi che assicura una parete per ogni vertice e la seconda che assicura un collegamento al bordo per ogni parete e dunque per ogni vertice; e devi dimostrare che non contiene cicli, a parte il ciclo del bordo esterno, con la terza ipotesi)
- l'albero che ha come vertici i quadrati (o se preferisci i centri dei quadrati) e come archi i lati (non "parietali") che due quadrati hanno in comune (o se preferisci i segmenti che collegano i centri di cdue quadrati adiacenti non separati da una parete). Questo è connesso per la terza ipotesi e non contiene cicli per la seconda e la quarta messe insieme.
Un albero con n vertici ha esattamente n-1 archi (come dice edriv, scegli una radice e associ ad ogni altro vertice il primo arco del percorso che lo collega alla radice, così hai altri n-1 vertici oltre alla radice, dunque n-1 archi); un quasi-albero con un solo ciclo con n vertici ha esattamente n archi, perché togliendo un arco del ciclo otteini un albero.
Sono il cuoco della nazionale!