componente connessa (I)

quant'è bella giovinezza che si fugge tuttavia!

lorenzo de'medici

in risposta ad un mio amico barese, ecco qua una spiegazione visiva del significato del termine "componente connessa".

immaginiamo di vivere in un arcipelago di isole, collegate tra loro da ponti, ognuno dei quali è percorso da una strada a doppio senso. l'isola dove noi viviamo si chiama aaaahh. un giorno prendiamo la macchina e ci avviamo per il primo ponte che incontriamo, che si chiama uuunnno. per semplicità, supponiamo che l'unica strada interna alle isole sia una litoranea percorribile solo in senso orario, cosicchè esiste un unico primo ponte che si incontra partendo da un qualsiasi punto della strada. prima di attraversare il ponte disegniamo su un foglietto un punto rappresentante l'isola e una linea per il ponte.

attraversiamo questo ponte ed arriviamo su di una seconda isola, l'isola di bbbbee. nuovamente cerchiamo il primo ponte, che chiamiamo ddueeee. potrebbe essere quello da cui siamo appena arrivati, nel caso ci sia un solo ponte per bbbbee. in questo caso facciamo sul nostro foglietto una croce su bbbbee, per segnarci che abbiamo percorso tutti i ponti, e torniamo a aaaahh, a prendere il successivo ponte. nell'altro caso, segniamo sulla carta prendiamo il ponte ddueeee e proseguiamo per andare all'isola di cccì.

li proseguiremo questa operazione in un'ovvia progressione; alla fine avremo solo isole segnate da croci sulla nostra carta: quella che vediamo disegnata è una componente connessa del grafo delle isole.

le altre le possiamo trovare volando con l'aereo su un'altra isola e ricominciando il gioco...