Numerazione degli archi di un grafo
Numerazione degli archi di un grafo
E' sempre possibile numerare con 1,2,...,k i k lati di un grafo connesso, in modo che in ogni vertice con almeno due lati il massimo comun divisore dei numeri associati ai lati che gli arrivano sia 1?
Ehm... sarà il caldo... non vorrei dir cagate ma... non è ovvio? 
Basta partire da un lato che ha un vertice di grado uno e andare avanti ad uno a caso di quelli connessi a lui sin che è possibile. Quando non è più possibile parto da un altro che non avevo ancora numerato...
Quando ho terminato i vertici di grado uno, scelgo a caso quello da cui partire e continuo.
Mi son perso qualcosa? Per esempio il fatto che sia connesso a cosa serve?
Edit: sperando sia più chiaro.
Basta partire da un lato che ha un vertice di grado uno e andare avanti ad uno a caso di quelli connessi a lui sin che è possibile. Quando non è più possibile parto da un altro che non avevo ancora numerato...
Quando ho terminato i vertici di grado uno, scelgo a caso quello da cui partire e continuo.
Mi son perso qualcosa? Per esempio il fatto che sia connesso a cosa serve?
Edit: sperando sia più chiaro.
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Ci sei abbastanza vicino, ma così non funziona. Un motivo è appunto il fatto che scarti l'ipotesi che sia connesso 
Infatti, se prendi due triangoli disgiunti, uno avrà almeno 2 archi pari.
Se a un vertice sono attaccati due numeri consecutivi, ok, quel vertice funziona. Però quando scegli un vertice a caso da cui iniziare il tuo percorso, ecco, è quel vertice che ti può dar problemi!
Quindi la strategia giusta è: intanto è sufficiente fare i grafi senza vertici di grado 1. Poi scelgo un vertice a caso e da lui inizio un percorso a caso, numerando 1,2,... gli archi su cui passo, e mi fermo quando passo per un vertice già toccato.
Poi, tra i vertici che ho già toccato, scelgo uno da cui pare un arco ancora non colorato, e continuo un percorso a caso da lì finchè non tocco un vertice già toccato. E così via.
L'algoritmo funziona perchè finisco se e soltanto se ogni vertice già toccato ha tutti gli archi colorati, e per l'ipotesi che è connesso, se e soltanto se ho colorato ogni vertice.
La colorazione è buona perchè ogni vertice o lo ho toccato per la prima volta formando un percorso che non si è fermato lì, e quindi è attaccato a due numeri consecutivi coprimi, oppure è il primo vertice che ho toccato, ma a questo ho dato il numero 1 che è il "jolly".
Infatti, se prendi due triangoli disgiunti, uno avrà almeno 2 archi pari.
Se a un vertice sono attaccati due numeri consecutivi, ok, quel vertice funziona. Però quando scegli un vertice a caso da cui iniziare il tuo percorso, ecco, è quel vertice che ti può dar problemi!
Quindi la strategia giusta è: intanto è sufficiente fare i grafi senza vertici di grado 1. Poi scelgo un vertice a caso e da lui inizio un percorso a caso, numerando 1,2,... gli archi su cui passo, e mi fermo quando passo per un vertice già toccato.
Poi, tra i vertici che ho già toccato, scelgo uno da cui pare un arco ancora non colorato, e continuo un percorso a caso da lì finchè non tocco un vertice già toccato. E così via.
L'algoritmo funziona perchè finisco se e soltanto se ogni vertice già toccato ha tutti gli archi colorati, e per l'ipotesi che è connesso, se e soltanto se ho colorato ogni vertice.
La colorazione è buona perchè ogni vertice o lo ho toccato per la prima volta formando un percorso che non si è fermato lì, e quindi è attaccato a due numeri consecutivi coprimi, oppure è il primo vertice che ho toccato, ma a questo ho dato il numero 1 che è il "jolly".