Primi elementi della teoria dei grafi

Traffico a senso unico

In una città ci sono strade in cui il traffico può scorrere in entrambi versi di marcia e strade in cui è consentito alle auto il passaggio in un solo verso indicato con un apposito cartello stradale.

In genere, in un centro cittadino il traffico a senso unico viene applicato per limitare il traffico in una determinata zona. Per organizzare una rete stradale con tutte le strade a senso unico è necessario orientare il verso delle vie in modo che sia possibile poter muoversi da una via a una qualsiasi altra via rispettando i sensi stabiliti. Tuttavia in due casi particolari non si può trasformare un sistema di traffico nei due versi in uno organizzato a senso unico altrimenti alcune vie potrebbero essere inaccessibili se si proviene da una determinata parte della città. Ad esempio, consideriamo il grafo in figura che rappresenta la mappa della rete stradale relativa ad una parte della città a cui si vuole applicare il senso unico in tutte le strade.

E chiediamoci: è possibile stabilire un dato verso agli spigoli in modo che vi sia un cammino orientato da un qualsiasi vertice ad un altro qualsiasi vertice? Lo spigolo tra i vertici C e F rappresenta l'unico collegamento tra le zone A e B della città: potrebbe essere l'unico ponte su un fiume oppure l'unico cavalcavia ferroviario o l'unico sottopassaggio ferroviario. Ora se a questo collegamento viene posto un solo verso di marcia ad esempio da C verso F nessuna auto proveniente da F potrebbe percorrere il tratto da F verso C e quindi le auto provenienti dalla zona B non potrebbero entrare nella zona A. Inoltre, lo spigolo tra i vertici E e K corrisponde a una strada senza uscita e non si può renderla a senso unico senza bloccare l'accesso delle auto provenienti da E oppure l'uscita delle auto proveniente da K. Gli spigoli come CF e EK sono detti di separazione o di ponte perchè collegano due parti di un grafo che altrimenti sarebbero disconnesse. E' evidente che uno spigolo di ponte non può far parte di un circuito e un grafo privo di spigoli di ponte conterrà almeno un circuito. Possiamo quindi affermare che si può realizzare una rete stradale con tutte le strade a senso unico soltanto se ogni coppia di vertici è contenuta in un circuito. Tornando al grafo precedente possiamo orientare in un solo verso tutti gli spigoli tranne quelli di ponte che dovranno avere il doppio verso.