Appunti Di Teoria Dei Grafi

Marco Barlotti

Appunti di

per linsegnamento di Matematica discreta e logica

(corso di laurea triennale in Informatica)

Vers. 2.2 Anno Accademico 2011-2012

In copertina una vignetta di Paolo Mottura tratta da I TL 2482-4 Topolino e il naufrago dello spazio di Silvano Mezzavilla ( Disney).

M. Barlotti - appunti di per il corso di laurea in Informatica - vers. 2.2 - Pag. ITeoria dei Grafi

PERCHE QUESTI APPUNTI, E COME USARLI(Prefazione alla vers. 2.2)

Questi appunti vogliono costituire un supporto scritto alla parte di Teoria dei grafidelle lezioni che tengo per linsegnamento di Matematica discreta e Logica per il Corso diLaurea triennale in Informatica presso la Facolt di Scienze Matematiche, Fisiche e NaturaliallUniversit di Firenze.

Si tratta di un basato sugli appunti integrativi che ho gi diffusowork in progressnellanno accademico 2010-2011. Anche per questo motivo, inevitabile la presenza di errorimateriali; inoltre, per quanto mi sia sforzato di conciliare il rigore con la chiarezza, alcunibrani del testo possono risultare poco comprensibili. Sar grato a tutti coloro, e specialmenteagli studenti, che vorranno segnalarmi qualunque problema, dai pi banali errori di stompaalle oscurit nellesposizione.

Firenze, 08.05.2012

Marco Barlotti

M. Barlotti - appunti di per il corso di laurea in Informatica - vers. 2.2 - Pag. IITeoria dei Grafi

AVVERTENZATutti i diritti di questa pubblicazione sono dellautore. consentita la riproduzione integrale di questa pubblicazione a titolo gratuito. altres consentita a titolo gratuito lutilizzazione di parti di questa pubblicazione in altraopera allinderogabile condizione che ne venga citata la provenienza e che della nuova operanella sua interezza vengano consentite la riproduzione integrale a titolo gratuito elutilizzazione di parti a queste stesse condizioni.Luso di questa pubblicazione in quasiasi forma comporta laccettazione integrale e senzariserve di quanto sopra.

M. Barlotti - appunti di per il corso di laurea in Informatica - vers. 2.2 - Pag. IIITeoria dei Grafi

SOMMARIO

1. - Generalit sui grafi1.1 - Prime definizioni . . . . . . . . . . . . . . . . . . . . . . . . . pag. 11.2 - Da un grafo allaltro . . . . . . . . . . . . . . . . . . . . . . . . pag. 41.3 - Prime propriet . . . . . . . . . . . . . . . . . . . . . . . . . pag. 41.4 - Isomorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . . pag. 7.1.5 - Esempi di grafi . . . . . . . . . . . . . . . . . . . . . . . . . . pag. 71.6 - Frammenti di topologia . . . . . . . . . . . . . . . . . . . . . . pag. 91.7 - Grafi disegnati su una superficie . . . . . . . . . . . . . . . . . . . pag. 101.8 - Disegni sul piano di alcuni grafi considerati nella sez. 1.5 . . . . . . . . . pag. 111.9 - Sottografi . . . . . . . . . . . . . . . . . . . . . . . . . . . . pag. 131.10 - Calibro . . . . . . . . . . . . . . . . . . . . . . . . . . . . pag. 14

2. - Connessione2.1 - Cammini, circuiti, cicli . . . . . . . . . . . . . . . . . . . . . . pag. 152.2 - Connessione . . . . . . . . . . . . . . . . . . . . . . . . . . . pag. 172.3 - Matrice di adiacenza . . . . . . . . . . . . . . . . . . . . . . . pag. 21

3. - Alberi3.1 - Alberi e foreste . . . . . . . . . . . . . . . . . . . . . . . . . pag. 293.2 - Caratterizzazione degli alberi come grafi connessi minimali . . . . . . . . pag. 303.3 - Classi di isomorfismo degli alberi con pochi vertici . . . . . . . . . . pag. 33

M. Barlotti - appunti di per il corso di laurea in Informatica - vers. 2.2 - Pag. IVTeoria dei Grafi

4. - Grafi piani4.1 - Definizione e prime propriet . . . . . . . . . . . . . . . . . . . . pag. 354.2 - Calibro e planarit . . . . . . . . . . . . . . . . . . . . . . . . pag. 384.3 - Il teorema di Kuratowski . . . . . . . . . . . . . . . . . . . . . . pag. 40

5. - Grafi euleriani5.1 - Definizione . . . . . . . . . . . . . . . . . . . . . . . . . . . pag. 415.2 - La caratterizzazione dei grafi euleriani senza orientamento . . . . . . . . pag. 415.3 - La caratterizzazione dei grafi euleriani con orientamento . . . . . . . . . pag. 45

6. - Grafi hamiltoniani6.1 - Definizione e prime propriet . . . . . . . . . . . . . . . . . . . . pag. 47.6.2 - Qualche condizione sufficiente . . . . . . . . . . . . . . . . . . . pag. 496.3 - Il caso dei grafi piani . . . . . . . . . . . . . . . . . . . . . . . pag. 556.4 - Il caso dei grafi con orientamento . . . . . . . . . . . . . . . . . . pag. 58

7. - Colorazioni7.1 - Colorazione di carte geografiche . . . . . . . . . . . . . . . . . . . pag. 597.2 - Il grafo duale di un grafo disegnato nel piano . . . . . . . . . . . . . . pag. 617.3 - Colorazione dei vertici di un grafo . . . . . . . . . . . . . . . . . . pag. 64

M. Barlotti - appunti di per il corso di laurea in Informatica - vers. 2. - Pag. 1Teoria dei Grafi #

1.- GENERALIT SUI GRAFI

1.1 - Prime definizioni.Si dice una terna ( , , ) dove , sono insiemi e una funzionegrafo Z i _ + i _ +

che a ogni associaj _ @ @ k un insieme { , } ( )" # i

oppure

@ @ una coppia ordinata ( , ) ." # i iNel primo caso si parla di , nel secondo caso di grafo senza orientamento grafo

con orientamento grafo con direzione(o, con terminologia meno felice: ) (in inglese:digraph directed graph vertici, contrazione di ). Gli elementi dellinsieme si dicono idi ; gli elementi dellinsieme si dicono di (oppure di , specialmenteZ _ Z Zlati archiquando un grafo con orientamento); la funzione si dice fra latiZ + funzione di incidenzae vertici di .Z

Sia un lato di , e sia ( ) { , } oppure ( ) ( , ); se , sij j @ @ j @ @ @ @ jZ + +" # " # " #dice un (in inglese: ), se invece , si dice un (in inglese:cappio loop collegamento@ @ j" #link).

Un grafo nel quale la funzione di incidenza iniettiva si dice ,grafo semplicementre (in contrapposizione) un grafo nel quale la funzione di incidenza non iniettiva sidice un . Un multigrafo con almeno un cappio si dice talvolta .multigrafo pseudografo

Due lati , si dicono paralleli se ( ) ( ) . Un grafo semplice se ej j j j" # " #+ +soltanto se non possiede alcuna coppia di lati distinti paralleli.

Un grafo ( , , ) si dice se e sono numeri naturali. SeZ i _ + i _ finito k k k kZ i _ + i Z ( , , ) un grafo finito, si dice l di .k k ordine

Si dice (o : le due espressioni si equivalgono)grafo orientato grafo asimmetricoun grafo con orientamento con la seguente propriet:

@ A @per ogni coppia di vertici , , se c un arco con primo estremo e secondoestremo allora non c nessun arco con primo estremo e secondo estremo ( ).A A @ 1

1 Come si vede, la nozione di grafo orientato diversa da quella di grafo con orientamento. importante non confondere i due concetti!


Dunque col termine si indicano due famiglie (la prima quella dei grafigrafosenza orientamento, la seconda quella dei grafi con orientamento) che possono anchepresentare situazioni molto diverse.

In questi appunti, specificheremo capitolo per capitolo (o addirittura sezione persezione) se ci riferiamo a una sola delle due famiglie (e in tal caso a quale), oppuretratteremo in distinte sottosezioni il caso dei grafi senza orientamento e quello dei graficon orientamento.

Cominciamo subito con le altre definizioni generali sui grafi, che diamo appuntoseparatamente nei due casi.

1.1.a - Altre prime definizioni per i grafi senza orientamento.

Sia ( , , ) un grafo senza orientamento.Z i _ +Se e ( ), si dice che il vertice e il lato sono (ma anche,j @ j @ j_ + incidenti

confidenzialmente, che un vertice di ).@ jDue vertici , si dicono se esiste un lato col quale sono entrambi@ A jadiacenti

incidenti. Si noti in particolare che un vertice risulta adiacente a se stesso se e soltanto seesiste un cappio incidente ad esso.

Due lati si dicono se esiste un vertice incidente a entrambi.consecutivi

Ad ogni vertice di si associa un numero naturale ( ), detto (o@ @Z gr gradoZvalenza) di (in ), definito come il numero dei collegamenti (di ) incidenti con pi il@ @Z Zdoppio dei cappi (di ) incidenti con . Tutte le volte che non necessario evidenziare ilZ @grafo si scrive ( ) anzich ( ) .Z gr gr@ @Z

Un vertice di grado si dice . Un vertice di grado si dice una .! "isolato foglia

Osservazione 1.1.1

Sia un grafo senza orientamento, e sia un vertice di . Se semplice e senza cappi,Z Z Z@grZ ( ) il numero dei vertici di adiacenti a e distinti da .@ @ @Z

Dimostrazione gr @Poich non ha cappi, ( ) il numero dei collegamentiZ Zincidenti a ; poich semplice, i collegamenti incidenti a sono in corrispondenza@ @Zbiunivoca con i vertici di adiacenti a e distinti da .Z @ @


1.1.b - Altre prime definizioni per i grafi con orientamento.

Sia ( , , ) un grafo con orientamento.Z i _ +Se e ( ) ( , ), si dice chej j @ A_ +

@ j @ j j e , e il di (detto anche di ) ;sono incidenti primo vertice vertice di entrata A j A j j e , il di (detto anche di ) ;sono incidenti secondo vertice vertice di uscita A @ adiacente a .

In un grafo con orientamento, in particolare, non si dice che e sono@ Aadiacenti ma si precisa se ad essere adiacente a o viceversa (naturalmente, inA @generale possono accadere entrambe le situazioni: ci avviene se e soltanto se esistonodue archi , tali che ( ) ( , ) e ( ) ( , ) ). Anche nei grafi con orientamentoj j j @ A j A @" # " #+ +si ha che: un vertice risulta adiacente a se stesso se e soltanto se esiste un cappioincidente ad esso.

Siano , due lati di . Si dice che a se il secondo vertice dij j j j" # # "Z consecutivoj j" # coincide col primo vertice di .

Sia ( , , ) un grafo con orientamento. Ad ogni vertice di si associanoZ i _ + Z @due numeri naturali:

@ @ ( ), detto di (in ), definito come il numero degli archigr grado in entrataZ( )/ Z

di per i quali vertice di uscita ;Z @ ( ), detto di (in ), definito come il numero degli archi @ @gr grado in uscitaZ

( )? Zdi per i quali vertice di entrata ;Z @

Tutte le volte che non necessario evidenziare il grafo si scrive ( ) eZ gr( )/ @gr gr gr( ) ( ) ( )? / ?( ) anzich rispettivamente ( ) e ( ) .@ @ @Z Z

Un vertice si dice se ( ) ( ) .@ @ @ !isolato gr gr( ) ( )/ ?

Un vertice si dice una se ( ) ( ) .@ @ @ "foglia gr gr( ) ( )/ ?

Osservazione 1.1.2

Sia un grafo con orientamento, e sia un vertice di . Se semplice e senza cappi,Z Z Z@grZ

( )? ( ) il numero dei vertici di adiacenti a distinti da .@ @ @ZDimostrazione gr @Poich non ha cappi, ( ) il numero dei collegamenti cheZ Z( )?

hanno come vertice di entrata ; poich semplice, tali collegamenti sono in@ Zcorrispondenza biunivoca con i vertici di adiacenti a .Z @


1.2 - Da un grafo allaltro.

Sia ( , , ) un grafo con orientamento. Si dice Z i _ + grafo senza orientamentoassociato a il il grafo senza orientamento ( , , ) per il quale la funzione diZ Z i _ +* *incidenza definita per ogni ponendo+ _* j

+ +*( ) { , } se e soltanto se ( ) ( , ) .j @ A j @ ASia ( , , ) un grafo senza orientamento, e sia il sottoinsieme di Z i _ + _ _ -

formato dai lati che sono incidenti a vertici distinti (quelli cio che abbiamo chiamatocollegamenti). Si dice di il grafo (senza orientamento) ( , , )sostegno Z Z i _ +! !! !semplice e senza cappi cos definito: ; ( ) ; .i i _ + _ +! !! - id_!

Se un grafo con orientamento, si dice di il sostegno del grafoZ Zsostegnosenza orientamento associato a .Z

In altre parole, il sostegno di ottenuto da mantenendo gli stessi vertici,Z Zeliminando i cappi e considerando un lato (e un solo lato!) per ogni coppia di verticiadiacenti in : tale lato viene identificato (come in generale si pu fare per ogni grafoZsemplice e senza cappi) con la coppia di vertici a cui esso incidente.

Ci sono importanti propriet che sono verificate da un grafo se e soltanto se sonoverificate dal suo sostegno: per lo studio di queste si possono pertanto, in molti casi,limitare le nostre considerazioni ai grafi semplici e senza cappi. Si vedano in proposito icapitoli 4 e 6. Per ora ci limitiamo ad osservare che losservazione 1.1.1 pu essere cosriformulata:

Osservazione 1.2.1

Sia un grafo senza orientamento, e sia un vertice di . Il numero dei vertici di Z Z Z@adiacenti a il grado di nel sostegno di .@ @ Z

1.3 - Prime propriet.

Teorema 1.3.1

Sia ( , , ) un grafo senza orientamento con . Si haZ i _ + _ - k k!@i

gr( ) .@ #-

Dimostrazione Possiamo procedere per induzione su .-Se , in non ci sono lati, cosicch ogni vertice di ha grado ; dunque per- Z Z ! !

- ! il teorema vero.


Supponiamo che il teorema sia vero per , e proviamolo per . Sia- - 5 " 5Sia ( , , ) un grafo con , e sia il grafo ottenuto da sopprimendo unZ i _ + _ Z Z 5k k !lato. Possono verificarsi due casi:

@ @ il lato soppresso un collegamento, incidente due vertici e ; allora" #gr gr gr gr gr grZ Z Z Z Z Z! ! !( ) ( ) , ( ) ( ) e ( ) ( ) per tutti gli altri@ @ " @ @ " @ @" " # #vertici , cosicch@ ! !

@ @i igr grZ Z! ( ) ( ) ;@ @ #

@ il lato soppresso un cappio, incidente il vertice ; allora"gr gr gr grZ Z Z Z! !( ) ( ) e ( ) ( ) per tutti gli altri vertici , cosicch ancora@ @ # @ @ @" " ! !

@ @i igr grZ Z! ( ) ( ) .@ @ #

Per lipotesi di induzione,!@i

grZ! ( )@ #5 "

da cui ! !@ @i i

gr grZ Z( ) ( )@ @ # #5 " # #5!

come si voleva dimostrare.

Teorema 1.3.2

In qualsiasi grafo senza orientamento, il numero dei vertici di grado dispari pari.

Dimostrazione Ovvio, perch in base al teorema 1.3.1 la somma dei gradi ditutti i vertici un numero pari.

Corollario 1.3.3 (Teorema delle strette di mano)

Se alcune persone si scambiano, anche ripetutamente, una stretta di mano, allora

( ) il numero delle persone che hanno dato un numero dispari di strette di mano 3pari;

( ) il numero delle persone che hanno stretto la mano a un numero dispari di persone33 pari.

Dimostrazione Sia ( , , ) il grafo senza orientamento in cui Z i _ + ilinsieme delle persone date, linsieme delle strette di mano scambiate e la funzione_di incidenza associa a ogni stretta di mano le due persone che se la sono scambiata. La+( ) segue dal teorema 1.3.2 applicato al grafo , la ( ) segue dal teorema 1.3.2 applicato3 33Zal sostegno di (cfr. sez. 1.2 e oss. 1.2.1) .Z


Teorema 1.3.4

Sia ( , , ) un grafo senza orientamento con e . Se ogni vertice di Z i _ + _ - i Z 8k k k kha grado almeno ,#

8 - .Dimostrazione Ricordando il teorema 1.3.1,

#8 # @ #! !@ @i i

gr( ) -

da cui immediatamente lasserto.

Lanalogo del teorema 1.3.1 per i grafi con orientamento molto menosuggestivo e non ha conseguenze analoghe al corollario 1.3.3.

Teorema 1.3.5

Sia ( , , ) un grafo con orientamento con . Si haZ i _ + _ - k k! !@ @i i

gr grZ Z( ) ( )/ ?( ) ( ) .@ @ -

Dimostrazione Possiamo procedere per induzione su .-Se , in non ci sono lati, cosicch ogni vertice di ha grado in entrata e- Z Z ! !

grado in uscita ; dunque per il teorema vero.! !-Supponiamo che il teorema sia vero per , e proviamolo per . Sia- - 5 " 5

Sia ( , , ) un grafo con orientamento con , e sia il grafo ottenuto da Z i _ + _ Z Z 5k k !sopprimendo un lato. Possono verificarsi due casi:

@ @ il lato soppresso un collegamento, con primo vertice e secondo vertice ;" #allora

gr gr gr grZ Z Z Z! !( ) ( ) ( ) ( )? ? / /

" " # #( ) ( ) , ( ) ( )@ @ " @ @ "

e naturalmente

gr gr gr grZ Z Z Z! !( ) ( ) ( ) ( )? ? / /( ) ( ) e ( ) ( ) per tutti gli altri vertici ,@ @ @ @ @

cosicch

! ! ! !@ @ @ @i i i i

gr gr gr grZ Z Z Z! !( ) ( ) ( ) ( )? ? / /( ) ( ) e ( ) ( ) ;@ @ " @ @ "


@ il lato soppresso un cappio, incidente il vertice ; allora"gr gr gr grZ Z Z Z! !

( ) ( ) ( ) ( )? ? / /" " " "( ) ( ) , ( ) ( )@ @ " @ @ "

e naturalmente

gr gr gr grZ Z Z Z! !( ) ( ) ( ) ( )? ? / /( ) ( ) e ( ) ( ) per tutti gli altri vertici ,@ @ @ @ @

cosicch ancora

! ! ! !@ @ @ @i i i i

gr gr gr grZ Z Z Z! !( ) ( ) ( ) ( )? ? / /( ) ( ) e ( ) ( ) .@ @ " @ @ "

In ogni caso, per lipotesi di induzione,! !@ @i i

gr grZ Z! !( ) ( )? /( ) e ( )@ 5 " @ 5 "

da cui ! !@ @i i

gr grZ Z( ) ( )? /( ) e ( )@ " 5 " @ " 5 "

e infine ! !@ @i i

gr grZ Z( ) ( )? /( ) ( )@ @ 5

come si voleva dimostrare.

1.4 - Isomorfismo.Siano ( , , ) e ( , , ) grafi. Si dice tra e Z i _ + Z i _ + Z Z" " " " # # # # " # isomorfismo

una coppia ( , ) tale che::

Appunti Di Teoria Dei Grafi

Documents

Transcript of Appunti Di Teoria Dei Grafi