Samuele Mongodi - samuele.mongodi@gmailsamuele/oli/qrafi.pdf · 2014. 8. 25. · Samuele Mongodi -...
45
Transcript of Samuele Mongodi - samuele.mongodi@gmailsamuele/oli/qrafi.pdf · 2014. 8. 25. · Samuele Mongodi -...
Quest’opera e soggetta alla licenza Creative CommonsAttribuzione - Non commerciale - No opere derivate 3.0 Italia
http://creativecommons.org/licenses/by-nc-nd/3.0/it/legalcode
1 I problemi di un museo
In citta hanno aperto un nuovo museo della Matematica; il direttore, preparando le visite guidate,si trova di fronte al seguente problema.
Problema 1 Il museo ha 20 stanze, ognuna collegata ad altre 3. E’ possibile organizzare unavisita guidata che parta da una stanza e le visiti tutte passando in ognuna una sola volta, fino aritornare in quella di partenza?
Certo, ci sono alcune domande che dovrebbero venire spontanee nel leggere il quesito:
• quanti modi diversi ci sono di disporre le stanze del museo come descritto?
• importa da quale stanza si parte?
• puo essere che si riesca (in questo museo o in un altro) ad organizzare una visita che toc-chi tutte le stanze una volta sola, ma che non sia possibile farla terminare nella stanza dipartenza?
e leggendo queste domande, soprattutto la prima, dovrebbe venire in mente un’altra questione:cosa vuol dire diversi?
Il museo, essendo appena aperto, ha bisogno di personale; il direttore ha bisogno di un guardiano,di una guida, di qualcuno che venda i biglietti, di qualcuno che faccia le pulizie e di qualcuno chesi occupi della pubblicita.
Problema 2 Si presentano 5 persone per questi 5 lavori; ognuna e qualificata per alcuni di questilavori e non per altri. In quali dei seguenti casi e possibile assegnare ogni candidato ad unaoccupazione?
1. la prima persona e qualificata solo per uno di questi, la seconda per due e cosı via;
2. la prima e la seconda persona sono qualificate per due lavori, la terza e la quarta per tre, conla condizione che le qualifiche di uno non includano mai completamente le qualifiche di unaltro, mentre la quinta per un lavoro solo.
Ovviamente, una domanda piu interessante puo essere di determinare in quali casi e possibileassegnare i lavori secondo le qualifiche.
Il museo raccoglie 10 argomenti matematici e l’organizzatore dell’esposizione propone al direttoredi commissionare ad un artista una scultura, in cui ogni argomento e rappresentato con un suosimbolo e tra argomenti collegati vi e una striscia di metallo. Il direttore, pero, preferisce i dipinti...
Problema 3 Ogni argomento e collegato ad altri 3; e possibile dipingere i 10 simboli degli argo-menti e tracciare tra ogni due argomenti collegati una linea (anche curva), di modo che due lineedi collegamento non si intersechino tra di loro?
Certo, se ci fossero stati solo due collegamenti da ogni argomento, sarebbe stato piu facile...
Il guardiano del museo deve controllare gli allarmi, dopo aver chiuso e fatto uscire gli ultimivisitatori; c’e un allarme in corrispondenza di ogni porta e lui deve passare a controllarli tutti.
Problema 4 Esiste un percorso che parta da una stanza e passi una e una sola volta per ogniporta, ritornando nella stanza di partenza? Ovviamente, si puo passare da una stessa stanza piuvolte.
Incredibilmente, se ogni stanza fosse stata collegata ad altre 4, la risposta sarebbe stata (forse) piufacile.
Al direttore vengono dati nuovi fondi, per ampliare leggermente il museo, ma sotto alcuni vincoliarchitettonici; lui pero non sa se accettare i soldi, in quanto non sa se la modifica richiesta epossibile.
1
Problema 5 E’ possibile aggiungere una stanza al museo di modo che, comunque, ogni stanza siacollegata ad altre 3? Si potrebbe invece toglierne una, chiedendo che ogni stanza sia poi collegataad altre 5? Oppure, lasciando sempre 20 stanze, si potrebbe ristrutturare il museo per avere unastanza collegata ad altre 5 e ogni altra collegata ad altre 4?
D’accordo, il benefattore ha delle richieste strane, ma son pur sempre soldi.
Il direttore e i 5 dipendenti vivono tutti vicini al museo e alcuni di loro si conoscevano gia primadi cominciare a lavorare lı.
Problema 6 Il direttore sostiene che, tra di loro, vi sono 3 persone di cui ognuna conosce gli altridue, oppure vi sono 3 persone di cui nessuna conosce gli altri. Ha ragione?
Furbo, questo direttore...
2 Pensiamoci un po’
Consideriamo, uno per volta, i problemi esposti nella sezione precedente e cerchiamo di isolare lecaratteristiche essenziali alla loro risoluzione. Ad alcuni daremo risposta, ad altri no.
2.1 La visita guidata
Senza informazioni sulla forma delle stanze e sulla loro disposizione, tracciare una cartina del museopuo diventare abbastanza complicato; del resto, e anche inutile, al fine di fornire una risposta alquesito. Indichiamo le stanze con i numeri da 1 a 20 e proviamo a descrivere i collegamenti:
i. 1 con 5,2,6
ii. 2 con 1,3,7
iii. 3 con 2,4,8
iv. 4 con 3,5,9
v. 5 con 4,1,10
vi. 6 con 1,11,12
vii. 7 con 2,12,13
viii. 8 con 3,13,14
ix. 9 con 4,14,15
x. 10 con 5,15,11
xi. 11 con 10,6,16
xii. 12 con 6,7,17
xiii. 13 con 7,8,18
xiv. 14 con 8,9,19
xv. 15 con 9,10,20
xvi. 16 con 11,20,17
xvii. 17 con 12,16,18
xviii. 18 con 13,17,19
xix. 19 con 14,18,20
2
xx. 20 con 15,19,16
Questa descrizione e evidentemente troppo dettagliata; infatti ogni collegamento compare duevolte. Quindi, ci sono 3 ⋅ 20/2 = 30 collegamenti. Proviamo a dare una rappresentazione grafica,disegnando dei cerchi numerati e collegandone due se le corrispondenti stanze sono adiacenti.
1
2
3
4
56
7
8
9
10
11
12
13
14
1516
17
18
19
20
Certo, questa figura e abbastanza confusa da impedire quasi ogni ragionamento; proviamo a di-sporre in modo diverso i cerchi, in modo da evitare troppe sovrapposizioni tra le linee che licollegano.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Ecco, qui si puo anche provare a ragionare. Il nostro problema e visitare tutte le stanze una e unasola volta, partendo e tornando nella stessa stanza, ovvero mettere in sequenza i numeri da 1 a20 di modo che due numeri vicini corrispondano a due stanze collegate. Proviamo a guardare laseconda figura; le stanze sono disposte su tre cerchi concentrici. Se ci facciamo guidare da questafelice disposizione, possiamo pensare di percorrere un cerchio alla volta e sperare che alla fine sichiuda tutto.
3
Cominciamo! Ovviamente partiamo da 1; dopo di che 2,3,4,5. Ora non possiamo tornare in 1,quindi scendiamo al prossimo cerchio, andando a 10; se poi vorremo risalire alla stanza 1, dovremopassare per la stanza 6 alla fine, quindi non ci passiamo adesso e dunque prendiamo la direzioneopposta: 15,9,14,8,13,7,12. Attenzione! C’e ancora un cerchio e dunque non possiamo ancorapassare dalla 6. Piuttosto, scendiamo all’ultimo cerchio, andando alla 17. Da qui, per forza,18,19,20,16 e, risalendo, 11,6,1.Ce l’abbiamo fatta: il nostro percorso e
1,2,3,4,5,10,15,9,14,8,13,7,12,17,18,19,20,16,11,6,1
Ovvero, in figura
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Ora, riflettiamo un poco: se anche avessimo numerato diversamente le stanze non sarebbe cambiatonulla. O anche, addirittura, se non avessimo numerato per nulla le stanze; nel disegno il problemasarebbe sempre stato quello di seguire le linee passando per ogni cerchio una volta sola, partendoe tornando nello stesso. Inoltre, sebbene la diversa disposizione grafica ci abbia aiutato, i duedisegni di prima erano equivalenti per il problema, infatti nel primo avremmo comunque trovatoquest’altro percorso:
4
1
2
3
4
56
7
8
9
10
11
12
13
14
1516
17
18
19
20
Infine, se avessimo rappresentato la situazione cosı
la soluzione sarebbe stata ancora piu ovvia (il cerchio esterno); certo, non era ovvio, all’inizio, chefosse possibile rappresentare in questo modo i collegamenti tra le stanze.Un piccolo esercizio: provate a mettere i numeri delle stanze nell’ultima figura, di modo checorrisponda alle precedenti.
2.2 I 5 lavori
Abbiamo i nostri 5 futuri dipendenti (che chiamiamo A,B,C,D,E) e i 5 possibili lavori (cheindichiamo con 1,2,3,4,5); ad ogni lettera associamo dunque un po’ di numeri, che indicano ilavori per cui una persona e qualificata. Ad esempio, nel primo caso proposto, a meno di cambiarei numeri che corrispondono ai lavori1, ci troveremo in questa situazione:
AÐ→ 11Questo passaggio e importante; se non vi convince, fate un po’ di prove!!
5
B Ð→ 1,2
C Ð→ 1,2,3
D Ð→ 1,2,3,4
E Ð→ 1,2,3,4,5
che puo anche essere rappresentata con la seguente figura:
E
D
C
B
A
5
4
3
2
1
La richiesta ora puo essere riformulata chiedendo di trovare, per ogni lettera, un numero a cuie collegata, di modo che lo stesso numero non capiti con due lettere diverse. In questo caso,ovviamente possiamo farlo, assegnando
A→ 1 B → 2 C → 3 D → 4 E → 5
Ovvero, scegliendo nella figura alcune linee, di modo che non ve ne siano mai due concorrenti inun cerchio:
E
D
C
B
A
5
4
3
2
1
6
Tra li resto, un facile ragionamento mostra che questo e l’unico modo di fare l’assegnazione deilavori.La seconda situazione descritta e, invece piu complicata; alcune sue possibili rappresentazioni sonole seguenti:
E
D
C
B
A
5
4
3
2
1
E
D
C
B
A
5
4
3
2
1
E
D
C
B
A
5
4
3
2
1
Come si puo verificare con un po’ di lavoro, non si puo passare da una situazione all’altra sem-plicemente permutando lettere e numeri; ad esempio, nel secondo e nel terzo caso, dal numero 1partono 4 linee, cosa che non succede per nessun numero del primo caso, del resto, nel secondo casodal numero 2 parte una sola linea, mentre negli altri due casi da ogni numero ne partono semprealmeno 2.Eppure, in tutti questi casi, l’assegnazione
A→ 2 B → 3 C → 4 D → 5 E → 1
risolve il problema.Vi sono altre situazioni possibili, che, come quelle sopra, non si ottengono tra loro scambiando lepersone o i lavori; in ciascuna di queste e possibile assegnare ad ogni persona un lavoro diverso.Puo essere un esercizio interessante trovare quali sono queste altre configurazioni.
2.3 Scultura vs Pittura
Non avendo noi troppe velleita artistiche, indichiamo gli argomenti con i numeri da 1 a 10 e, perora, indichiamo semplicemente i collegamenti tra loro, senza preoccuparci di dove si intersecano lelinee. Otteniamo, ad esempio, una delle seguenti figure.
1
2
34
5
6
7
8 9
10
1
2
3
4
5
6
7
8
9
10
7
Evidentemente, nessuna di queste due figure puo andar bene come dipinto, per il direttore del mu-seo; meno evidente e mostrare che non e possibile ottenere una figura che rappresenti la situazionedescritta e in cui le linee non si intersechino.
2.4 Controllando gli allarmi
Ormai non provochera grande stupore rappresentare le stanze con un po’ di cerchietti e le portecon collegamenti tra questi; la richiesta che facciamo questa volta e un percorso che utilizzi tuttele linee della figura e parta e finisca nella stessa stanza.Riportiamo il disegno fatto nel primo problema:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Supponiamo di partire dalla stanza 1 e di andare nella stanza 2; in questo modo avremo utilizzatola linea tra queste, che quindi andra eliminata. Ora, sia che andiamo in 3 o in 7 da 2, avremoutilizzato anche un’altra linea uscente da 2 e quindi ne rimarra solo una. Questo vuol dire che,per usare quest’ultima linea, dovremo andare da un’altra stanza alla numero 2 e a questo puntonon potremo piu muoverci. Quindi non riusciremo mai a tornare alla 1. Se anche dalla 1 fossimoandati alla 5 o alla 6, avremmo potuto fare lo stesso ragionamento, quindi il cammino richiestonon si puo realizzare.Come accennato, nel caso di 20 stanze in cui ognuna e collegata ad altre 4, la risposta e forse piufacile, in quanto il cammino e possibile. Lasciamo come esercizio di trovarlo.
8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1718
1920
2.5 Ristrutturazioni
Cerchiamo di capire come potrebbe essere fatto il nuovo museo. Con 21 stanze, in cui ognunae collegata ad altre 3; questo vuol dire che in ogni stanza ci devono essere 3 porte verso altrestanze. Quindi, in una eventuale rappresentazione del museo con cerchi e linee, avremo 21 cerchie da ognuno di essi 3 linee; quindi ci saranno 3 ⋅ 21 linee? Beh, quasi, in quanto ogni linea uniscedue cerchi e quindi in questo modo viene contata due volte; quindi dovremmo avere 3 ⋅ 21/2 linee(ovvero, porte), ma questo numero non e intero. Quindi la ristrutturazione non e possibile.Del resto, non possiamo nemmeno avere 19 stanze ognuna collegata ad altre 5 perchE dovremmoavere 5 ⋅ 19/2 porte, che non e possibile.Ora, veniamo all’ultimo progetto. Sappiamo che si puo costruire un museo di 20 stanze, in cuiognuna e collegata ad altre 4, visto che lo abbiamo disegnato nel paragrafo precedente; il problemae inserire un altro collegamento. Questo aumenterebbe il numero di porte di due stanze e quindinon va bene; dunque questa costruzione non funziona. Ora, proviamo a contare quante porte cidovrebbero essere: in 19 stanze avremo 4 porte e in una sola ne avremo 5, quindi 19⋅4+5 = 76+5 = 81e il doppio del numero delle porte (per lo stesso ragionamento di prima), ma e un numero disparie quindi ci vorrebbero 81/2 porte, che non e possibile.Insomma, queste ristrutturazioni non si possono proprio fare.
2.6 Vicini di casa
Rappresentiamo il direttore e i suoi dipendenti con i numeri da 1 a 6 (non ve lo sareste maiaspettato, vero?) e disegnamo un tratto rosso tra quelli che si conoscono, un tratto blu tra quelliche non si conoscono. Quello che sostiene il direttore e che possiamo sempre trovare un triangoloblu o un triangolo rosso.Ad esempio, potremmo ottenere una situazione del genere:
9
1
23
4
5 6
In questo caso, vi sono 3,5,6 che si conoscono l’un l’altro, mentre tra 2,4,5 nessuno conosce glialtri due. Purtroppo, ci sono molti modi di colorare le 15 linee che collegano 6 punti e non sarebbemolto conveniente esaminarli tutti per verificare che in ognuno ci sono dei triangoli di un solocolore.Cerchiamo di ragionare: prendiamo il cerchio 1; da lui escono 5 linee. Dovendo queste essere bluo rosse, ce ne saranno tre dello stesso colore; poniamo ce ne siano tre blu (se ce ne sono tre rossi,basta scambiare in quel che segue le parole blu e rosso) che collegano i cerchi i, j, k con 1 (nelnostro esempio, 3,5,6).Allora, se una delle linee tra i e j, tra j e k o tra k e i e blu, abbiamo il nostro triangolo blu;altrimenti tutte queste linee sono rosse (come accade nell’esempio), ma allora i, j, k sono i verticidi un triangolo rosso. Quindi, in ogni caso, abbiamo un triangolo monocromatico.E’ interessante notare che con 5 persone non e piu vero nulla: nella figura seguente non c’e nessuntriangolo tutto rosso o tutto blu.
1
2
3
4
5
3 Un po’ di teoria
In tutti i problemi che abbiamo esaminato ci siamo serviti (in maniera piu o meno naturale) difigure con pallini e linee; le informazioni che volevamo trasmettere erano legate a come erano fattii collegamenti tra questi pallini. Ecco dunque il concetto di grafo: un grafo e un insieme di vertici(i pallini) collegati da archi (o lati); un arco sara, formalmente, la coppia di vertici che congiunge.Per ora, i collegamenti tra i vertici non avranno una direzione, quindi l’arco (1,2) e l’arco (2,1)saranno la stessa cosa. Inoltre, per semplicita, escluderemo che possa esistere piu di un arco tradue vertici o un arco da un vertice in sE; graficamente, escluderemo i due seguenti casi
10
A B 1
Un grafo che rispetta queste condizioni si dira semplice; se ammetteremo che si presentino configu-razioni come la prima, parleremo di grafi con archi multipli, mentre se ammetteremo configurazionicome la seconda, parleremo di grafi con loops (dall’inglese, tradotto a volte con cappi).Nel caso si vogliano distinguere l’arco (1,2) e l’arco (2,1), potremo mettere delle freccie lungo gliarchi e parleremo di grafi diretti (o orientati); simili strutture possono essere utili, ad esempio, perdescrivere i collegamenti tra diversi luoghi, nel caso che alcune vie di comunicazione possano esserepercorse solo in un senso.
A B
CD
E F G
Ribadiamo che, se non diversamente specificato, considereremo solo grafi senza archi multipli, senzacappi, non diretti, ovvero semplici.In maniera formale, un grafo semplice G e una coppia (V,E), dove V e un insieme qualsiasi(l’insieme dei vertici) e E e un insieme di sottoinsiemi di 2 elementi di V . Ad esempio,
V = {1,2,3,4,5} E = {{1,2},{1,3},{2,3},{1,4},{2,5},{1,5}}
rappresenta il grafo
1
23
45
3.1 Qualche grafo speciale
Il primo grafo che viene in mente alla fantasia malata del matematico e, ovviamente, un casodegenere, ovvero il grafo nullo su n vertici, che e fatto da n vertici e nessun arco (alcuni esempinella Figura 1).Non molto interessante, vero? Il suo opposto e il grafo completo su n vertici che e un grafo formatoda n vertici e da tutti gli archi possibili. Di solito si indica con Kn. PoichE deve esistere un arcoper ogni coppia di vertici, il numero di archi sara proprio il numero di coppie possibili tra n vertici,ovvero n(n−1)/2; la Figura 2 riporta i grafi completi per i primi 5 valori di n. Come si puo notare,K1 e anche il grafo nullo con un vertice.
11
(a) n = 1 (b) n = 2 (c) n = 3
Figura 1: Grafi nulli
(a) K1 (b) K2 (c) K3 (d) K4 (e) K5
Figura 2: Grafi completi
Un’altra classe di grafi interessante e quella formata dai grafi ciclici ; il grafo ciclico su n vertici,indicato di solito con Cn, e un grafo in cui ogni vertice e estremo esattamente di due archi. Taligrafi sono, in pratica, i poligoni di n lati, come si puo vedere nella Figura 3.
(a) C3 (b) C4 (c) C5 (d) C6
Figura 3: Grafi ciclici
Un grafo lineare2 su n vertici, indicato con Ln, e descritto dai seguenti insiemi di vertici e archi:
V = {1,2, . . . , n} E = {{1,2},{2,3}, . . . ,{n − 1, n}}
Alcuni esempi nella Figura 4.
(a) L1 (b) L2 (c) L3 (d) L4
Figura 4: Grafi lineari
Citiamo poi, per completezza, il grafo bipartito completo su (m,n) vertici; tale grafo si indica conKm,n ed e composto da due insiemi di vertici V1 e V2 contenenti m ed n vertici. Ogni vertice diV1 e collegato a tutti i vertici di V2 e viceversa, mentre non vi sono archi tra due vertici di V1 o diV2. In Figura 5 possiamo vedere alcuni esempi.Inoltre, vi sono 5 grafi associati ai 5 solidi platonici (tetraedro, ottaedro, cubo, dodecaedro, ico-saedro), i cui vertici corrispondono ai vertici dei solidi e i cui archi rappresentano gli spigoli; liriportiamo nella Figura 6.
2Questo nome non e standard: in inglese, questo tipo di grafo viene chiamato path graph (grafo cammino) eindicato con Pn
12
(a) K3,1 (b) K3,2 (c) K3,3
Figura 5: Grafi bipartiti completi
(a) Tetraedro (b) Ottaedro (c) Cubo
(d) Dodecaedro (e) Icosaedro
Figura 6: Grafi dei solidi platonici
3.2 Grafi isomorfi, sottografi, cicli e cammini
Negli esempi con cui abbiamo cominciato queste note, abbiamo piu volte notato che grafi che sicorrispondevano a meno di permutare i nomi dei vertici erano, ai fini dei nostri problemi, equi-valenti. Diciamo quindi che due grafi sono isomorfi se c’e un modo di far corrispondere i verticidell’uno con i vertici dell’altro, in modo da portare vertici collegati da un arco in vertici collegatida un arco. Consideriamo i due grafi riportati nella Figura 7.Se facciamo corrispondere i due insiemi di vertici nel modo seguente
1→ 1 2→ 4 3→ 7 4→ 3 5→ 6 6→ 2 7→ 5
otteniamo che i lati dell’ettagono nella Figura 7a diventano le diagonali (che sottendono 3 lati)dell’ettagono nella Figura 7b, mentre le diagonali (che sottendono 2 lati) dell’ettagono nella Figura7a diventano i lati dell’ettagono nella Figura 7b.Anche i tre grafi della Figura 8 sono isomorfi.Formalmente, dati due grafi G = (V,E) e G′ = (V ′,E′), questi si dicono isomorfi se esiste unafunzione bigettiva
f ∶ V → V ′
tale che {v1, v2} ∈ E se e solo se {f(v1), f(v2)} ∈ E′.
13
1
23
4
5
6
7
(a)
1
23
4
5
6
7
(b)
Figura 7
(a) (b) (c)
Figura 8
Un sottografo di un grafo G e un grafo formato da alcuni dei vertici di G e da alcuni degli archi diG, ovvero H ⊆ G se H = (W,F ) e W ⊆ V , F ⊆ E.Ad esempio, K3,3 e un sottografo di K7, come si vede nella Figura 9, dove K3,3 e evidenziato inrosso all’interno di K7.
Figura 9
Ora abbiamo tutti gli strumenti per definire cosa sono un ciclo e un cammino, all’interno di ungrafo; un ciclo in G e un sottografo di G isomorfo a Cn per qualche n (che si dira lunghezza delciclo), mentre un cammino in G e un sottografo di G isomorfo a Ln per qualche n (che si diralunghezza in vertici del cammino, mentre la sua lunghezza in archi sara n − 1). Ad esempio, nelgrafo riportato nella Figura 10, si trovano 7 cicli, mostrati singolarmente nelle Figure 11a-11g.Per quanto riguarda invece il concetto di cammino, esso puo essere inteso come una successionedi vertici, senza ripetizioni, di modo che due vertici consecutivi in tale successione siano collegatida un arco nel grafo; possiamo inoltre dire che un ciclo e un cammino chiuso, ovvero che parte earriva nello stesso vertice.Gli estremi di un cammino sono i vertici che, nel sottografo isomorfo a Ln, appartengono ad unsolo arco; due vertici di un grafo si dicono connessi tra loro se esiste un cammino che li ha comeestremi, un grafo e connesso se ogni coppia di vertici e connessa.
14
A B C D
E F G
H
Figura 10
A B
E
(a)
A B C
E
(b)
B C
E
(c)
C D
E F
(d)
A B C D
E F
(e)
B C D
E F
(f)
F G
H
(g)
Figura 11
Una generalizzazione di cammino e il concetto di percorso: un percorso e, formalmente, una suc-cessione di vertici, non tutti distinti, di modo che due vertici consecutivi nella successione sianocollegati da un arco nel grafo. Ad esempio, nel grafo della Figura 12 possiamo trovare un camminoche contiene tutti i vertici e un percorso che passa per tutti gli archi. Esplicitamente, il camminoABCDEFG contiene tutti i vertici ed e un cammino in quanto e una successione di vertici tuttidistinti, in cui due successivi sono collegati da un arco (ad esempio ABAF non e un cammino,perche ripete il vertice A, mentre AEB non lo e perche non esiste l’arco tra A e E; invece, ilpercorso EFDEGDCFGCBFABG passa per tutti gli archi una e una volta sola ed e un percorsoin quanto tra due vertici consecutivi nell’elenco appena fornito c’e sempre un arco del grafo.
A B C D E
F
G
Figura 12: Cammini e percorsi
3.3 I numeri di un grafo
Vi sono alcune quantita numeriche associate ad un grafo che possono permettere di determinarequando due grafi sono o meno isomorfi. Ad esempio, il numero di vertici e il numero di archi diun grafo; infatti, se G e G′ sono isomorfi, hanno lo stesso numero di vertici e di archi. Questi duenumeri si indicano, solitamente, con v(G) e e(G) (questo secondo viene dall’inglese edge) o con ve e se non ci sono ambiguita su quale grafo stiamo considerando.
15
Un altra caratteristica sicuramente comune a due grafi isomorfi e il numero di archi che hanno uncerto vertice come estremo; si dice valenza del vertice v nel grafo G = (V,E) (oppure grado di vin G), e si indica con dG(v) (o semplicemente d(v)), il numero di archi che escono dal vertice v,ovvero il numero di elementi di E che contengono v. Se G = (V,E) e G′ = (V ′,E′) sono isomorfi,tramite una funzione bigettiva f ∶ V → V ′, allora per ogni v ∈ V deve valere dG(v) = dG′(f(v)).Un grafo in cui tutti i vertici hanno la stessa valenza (poniamo sia k), si dice regolare (o k−regolare);il grafo completo Kn e (n−1)−regolare, il grafo nullo e 0−regolare, il grafo ciclico Cn e 2−regolare,il grafo bipartito completo Kn,n e n−regolare, i grafi associati ai poliedri regolari sono regolari.In questi termini, gli estremi di un cammino sono gli unici due vertici che hanno valenza 1 al suointerno.La valenza puo anche essere interpretata come il numero di vertici collegati ad uno dato tramiteun arco; in quest’ottica e ovvio che dG(v) ≤ v(G) e dunque un grafo k−regolare ha almeno k + 1vertici.
Diciamo circonferenza di G la massima lunghezza di un ciclo in G (indicata con circ(G)); definiamoinoltre girth di G (o giro o buco) la minima lunghezza di un ciclo in G (e la indichiamo con g(G)).Nel caso non vi siano cicli in G, si pone convenzionalmente g(G) = −∞ e circ(G) = 0.
Tra i vertici di un grafo connesso possiamo definire una distanza: dG(v,w) e la minima lunghezza(in archi) di un cammino tra v e w. Ovviamente, dG(v,w) = 0 se e solo se v = w; inoltre, altrettantoovviamente dG(v,w) = dG(w, v). Infine, se ho tre vertici v,w, u, sicuramente, un cammino diminima lunghezza da v a u unito ad un cammino di minima lunghezza da u a w produce uncammino tra v e w (forse non di minima lunghezza) quindi ho
dG(v,w) ≤ dG(v, u) + dG(u.w)
E queste tre proprieta ci dicono che abbiamo ragione a chiamare dG distanza.
1
2
3
4
510
15
9
14
8
13
7
12
17
1819
20
16
11
6
Figura 13: Il solito grafo
Facciamo alcuni esempi: consideriamo il grafo del museo riportato nella Figura 13 e calcoliamo ledistanze tra alcuni vertici.Cominciamo col vedere le distanze dal vertice 1: i vertici 2,5,6 sono collegati direttamente a lui,quindi
dG(1,2) = dG(1,6) = dG(1,5) = 1
16
Ora, al vertice 2 sono collegati 3,7, al vertice 6 sono collegati 12,11, al vertice 5 sono collegati4,10, quindi
dG(1,3) = dG(1,7) = dG(1,12) = dG(1,11) = dG(1,10) = dG(1,4) = 2
Proseguendo in questo modo si ottiene che
dG(1,8) = dG(1,13) = dG(1,17) = dG(1,16) = dG(1,15) = dG(1,9) = 3
e infine chedG(1,14) = dG(1,18) = dG(1,20) = 4
dG(1,19) = 5
La massima distanza possibile tra due vertici si chiama diametro di G; quindi in questo casodiam(G) = 5.
3.4 Esercizi
Esercizio 1 Trovare quali dei grafi in figura 14 sono isomorfi, costruendo l’isomorfismo se esisteo dimostrando che non puo esistere.
1
23
4
5 6
(a)
1
23
4
5 6
(b)
1
23
4
5 6
(c)
1
23
4
5 6
(d)
1
23
4
5 6
(e)
1
23
4
5 6
(f)
Figura 14: Esercizio 1
Esercizio 2 Scrivere gli insiemi di archi e vertici per i grafi della figura 14.
Esercizio 3 Elencare tutti i grafi con 4 vertici, a meno di isomorfismo.
Esercizio 4 Dimostrare che non ci puo essere un grafo con 5 vertici di cui uno di valenza 5, unodi valenza 1, uno di valenza 4 e due di valenza 2.
Esercizio 5 Disegnare i 7 sottografi non isomorfi di K3.
Esercizio 6 Trovare 6 grafi con 5 vertici e 5 archi tutti tra loro non isomorfi.
Esercizio 7 Dimostrare che ogni percorso W tra due vertici x, y ∈ V (G) contiene un camminotra x, y come sottografo. Ovvero che togliendo vertici e archi a W si ottiene un cammino tra x e y.
17
Il complementare di G = (V,E) e il grafo Gc = (V c,Ec) che ha come vertici gli stessi di G (e quindiV c = V ) e come archi tutti e soli gli archi che non stanno in E. Ovvero, (x, y) ∈ Ec se e solo se(x, y) /∈ E.Esercizio 8 Trovare un grafo G di 5 vertici isomorfo al suo complementare.
Esercizio 9 Dimostrare che il complementare di un grafo disconnesso e connesso.
Esercizio 10 Dimostrare che non esiste un grafo di 6 vertici isomorfo al proprio complementare.
4 Alcune proprieta elementari
Per mostrare quali siano le tecniche e le problematiche della teoria dei grafi, raccogliamo in questasezione alcuni risultati che legano le quantita e le proprieta definire nelle pagine precedenti. Sup-porremo, nel seguito, che ogni grafo abbia un numero finito di vertici. Cominciamo col dire che,se da ogni vertice escono abbastanza archi, il grafo e connesso.
Proposizione 1 Un grafo di n vertici in cui ogni vertice ha valenza almeno n/2 e connesso.
Dim : Prendiamo due vertici v e w e cerchiamo di mostrare che c’e un cammino tra loro. Conside-riamo l’insieme dei vertici che si possono raggiungere da v, ovvero quelli per cui esiste un camminotra essi e v:
R(v) = {u ∶ esiste un cammino da v a u}
e allo stesso modo consideriamo i vertici che si possono raggiungere da w
R(w) = {u ∶ esiste un cammino da w a u}
Sappiamo che da v escono almeno n/2 archi e cosı pure da w; inoltre, R(v) contiene v e R(w)contiene w. Quindi R(v) e R(w) hanno almeno n/2 + 1 elementi a testa. Del resto, l’unione diR(v) e R(w) e contenuta nell’insieme dei vertici di G, quindi ha al massimo n elementi. Dallateoria degli insiemi sappiamo che
∣R(v) ∪R(w)∣ = ∣R(v)∣ + ∣R(w)∣ − ∣R(v) ∩R(w)∣
e quindi l’intersezione deve avere almeno due elementi, perche si deve avere
n ≥ ∣R(v)∣ + ∣R(w)∣ − ∣R(v) ∩R(w)∣ ≥ n/2 + 1 + n/2 + 1 − ∣R(v) ∩R(w)∣
Se questi due elementi sono v e w, vuol dire che c’e un arco da v a w e quindi abbiamo trovatoil nostro cammino; se invece c’e un elemento u nell’intersezione, questo vuol dire che u ∈ R(v),quindi c’e un cammino da v a u e contemporaneamente u ∈ R(w), quindi c’e un cammino da u aw. Mettendo assieme questi due cammini, otteniamo un cammino da v a w, come volevamo. ◻
Osserviamo che non e detto il viceversa: non tutti i grafi connessi hanno ogni vertice di valenzamaggiore o uguale a n/2. Si consideri ad esempio il grafo ciclico Cn o il grafo lineare Ln; essi hannovertici di valenza 1 o 2, sono connessi e possono avere quanti vertici vogliamo.Osserviamo anche che il risultato non e piu vero se mettiamo qualcosa meno di n/2: il grafo nellaFigura 15 ha 6 vertici, ognuno di valenza 2, ed e sconnesso; infatti non si puo andare da uno deivertici 1,2,3 a uno dei vertici 4,5,6 con un cammino.
1
2
3
4
5
6
Figura 15: Grafo sconnesso con 6 vertici di valenza 2
18
Proposizione 2 In un grafo il numero di vertici di valenza dispari e pari.
Dim : Per dimostrare questa proposizione, contiamo in un modo un poco complicato il numerodi archi di un grafo.Iniziamo con l’indicare con ni il numero di vertici di valenza i; da uno qualunque di questi verticiusciranno dunque i archi, per un totale di ini archi. Quindi, potremmo credere che il numero diarchi del grafo sia
s = 0n0 + 1n1 + 2n2 + . . . +mnmdove m e la massima valenza di un vertice del grafo. Pero, in realta, il numero scritto e il doppiodel numero di archi: infatti ogni arco compare nella conta due volte, una per ogni suo estremo.Quindi il numero di archi e
s
2Questo ci dice che s e un numero pari; osserviamo che
s = (0n0 + 2n2 + 4n4 + . . .) + (1n1 + 3n3 + 5n5 + . . .)
la prima parentesi e somma di numeri pari e dunque e pari, percio deve esserlo anche la seconda.Ora osserviamo che
1n1 + 3n3 + . . . = (n1 + n3 + . . .) + (2n3 + 4n5 + . . .)il primo membro e pari, la seconda parentesi e pari, quindi anche
n1 + n3 + . . .
e pari, ma questo e esattamente il numero di vertici di valenza dispari, che quindi e pari. ◻Dalla dimostrazione otteniamo anche la formula
∑i∈Nini = 2e
ma e anche facile vedere che
∑i∈Nini = ∑
v∈Gd(v)
ovvero che la somma a sinistra non e altro che la somma di tutte le valenze dei vertici del grafo.Anche questa e quindi uguale al doppio del numero degli archi.
Proposizione 3 Se ogni vertice di G ha valenza almeno k ≥ 2, allora esistono un cammino dilunghezza k e un ciclo di lunghezza k + 1.
Dim : Sia P = {x1, x2, . . . , xm} un cammino in G, rappresentato tramite la successione dei suoivertici, di modo che tra xi e xi+1 vi sia un arco e che xi ≠ xj se i ≠ j.Supponiamo che m < k e consideriamo l’insieme
N(xm) = {y ∈ V ∣ dG(xm, y) = 1}
detto intorno di xm e fatto da tutti i vertici che sono connessi a xm con un arco. Allora, poicheper ipotesi ∣N(xm)∣ ≥ k, c’e almeno un vertice z ∈ N(xm) che non e in P ; dunque possiamo porrexm+1 = z e costruire il cammino piu lungo
P ′ = {x1, . . . , xm, xm+1}
Questa costruzione funziona finche ho un cammino di lunghezza minore di k e dunque ci garantisceche il piu lungo cammino in G ha lunghezza almeno k.Per la seconda parte, supponiamo che P = {x1, . . . , xm} sia un cammino massimale, ovvero nonestendibile (quindi con m > k); il fatto che non si possa estendere vuol dire che N(xm) contienesolo vertici di P . Sempre per l’ipotesi sulla minima valenza di ogni vertice, N(xm) avra almeno kelementi, quindi il piu piccolo indice i per cui xi appartiene a N(xm) sara al piu n − k.Consideriamo quindi il ciclo C = {xi, xi+1, . . . , xm, xi} dove i e l’indice descritto sopra; per quantodetto i ≤ n − k e dunque la lunghezza di C sara almeno k + 1. ◻Nel dimostrare la presenza di un ciclo di lunghezza almeno k + 1, abbiamo sfruttato l’esistenzadi un cammino che non puo essere prolungato, che e garantita dall’assunzione che il grafo abbiaun numero finito di vertici. Il risultato precedente ci dice che la circonferenza di G e sicuramentemaggiore della minima valenza di un suo vertice; vediamo ora il legame tra girth e diametro.
19
1 2 i m-2 m-1 m
⋯ ⋯
Figura 16: Cammino e ciclo di lunghezza almeno k e k + 1.
Proposizione 4 In un grafo G con almeno un ciclo si ha g(G) ≤ 2diamG + 1.
Dim : Se g(G) ≥ 2diamG + 2, allora esiste un ciclo C di lunghezza 2diamG + 2; presi due verticix, y di C, si ha dG(x, y) < diamG + 1, per definizione di diametro. Quindi esiste un cammino{x,x1, . . . , xk, y} di lunghezza minore di diamG + 1.Se ora scegliamo x, y che distano esattamente diam G+ 1 in C, otteniamo che il cammino minimoche li congiunge non sta in C, quindi unendo il cammino minimo che li congiunge in G al camminominimo che li congiunge in C otteniamo un ciclo di lunghezza al piu 2diam G + 1. ◻Per comprendere meglio il legame tra i vari numeri che abbiamo associato, vediamo ora un risultatoche lega girth, valenza e numero dei vertici. Lo riportiamo anche per il metodo di dimostrazione,che contiene alcune idee molto interessanti.
Proposizione 5 Un grafo G k−regolare con g(G) = 2m + 1 dispari ha almeno
1 + k + k(k − 1) + . . . + k(k − 1)m−1
vertici
Dim : Sia x un vertice di G; definiamo gli insiemi
Ni(x) = {y ∈ V (G) ∣ dG(x, y) = i}
per i = 0, . . . ,m.Notiamo che ∣N0(x)∣ = 1 e ∣N1(x)∣ = k (in quanto G e k−regolare); inoltre, Ni(x) e Nj(x) sonodisgiunti se i ≠ j.Da ogni y ∈ Ni(x) (con i ≥ 1) parte uno e un solo arco che ha l’altro estremo in Ni−1(x); se infattivi fossero due archi, da y a z1 e da y a z2 con z1, z2 ∈ Ni−1(x), allora potremmo andare da x a z1con i− 1 archi, da z1 a y, da y a z2 e poi da z2 a x con i− 1 archi, ottenendo un ciclo di lunghezza2i ≤ 2m < g(G), il che e assurdo. D’altra parte, deve esistere almeno un arco da y a un punto diNi−1(x), per la definizione degli insiemi Ni(x).Ora, questo significa che ad ogni vertice di Ni(x) corrispondono k − 1 vertici di Ni+1(x) e a verticidiversi di Ni(x) corrispondono insiemi disgiunti di vertici di Ni+1(x).Dunque ∣Ni+1(x)∣ = (k − 1)∣Ni(x)∣, se i ≥ 1, e quindi ∣Ni(x)∣ = k(k − 1)i−1 se i ≥ 1; ora, poiche gliNi sono tutti disgiunti, di certo
V (G) ⊇ N0(x) ∪N1(x) ∪ . . . ∪Nm(x)
quindi∣V (G)∣ ≥ 1 + k + k(k − 1) + . . . + k(k − 1)m−1
come volevamo dimostrare. ◻E’ abbastanza notevole che la stessa espressione intervenga come massimo possibile per il numerodi vertici di un grafo k−regolare di cui sia fissato il diametro m = diamG.
Proposizione 6 Un grafo G k−regolare con diamG =m ha al piu
1 + k + k(k − 1) + . . . + k(k − 1)m−1
vertici.
Dim : Sia x ∈ V (G), allora
N0(x) ∪N1(x) ∪ . . . ∪Nm(x) = V (G)
Inoltre, essendo il grafo k−regolare, al piu si avra ∣Ni+1(x)∣ ≤ (k − 1)∣Ni(x)∣ per i ≥ 1. Quindi
∣V (G)∣ ≤ 1 + k + k(k − 1) + . . . + k(k − 1)m−1
come volevamo dimostrare. ◻
20
4.1 Alberi
Un albero e un grafo connesso che non contiene cicli; una foresta e un grafo che non contiene cicli.In particolare, una foresta e un grafo le cui componenti connesse sono alberi.Diremo nel seguito che il grafo G′ = (V ′,E′) e ottenuto dal grafo G = (V,E) eliminando il verticev se V ′ = V ∖ {v} e E′ e formato da tutte le coppie di E che non contengono v. Ad esempio,eliminando il vertice 1 dal grafo della figura 17a otteniamo il grafo della figura 17b.
2
34
5
6 7
1
(a)
2
34
5
6 7
(b)
Figura 17: Eliminazione del vertice 1.
Allo stesso modo, aggiungendo un vertice ad un sottografo, si aggiungono anche tutti gli archi dalsottografo al nuovo vertice.Togliere un arco e invece una operazione molto piu semplice: dal grafo G = (V,E), dato un arcoe ∈ E, otteniamo togliendo e il grafo G′ = (V,E′) con E′ = E ∖ {e}; ovviamente G′ e un sottografodi G
Proposizione 7 Sia G un grafo connesso di n vertici, allora esiste un sottografo T con n verticiche e un albero.
Dim : Se G e un albero, allora poniamo T = G; se G non e un albero, conterra un ciclo. Eliminandoun arco di questo ciclo otteniamo un sottografo G′ che e ancora connesso. Se G′ e un albero,poniamo G′ = T , altrimenti contiene un ciclo e possiamo proseguire. In questo modo, in un numerofinito di passi (poiche G ha al piu n(n − 1)/2 archi), arriviamo ad ottenere un albero T comesottografo di G. ◻
Quindi possiamo affermare che G = G[T ]; diciamo allora che T e un albero generatore per G.Studiamo alcune proprieta degli alberi.
Proposizione 8 Per un grafo G, le seguenti affermazioni sono equivalenti.
(i) G e un albero.
(ii) Ogni due vertici di G sono collegati da un unico cammino in G.
(iii) G e minimalmente connesso, ovvero togliendo un qualunque arco si sconnette G.
(iv) G e massimalmente aciclico, ovvero G non contiene cicli, ma se si aggiunge un arco tra duevertici non ancora adiacenti, il grafo ottenuto ha almeno un ciclo.
Dim : Dimostriamo che il fatto che G sia un albero e equivalente alle altre tre affermazioni
(i)⇔ (ii) Se G e un albero, e connesso, quindi tra due vertici x, y ∈ V (G) c’e almeno un cammino;se ci fossero due cammini P = {x,x1, . . . , xk, y} e P ′ = {x, y1, . . . , yh, y}, potremmo considerare ilpiu piccolo i tale che xi ≠ yi e poi li piu piccolo j > i tale che yj ∈ V (P ), allora prendendo ilcammino in P ′ da yi−1 = xi−1 a yj e poi seguendo P da yj a xi−1 = yi−1 si otterra un ciclo, il chenon e possibile se G e un albero.Del resto, se in G tra due vertici c’e sempre uno o un solo cammino, G e connesso e G non puocontenere cicli, altrimenti tra due vertici del ciclo ci saranno almeno due cammini, le due parti incui da essi viene diviso il ciclo.
21
(i) ⇔ (iii) Come gia detto, G e connesso in quanto e un albero. Sia e = (x, y) un arco di G;supponiamo che, pur togliendo e da G, questo rimanga connesso. Allora esiste un cammino P dax a y che non contiene e, ma dunque P unito all’arco e (percorso nella direzione opportuna) e unciclo di G, che non puo contenere cicli in quanto albero e dunque togliendo l’arco e, G diventasconnesso.Se d’altra parte G e minimalmente connesso, e connesso e non puo contenere cicli, infatti togliendoun arco da un ciclo questo rimane connesso.
(i)⇔ (iv) Essendo un albero, G non contiene cicli. Supponiamo che aggiungendo un arco (x, y)tra due vertici inizialmente non adiacenti non ci siano comunque cicli; questo vuol dire che il grafocosı ottenuto e ancora un albero, ma per quanto dimostrato un albero e minimalmente connessoe dunque togliendo un arco si disconnette. Se ora togliamo l’arco (x, y), riotteniamo G, che devequindi essere sconnesso, ma questo e assurdo.Del resto, se G e massimalmente aciclico, G e connesso, altrimenti aggiungendo un arco tra verticidi due componenti connesse diverse non si otterrebbe nessun ciclo ed inoltre e aciclico. Dunque eun albero. ◻
Osserviamo che un sottografo connesso di un albero e un albero, in quanto, ad esempio, e ancoraminimalmente connesso.
Figura 18: Esempio di albero
Dimostriamo ora una proposizione su come enumerare i vertici di un grafo connesso.
Proposizione 9 I vertici di un grafo G connesso possono essere sempre enumerati come v1, . . . , vndi modo che, per ogni i = 0, . . . , n − 1, il grafo ottenuto da G eliminando vn, . . . , vn−i e ancoraconnesso.
Dim : Scegliamo un vertice v1 in G e sia v2 un vertice in N1(v1); chiamiamo G1 il sottografocomposto dal solo vertice v1 e G2 il sottografo composto da v1, v2 e dall’arco che li congiunge.Notiamo che G1 e ottenuto da G eliminando tutti i vertici che non sono v1 e G2 e ottenuto da Geliminando tutti i vertici diversi da v1, v2.
v1
vk
vj
vi
⋯
⋯
⋯
⋮
⋮
⋯
⋯
C
F
H
⋰
⋱
Figura 19: In rosso il sottografo Gi, in blu il cammino P che termina con i vertici C, vk,H, vj , F, vi,dunque il vertice vi+1 sara F , l’ultimo vertice di P non in Gi.
Ora, supponiamo di aver trovato i vertici v1, . . . , vi e sia Gi il sottografo che si ottiene da Geliminando gli altri vertici; supponiamo che i grafi G1, . . . ,Gi siano connessi. Vogliamo trovare ilprossimo vertice vi+1. Consideriamo v ∈ V (G) ∖ {v1, . . . , vi} e sia P un cammino da v a vi (esiste
22
per ipotesi, poiche G e connesso); scegliamo come vi+1 l’ultimo vertice di P , percorrendolo da v avi, che non sta in Gi (si veda anche la figura 19).In questo modo N1(vi+1) contiene almeno un vertice di Gi e dunque Gi+1 (ottenuto da G eliminandoi vertici diversi da v1, . . . , vi+1) sara connesso.In questo modo otteniamo una successione di vertici v1, . . . , vn come richiesto. ◻
Il grafo ottenuto da G eliminando i vertici che non stanno in un certo sottoinsieme U ⊆ V (G) si dicesottografo di G generato da U e si indica con G[U]; nella dimostrazione precedente, il sottografoGi poteva essere indicato come G[v1, . . . , vi]. Ovviamente si ha G[v1, . . . , vn] = G.
Se applichiamo tale enumerazione ad un albero, otterremo che ogni Gi sara un albero e dunque ilvertice vi avra un solo vertice adiacente in Gi−1 (se ne avesse due, poiche ogni albero e connesso,si otterrebbe un ciclo in Gi).
Proposizione 10 Un grafo connesso di n vertici e un albero se e solo se ha n − 1 archi.
Dim : Se G e un albero composto da 1 solo vertice, ovviamente ha 0 archi; se poi abbiamodimostrato che ogni albero con i < n vertici ha i − 1 archi, dato G albero di n archi, da quantodetto sappiamo che Gn−1 e un albero di n−1 vertici con n−2 archi ed aggiungendo l’ultimo verticevn (che, come detto, ha un solo vertice adiacente in Gn−1), aggiungeremo un solo arco, ottenendoche G ha n − 1 archi.D’altra parte, se G e un grafo connesso di n vertici con n − 1 archi, posso togliere archi fino adottenere un grafo G′ connesso e senza cicli, quindi un albero; ora G′ ha n vertici, dunque ha n − 1archi, per quanto appena detto. Ma quindi G′ = G e G e un albero. ◻
4.2 Grafi bipartiti
Un grafo si dice bipartito (o in generale r−partito) se esistono due (o r) sottoinsiemi V1, V2 di V (G)(o V1, . . . , Vr) disgiunti, la cui unione sia V (G) e tali che non esista un arco di E(G) tra due verticidello stesso sottoinsieme Vi.Esempi di grafo bipartito sono quelli nella figura 5; un esempio di grafo tripartito e presentatonella figura 20.
1
2
3
4
5
6
7
8
Figura 20: Grafo tripartito con V1 = {1,2}, V2 = {3,4,5}, V3 = {6,7,8}.
C’e una comoda descrizione dei grafi bipartiti, che nasce dall’osservazione che un grafo bipartitonon puo contenere cicli di lunghezza dispari.
Proposizione 11 Un grafo e bipartito se e solo se non contiene cicli di lunghezza dispari.
Dim : Innanzitutto, dimostriamo che un grafo bipartito non contiene cicli di lunghezza dispari.Osserviamo che un cammino di lunghezza 1 e un arco e dunque collega un vertice di V1 a un verticedi V2; dunque un cammino di lunghezza 2 ha gli estremi nello stesso sottoinsieme Vi. In generale,dato un cammino P = {x1, . . . , xn}, se x1 sta (ad esempio) in V1, x2 stara in V2, poi forzatamentex3 sara in V1 e cosı via; dunque, a seconda che n sia pari o dispari, xn sara in V1 o in V2. Se dunqueC e un ciclo {x1, x2, . . . , xn, x1} di lunghezza n dispari, il cammino P = {x1, . . . , xn}, supponendoche x1 sia in V1, avra l’estremo xn in V1, per quando detto prima, e dunque x1 si dovra trovare inV2, ma questo e assurdo. Dunque la lunghezza del ciclo deve essere pari.
23
Il viceversa e ben piu complicato; procediamo per passi.
In un grafo senza cicli di lunghezza dispari, due cammini disgiunti tra i medesimi vertici hannoentrambi lunghezza pari o lunghezza dispari.Due cammini sono disgiunti se hanno in comune solo gli estremi; se vi fossero, tra gli stessi vertici,due cammini uno di lunghezza pari e uno di lunghezza dispari disgiunti, percorrendo prima uno epoi l’altro a ritroso si otterrebbe un ciclo di lunghezza dispari, il che e assurdo.
In un tale grafo, due cammini tra i medesimi estremi hanno entrambi lunghezza pari o dispari.Quello che vogliamo dimostrare e equivalente a dire che la differenza tra le lunghezze e pari;siano P = {x, v1, . . . , vn, y} e P ′ = {x,w1, . . . ,wm, y} due cammini, allora esistera il minimo itale che vi ≠ wi. Se i > 1, si possono modificare i due cammini in P = {vi−1, vi, . . . , vn, y} eP ′ = {wi−1,wi, . . . ,wm, y}, in quanto cosı abbiamo diminuita le lunghezze della stessa quantita,dunque la differenza e rimasta la stessa; se i = 1, ovviamente questa operazione lascia i camminiinvariati3.Ora, supponiamo che v1 ≠ w1; esistera un minimo j tale che wj ∈ V (P ), ovvero sia, esiste un k percui vk = wj . I due cammini {x, v1, . . . , vk} e {x,w1, . . . ,wj} sono cammini tra i medesimi estremi edisgiunti, quindi, secondo il risultato precedente, hanno entrambi un numero pari o dispari di archi;possiamo allora modificare i due cammini eliminando {x, v1, . . . , vk−1} da P e {x,w1, . . . ,wj−1} daP ′, in quanto le due parti eliminate hanno entrambe un numero pari o dispari di archi e dunquela differenza tra le lunghezze dei due nuovi cammini ha la stessa parita della differenza tra lelunghezze dei due cammini originali.Ripetendo queste due operazioni si arriva a ridurre P e P ′ a un solo punto, dunque la differenzatra le lunghezze e 0, che e pari.
A questo punto, supponiamo che G sia connesso; se non lo fosse, potremmo considerare le singolecomponenti connesse, ovvero sottografi del tipo G[U] che siano connessi ma che non siano contenutiin altri sottografi dello stesso tipo e connessi. Se queste sono bipartite, anche il grafo e bipartito.Scegliamo quindi un vertice x; ad ogni altro vertice y associamo 1 se un qualsiasi cammino da xa y ha lunghezza dispari e 2 se ha lunghezza pari. Per quanto detto sopra, tale definizione e benposta; definiamo V1 come l’insieme dei vertici a cui abbiamo associato 1 e V2 l’insieme dei verticia cui abbiamo associato 2. Due vertici a cui abbiamo associato, ad esempio, 1 non possono essereconnessi da un arco, altrimenti esisterebbe un arco da x a uno dei due che ha lunghezza dispari eun arco da x all’altro che ha lunghezza pari.Dunque G e bipartito. ◻
Dalla dimostrazione della proposizione precedente si puo ricavare anche la prossima proposizione,la cui dimostrazione e lasciata come esercizio. Chiamiamo ciclo indotto in G un sottografo del tipoG[U] che sia un ciclo, ovvero isomorfo a Ck; in altre parole, un ciclo indotto e un ciclo in cui duevertici sono adiacenti in G se e solo se lo sono nel ciclo.
Proposizione 12 Un grafo e bipartito se e solo se ogni ciclo indotto ha lunghezza pari.
4.3 Esercizi
Esercizio 1 Sia Vn l’insieme delle n−uple ordinate formate da 1 o 0. Ad esempio, per n = 3 si ha
V3 = {(0,0,0), (1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1), (1,1,1)}
Sia En l’insieme delle coppie (x, y) con x, y ∈ Vn in cui x e y differiscono per un solo elemento. Adesempio, ((1,0,0), (1,1,0)) sta in E3, ma ((1,0,0), (0,1,0)) no. Il grafo cubico n−dimensionale eQn = (Vn,En). Determinare numero di vertici e archi, valenza di ogni vertice, circonferenza, girth,diametro di G.
Esercizio 2 Dimostrare che per ogni n ≥ 4 pari esiste un grafo trivalente con n vertici.
Esercizio 3 Un grafo con 2n vertici e n2 + 1 archi contiene un sottografo isomorfo a K3, ovveroun triangolo.
Esercizio 4 Dimostrare che in un grafo con almeno due vertici ci sono sempre due vertici con lastessa valenza.
3Si ponga v0 = x e w0 = x.
24
Una foglia in un albero e un vertice di valenza 1.Esercizio 5 Se d e la massima valenza di un vertice in un albero T , allora vi sono almeno d fogliein T .
Esercizio 6 Se un albero T non ha vertici di valenza 2, allora le foglie sono piu degli altri vertici.
Esercizio 7 Se in G ogni vertice ha valenza almeno k e T e un albero con al piu k + 1 vertici,esiste un sottografo di G isomorfo a T .
Esercizio 8 Dimostrare che Qn e un grafo bipartito.
Esercizio 9 Dimostrare che ogni grafo bipartito e isomorfo a un sottografo di qualche Km,n.
Esercizio 10 Dimostrare che ogni grafo G ha un sottografo H bipartito tale che v(H) ≥ v(G)/2.
5 Connessione e cammini
Come abbiamo gia detto, un grafo e connesso se, comunque fissati due suoi vertici, esiste almenoun cammino che li congiunge. Una componente connessa di G e un sottografo connesso massimaledi G, ovvero un sottografo a cui non e possibile aggiungere nulla senza farlo diventare sconnesso;ovviamente un grafo connesso ha come unica componente connessa se stesso.
Dati due vertici x, y ∈ V (G), diciamo che un altro vertice z ∈ V (G) li separa se ogni cammino trax e y passa per z; dati due vertici x, y ∈ V (G) adiacenti, diciamo che l’arco (x, y) e un ponte se el’unico cammino tra x e y.
Un grafo G si dice k−connesso con k ∈ N se, comunque si eliminino meno di k vertici, il grafoottenuto e ancora connesso; la connettivita di G e il massimo k per cui G e k−connesso e si indicacon κ(G).Ogni grafo non vuoto e 0−connesso; ogni grafo connesso e 1−connesso. Se κ(G) = 0, G e sconnessooppure e K1, mentre in generale κ(Kn) = n − 1.
Analogamente, un grafo G si dice l−connesso per archi se, comunque si eliminino meno di l archi,il grafo rimane connesso; la connettivita per archi di G e il massimo l per cui G e l−connesso e siindica con λ(G).
Proposizione 13 Se G non e banale, si ha κ(G) ≤ λ(G).
Dim : Se λ(G) = l, allora esiste almeno un insieme F di l archi che, tolto, sconnette G. ChiamiamoG1 una componente connessa del grafo risultante dall’aver eliminato F e chiamiamo U i vertici inV (G1) che sono estremo di un arco in F .Innanzitutto notiamo che non esiste un arco in F che abbia entrambi gli estremi in G1, altrimentieliminando gli altri archi di F e non questo si otterrebbe comunque un grafo sconnesso, ma alloraλ(G) < l. Quindi ∣U ∣ ≤ ∣F ∣.Se poi c’e qualche vertice di G1 che non sta in U , allora il grafo ottenuto eliminando i vertici in Uda G e sconnesso e dunque κ(G) ≤ ∣U ∣ ≤ ∣F ∣ = λ(G).Se invece U = V (G1), scegliamo v ∈ V (G1) e consideriamo NG(v) (i vertici adiacenti a v in G);alcuni di questi vertici sono collegati a v tramite archi di F , mentre gli altri (che quindi sonoadiacenti a v anche in G1) tra loro non possono essere collegati da archi di F . Quindi dG(v) ≤ ∣F ∣.Ora, se esiste un vertice di G non adiacente a v, eliminando i vertici di N(v) si sconnette il grafoe dunque κ(G) ≤ dG(v) ≤ ∣F ∣ = λ(G).Se, comunque scelto v si ha che N(v) ∪ {v} = V (G), allora G e un grafo completo, ma alloraκ(G) = λ(G) = ∣V (G)∣ − 1. ◻La connettivita, come e stata definita piu sopra, sembra aver poco a che fare con il concetto dicammino, su cui si basa la connessione; in realta vedremo che le due nozioni sono strettamentelegate. Prima di arrivare a questo risultato, ci servono alcune definizioni.
Diciamo che un insieme di vertici S separa due vertici x, y ∈ V (G) se x, y /∈ S e il grafo ottenutoda G eliminando S non contiene cammini tra x e y; κ(x, y) e il minimo numero di vertici che devecontenere un insieme di vertici che separa x e y.Ovviamente κ(x, y) ≥ κ(G) per ogni x, y ∈ V (G); ricordiamo inoltre che due cammini tra x e y sidicono distinti se hanno in comune solo gli estremi. Denotiamo con γ(x, y) il massimo numero dicammini distinti tra x e y; ovviamente si ha la seguente disuguaglianza.
25
Proposizione 14 Per due vertici distinti e non adiacenti si ha
γ(x, y) ≤ min{dG(x), dG(y)}
Dim : Ovviamente, se si eliminano tutti i vertici adiacenti ad x, oppure ad y, non c’e modo dicongiungere x e y con un cammino; questo e possibile in quanto x e y non sono adiacenti. ◻
Inoltre, abbiamo anche una disuguaglianza tra connettivita tra due vertici e numero di camminidisgiunti.
Proposizione 15 Per due vertici distinti e non adiacenti si ha γ(x, y, ) ≤ κ(x, y).
Dim : Per disconnettere x e y dobbiamo quanto meno togliere un punto da ogni cammino traquesti, quindi almeno γ(x, y) punti, da cui la tesi. ◻
In realta, un importante risultato della teoria dei grafi e il seguente, che afferma che il minimonumero di vertici da eliminare per separare due vertici e il massimo numero di cammini disgiuntipossibili tra questi.
Proposizione 16 (Teorema di Menger) Per due vertici distinti e non adiacenti si ha γ(x, y) =κ(x, y).
Dim : Dimostreremo la tesi per induzione sul numero di vertici e su κ(x, y), ovvero, dato un grafoG e due vertici con κ(x, y) = m, supporremo che la tesi valga per ogni grafo con meno vertici diG e qualunque coppia di vertici, oppure per ogni coppia di vertici con κ(x, y) < m in un qualsiasigrafo G.Inoltre, in vista della precedente proposizione, ci basta dimostrare che γ(x, y) ≥ κ(x, y).
Passo base: In un grafo con un solo vertice, la tesi e ovvia. Inoltre, se κ(x, y) = 0 non esistonocammini tra x e y, quindi γ(x, y) = 0; se poi κ(x, y) = 1, bisogna rimuovere almeno un vertice persconnettere x e y, quindi esiste almeno un cammino tra di essi, quindi γ(x, y) ≥ 1.
Passo induttivo: Sia dunque κ(x, y) = m ≥ 2 con x, y vertici di G. Vogliamo dimostrare cheγ(x, y) ≥m. Come detto sopra, supporremo che la tesi sia vera per tutti i grafi G con meno verticio per tutte le coppie di vertici x, y con κ(x, y) < m in un qualsiasi grafo. Sia S un insieme di mvertici che separa x da y; allora ogni cammino da x a y deve contenere un elemento di S.Siano P1, . . . , Pk tutti i cammini da x a y; per ognuno di loro consideriamo i vertici tra tra x e S(ovvero il primo incontro di Pi con S) e consideriamo il sottografo generato in G da tutti questivertici, aggiungiamo poi un nuovo vertice y′ e colleghiamolo a tutti i vertici di S. Chiamiamo Gx
il nuovo grafo. Similmente, consideriamo per ogni cammino i vertici tra l’ultima intersezione conS e y, aggiungiamo il vertice x′ e colleghiamolo a tutti i vertici di S. Chiamiamo Gy il grafo cosıottenuto.Ovviamente dGx(y′) = dGy(x′) = m e S separa x da y′ in Gx e y da x′ in Gy ed e il minimoseparatore possibile, ovvero κ(x, y′) = κ(x′, y) =m. Ora abbiamo due casi.
Caso I: Esiste S di modo che sia Gx che Gy hanno meno vertici di G. Allora possiamo applicarel’ipotesi induttiva e dunque otteniamo che ci sono m cammini disgiunti tra x e y′ e altrettanti tra x′
e y. E’ ovvio che ciascuno di questi cammini passa per un punto diverso di S e dunque, eliminando ivertici x′ e y′ da ogni cammino in Gy e Gx rispettivamente e incollando opportunamente i camminisi ottengono m cammini disgiunti tra x e y in G e dunque γ(x, y) ≥m.
Caso II: Per ogni possibile separatore S, Gx o Gy (o entrambi) ha lo stesso numero di vertici diG. Allora Gx e G sono grafi isomorfi, oppure Gy e G sono isomorfi. E questo significa che y eadiacente a tutti i vertici di S oppure lo e x.Supponiamo ora di togliere ogni arco di G la cui eliminazione non alteri κ(x, y).In tale situazione, vogliamo dimostrare che il cammino minimo tra x e y ha lunghezza 2.Supponiamo che questo sia falso e consideriamo il cammino minimo x,u, v, . . . , y; se e minimo,dobbiamo supporre che u non sia connesso a y da un arco e v non lo sia ad x. Inoltre, avendoeliminato precedentemente tutti gli archi superflui, eliminando l’arco (u, v) otterremo un grafo G′
in cui κG′(x, y) =m− 1 e dunque ci sara un insieme di m− 1 punti, chiamiamolo T , che separa x ey.Osserviamo che T non puo contenere u e v, altrimenti sarebbe un separatore anche in G, ma hatroppo pochi vertici. Del resto, se togliamo i vertici di T e l’arco (u, v), disconnettiamo G, quindi
26
gli insiemi T ∪ {u} e T ∪ {v} sono separatori per x e y e hanno entrambi m elementi. Poiche siamonel caso II, T ∪ {u} e adiacente a x oppure a y, ma u e y non possono essere adiacenti, dunque xe collegato ad ogni vertice di T ∪ {u}; similmente, y e collegato ad ogni vertice di T ∪ {v}. Ora,m ≥ 2, quindi m − 1 ≥ 1, quindi c’e almeno un elemento t ∈ T , che dunque e un vertice adiacentesia ad x che ad y. Ne segue che il cammino x, t, y e il piu breve possibile ed ha lunghezza 2.Ora consideriamo il grafo H ottenuto da G levando t; H ha meno vertici, quindi l’ipotesi induttivasi applica. Allora per H vale κH(x, y) = γH(x, y); inoltre, poiche sicuramente t sta in ogni insiemeche separi x e y in G, in H si ha
γH(x, y) = κH(x, y) =m − 1 = κG(x, y) − 1
Dunque ci sono m − 1 cammini disgiunti da x a y in H e se ad essi aggiungiamo x, t, y (che none tra questi ed e disgiunto da tutti loro) otteniamo m cammini in G, dunque γG(x, y) ≥ m, comevolevamo dimostrare. ◻
Il teorema di Menger appena dimostrato fornisce informazioni sulle singole coppie di punti; peroci vuole poco per passare da questo risultato ad una caratterizzazione dei grafi con connettivita n.
Proposizione 17 (Teorema di Whitney) Un grafo G e n−connesso se e solo se per ogni duevertici distinti esistono (almeno) n cammini disgiunti che li connettono.
Dim : Se per ogni due vertici vi sono almeno n cammini, in particolare per ogni due vertici nonadiacenti si ha γ(x, y) ≥ n, quindi κ(x, y) ≥ n, quindi κ(G) ≥ n (in quanto per disconnettere duequalunque vertici non adiacenti si devono togliere almeno n vertici, dunque non si puo disconnettereG togliendone meno).D’altra parte, supponiamo che G sia n−connesso, allora sappiamo che κ(G) ≥ n, quindi κ(x, y) ≥ n,quindi γ(x, y) ≥ n se i due vertici non sono adiacenti. Nel caso di due vertici adiacenti, bastaconsiderare il grafo G′ ottenuto da G togliendo il vertice (x, y); si avra
κG′(x, y) ≥ κG(x, y) − 1 ≥ n − 1
e poiche in G′ i due vertici non sono piu adiacenti, abbiamo che per il teorema di Menger vi sarannoalmeno n − 1 cammini tra x e y e se aggiungiamo l’arco (x, y) ne avremo n in G, che e la nostratesi. ◻
5.1 Percorsi euleriani
Una delle prime avvisaglie (o forse la prima) della teoria dei grafi e il problema di ponti di Konig-sberg, affrontato da Leonhard Euler nel 1736. La citta di Konigsberg comprende 3 isole e tra quellacentrale e ognuna delle altre due vi sono due ponti, inoltre da ogni isola alla terraferma vi e unponte; il problema che si pose (e a cui rispose) Eulero fu se fosse possibile partire e tornare a casapropria girando tutte le isole e la terraferma e usando una sola volta ogni ponte, ma usandoli tutti.
A
B
C
D
Figura 21: I ponti di Konigsberg
Per questo, un percorso chiuso (ovvero in cui il primo e l’ultimo vertice coincidono) che utilizziuna ed una sola volta ogni arco di un grafo si dice percorso euleriano in G; un grafo che ammettaun percorso euleriano chiuso si dice grafo euleriano.
27
La risposta che si diede Eulero alla questione dei ponti di Konigsberg fu negativa ed anzi andooltre e produsse il seguente risultato.
Proposizione 18 (Eulero) Un grafo e euleriano se e solo se ogni vertice ha valenza pari.
Dim : Supponiamo di avere un grafo euleriano G; allora avremo un percorso che copre tutti i latidi G una e una sola volta ciascuno. Utilizziamo per un attimo il linguaggio delle isole e dei ponti(al posto di vertici e archi); se siamo su un’isola (a parte quella di partenza), avremo utilizzatoun qualche ponte per raggiungerla e dovremo quindi utilizzare un altro ponte per abbandonarla(a meno che non sia l’ultima). Quindi ogni volta che passeremo per un’isola intermedia del nostropercorso euleriano, utilizzeremo 2 ponti; rimangono escluse la prima e l’ultima isola del percorso,che, se distinte, porteranno ad utilizzare un numero dispari di ponti, ma visto che coincidono (ilpercorso e chiuso), anche questa isola dovra avere un numero pari di ponti.Riscrivendo questo in termini di vertici e archi, troviamo che ogni vertice deve stare all’estremitadi un numero pari di archi, ovvero che ogni vertice ha valenza pari.
Supponiamo invece che un grafo abbia tutti i vertici di valenza pari e cerchiamo di costruire unpercorso euleriano. Utilizziamo il seguente algoritmo: scegliamo un vertice a caso v0 e consideriamoil percorso banale W fatto dal solo v0; scegliamo v1 tale che sia adiacente a v0 e di modo che (v0, v1)non sia un ponte in G, a meno che non vi sia altra scelta. Poniamo cosı W = {v0, v1}.Sia ora W = {v0, v1, . . . , vi}; scegliamo vi+1 adiacente a vi di modo che (vi, vi+1) non sia un pontein Gi ottenuto da G togliendo gli archi gia toccati da W , a meno che non vi sia altra alternativa.Questo algoritmo ovviamente termina, se G e un grafo finito. Dimostriamo ora che il risultato eun percorso euleriano.Innanzitutto, vediamo che e un percorso chiuso: se non termina nel vertice v0, terminera in unqualche vertice w; questo vuol dire che il percorso e passato per ognuno degli archi che escono daw (altrimenti si potrebbe proseguire oltre w), ovvero 1 arco e stato usato alla fine del percorsoper arrivare a w, poi ne sono stati usati 2 ogni volta che w compariva come vertice interno delpercorso. Questo vuol dire che e stato usato un numero dispari di archi uscenti da w, ma poicheogni vertice ha valenza pari, non possono essere tutti. Quindi l’unica possibilita e che w sia v0.Chiamiamo G′ il grafo ottenuto eliminando da G gli archi di W ; per ipotesi, ogni vertice di G′ havalenza pari; supponiamo che G′ abbia qualche arco (ovvero che W non sia euleriano e quindi noncopra tutti gli archi di G). Ora, consideriamo un arco di G′ che ha come estremo un vertice w diW e che sia l’ultimo tale arco, percorrendo W da v0, v1, . . . fino di nuovo a v0. Per ipotesi, ognicammino che parta con w e con questo arco in G′ incrocera W in vertici precedenti a w, quindi,nel grafo Gw ottenuto da G eliminando gli archi di W precedenti a quel punto, l’unico camminoda w al suo successore in W e l’arco tra loro, quindi questo arco e un ponte. Questo e assurdo,perche da w parte un altro arco che non e un ponte (quello che non fa parte di W ) e quindi questoavrebbe dovuto essere scelto prima dell’altro.Dunque ogni vertice di G′ ha valenza 0, ovvero W utilizza tutti gli archi di G. ◻
L’algoritmo descritto nella dimostrazione precedente per trovare un percorso euleriano e statoelaborato da Fleury nel 1921.
5.2 Grafi 2−connessi
In questa parte esamineremo in maggior dettaglio la struttura dei grafi 2−connessi; per far questo,introduciamo il concetto di H−cammino. Se G e un grafo e H e un suo sottografo, un H−camminoin G e un cammino in cui il primo e l’ultimo vertice stanno in H, mentre ogni altro vertice sta inG ∖H.Inoltre diciamo blocco un sottografo massimale che non contenga vertici separatori (ovvero che,tolti, disconnettono il sottografo. Un blocco puo essere un sottografo massimale 2−connesso, unvertice isolato oppure un K2. Cercheremo di studiare come sono tra loro organizzati questi blocchi.
Proposizione 19 Un grafo e 2−connesso se e solo se e possibile costruirlo a partire da un ciclo eaggiungendo di volta in volta un H−cammino al grafo H ottenuto fino a quel punto.
Dim : Innanzitutto dimostriamo che ogni grafo ottenuto con questa costruzione e 2−connesso;un ciclo certamente lo e, infatti comunque togliamo 1 solo vertice rimane connesso, quindi e sicu-ramente 2−connesso. Ora, se abbiamo un grafo H che e 2−connesso e un altro grafo H ′ formato
28
da H e da un H−cammino, troviamo che H ′ e anch’esso 2−connesso: infatti, se togliamo da H ′
un vertice di H, H rimarra connesso e quindi a maggior ragione H ′; se invece togliamo un verticedall’H−cammino, i vertici di H rimarranno tra loro connessi e i vertici del cammino rimarrannoconnessi passando per H.
Figura 22: Costruzione di un grafo 2−connesso.
Ora veniamo alla parte piu complicata: dimostriamo che ogni grafo 2−connesso si ottiene in questomodo.In un grafo G 2−connesso c’e almeno un ciclo: basta considerare 3 vertici x, y, z di modo che x siaadiacente a y e y a z; ora, eliminando y il grafo rimane connesso, quindi esiste un cammino da xa z che non passa per y e raccordando questo cammino con il cammino xyz otteniamo un ciclo.Ora, prendiamo questo ciclo e consideriamo il piu grande sottografo H di G ottenibile a partireda questo ciclo con il procedimento descritto prima. Supponiamo che H non sia tutto G; sel’arco (x, y) non appartiene ad H, ma i vertici x, y appartengono ad H, allora l’arco (x, y) e unH−cammino, che quindi puo essere aggiunto ad H nel rispetto della costruzione predente e dunqueH non e massimale, ma questo e assurdo.Rimane il caso in cui ci sia un arco (x, y) di cui x sta in H e y no (infatti G e connesso, quindise c’e un arco non in H, ce n’e uno non in H ma con un estremo in H). Poiche G e 2−connesso,eliminando x, possiamo ancora trovare un cammino da H a y, ma allora raccordando questocon l’arco yx otteniamo un H−cammino da aggiungere ad H e questo e assurdo, visto che H emassimale. Quindi H = G. ◻
Ora, dato un grafo generico G, consideriamo l’insieme B dei suoi blocchi e l’insieme A dei suoivertici separatori. Notiamo che, per massimalita, due blocchi si sovrappongono solo in un verticeseparatore. Definiamo un grafo che ha come vertici A ∪B e come archi le coppie (a,B) con a ∈ A,B ∈ B tali che a ∈ B (ovvero il vertice a stia nel blocco B. Chiamiamo il grafo B cosı ottenutografo dei blocchi di G.Notiamo che due vertici di B sono adiacenti solo nel caso siano di tipo diverso, ovvero un bloccoe un vertice separatore; questo fa di B un grafo bipartito. Inoltre e chiaro che, se G e connesso,anche B lo e e viceversa.
Proposizione 20 Il grafo dei blocchi B di un grafo connesso G e un albero
Dim : Supponiamo che il grafo B non sia un albero, allora esiste un ciclo e quindi eliminandoun vertice di tale ciclo il grafo non risultera sconnesso; poiche il grafo e bipartito, il ciclo conterraalmeno un vertice a dell’insieme A. Eliminando tale vertice da B, non si sconnettera il grafo,mentre invece G verra sconnesso dall’eliminazione del corrispondente vertice separatore. Vediamobene che questo e assurdo: ogni cammino in G diventa un cammino in B e ogni cammino in Bcorrisponde a qualche cammino in G (poiche i blocchi sono connessi), dunque B e un albero. ◻
29
5.3 Esercizi
Esercizio 1 Determinare la connettivita e la connettivita per archi di K3,3, C4, L9, i grafi associatiai solidi platonici e il grafo Qn del cubo n−dimensionale per ogni n.
Esercizio 2 Determinare γ(x, y) per due qualsiasi vertici di Kn,m.
Esercizio 3 Dire quali tra i grafi Kn, Km,n, Cn, Qn e i grafi associati ai solidi platonici sonoeuleriani e per questi ultimi determinare un percorso euleriano.
Esercizio 4 Dimostrare che in un grafo n−connesso ogni n vertici stanno su un ciclo.
Esercizio 5 Dimostrare che un grafo k−connesso con almeno 2k vertici contiene un ciclo dilunghezza almeno 2k.
Esercizio 6 Sia G un grafo in cui tutti i vertici a parte due (siano x, y) hanno valenza pari;dimostrare che esiste un percorso semieuleriano, ovvero un percorso che utilizza tutti gli archi diG, ma non e chiuso (in particolare, parte da x e arriva ad y o viceversa).
Esercizio 7 Un ciclo di G e un ciclo di un blocco di G.
Esercizio 8 Determinare almeno due grafi il cui grafo dei blocchi associato sia l’albero di Figura18.
Esercizio 9 Diciamo che e ∼ e′ per e, e′ ∈ E(G) se e = e′ oppure se c’e un ciclo di G a cuiappartengono entrambi gli archi. Dimostrare che, fissato e ∈ E(G), l’insieme [e] = {e′ ∈ E(G) ∶e ∼ e′} e il blocco che contiene l’arco e.
6 Grafi hamiltoniani
Nel 1875 W.R. Hamilton produsse un buffo gioco in legno, a forma di dodecaedro, in cui da ognivertice sporgevano degli spilli e ad uno di essi era legato un filo; lo scopo del gioco e far passare ilfilo attorno ad ogni spillo una ed una volta sola, seguendo gli spigoli del solido.Insomma, questo gioco e proprio il primo problema di queste note.La trovata di Hamilton non ebbe un gran successo commerciale (anzi, non ne ebbe proprio), masollevo l’interessante questione dei cicli hamiltoniani, ovvero un ciclo che passi per ogni vertice.Un grafo in cui esiste un tale ciclo si dice, ovviamente, hamiltoniano.Il problema puo sembrare molto simile a quello dei grafi euleriani, descritto e risolto nella sezione5.1, ma purtroppo (o per fortuna) non e stata trovata una risposta altrettanto semplice, percaratterizzare quali grafi sono hamiltoniani e quali no. Non e nemmeno facile capire quale tipo dicondizioni cercare.Cominciamo con un risultato semplice, ma interessante, ottenuto da Dirac nel 1952.
Proposizione 21 (Dirac) Ogni grafo con n ≥ 3 vertici e con ogni vertice di valenza almeno n/2ha un ciclo hamiltoniano.
Dim : Innanzitutto, G e connesso, come risulta dalla Proposizione 1. Consideriamo un camminoP = {x0, . . . , xk} che sia il piu lungo possibile in G; questo vuol dire che N(x0) contiene solo verticidi P , come anche N(xk). Definiamo gli insiemi
M0 = {i ∈ N ∶ 0 ≤ i ≤ k − 1, (xi, xk) ∈ E(G)}
Mk = {i ∈ N ∶ 0 ≤ i ≤ k − 1, (xi+1, x0) ∈ E(G)}
che sono gli insiemi degli indici per cui xi e collegato a xk e xi+1 e collegato a x0, rispettivamente.Per ipotesi e per quanto detto, ∣M0∣ = ∣N(x0)∣ ≥ n/2 e ∣Mk ∣ = ∣N(xk)∣ ≥ n/2; ma poiche k ≤ n, siha che i valori possibili per i tra 0 e k − 1 sono al piu n e dunque esiste i ∈ M0 ∩Mk. Dunque(xi, xk) ∈ E(G) e (xi+1, x0) ∈ E(G).Consideriamo dunque il ciclo
C = {x0, xi+1, xi+2, . . . , xk, xi, xi−1, . . . , x0}
Vogliamo dimostrare che questo e hamiltoniano. Supponiamo che vi sia un vertice non in C, allorac’e un vertice v non in C che e adiacente ad un vertice di C, diciamo xj . Ma allora possiamo
30
x0 xi
xi+1
xk
⋯ ⋯
Figura 23: Ciclo hamiltoniano
costruire un cammino che parte da v, poi segue il ciclo C da xj in poi; cosı otteniamo un camminopiu lungo di P , ma questo e assurdo, poiche P era il piu lungo possibile. ◻
Un corollario immediato di questo risultato e che Kn e hamiltoniano per n ≥ 3, poiche n− 1 ≥ n/2.Inoltre si nota subito che la condizione imposta non e necessaria, in generale, in quanto Cn ehamiltoniano (e lui stesso un ciclo!) ma ogni suo vertice ha valenza 2, indipendentemente dal suonumero totale di vertici.In un qualche senso, pero, tale risultato e ottimale; consideriamo infatti il grafo formato da duecopie di Kn attaccate per un vertice (nella Figura 24 si ha un esempio di tale costruzione pern = 4).
Figura 24: Grafo non hamiltoniano con 7 vertici di valenza almeno 3.
Questo grafo ha 2n − 1 vertici, di cui 2n − 2 di valenza n − 1 < (2n − 1)/2 e non e hamiltoniano,infatti togliendo il vertice centrale si sconnette e dunque κ(G) = 1; se esistesse un ciclo che passaper tutti i vertici, ci sarebbero almeno due cammini tra un vertice e l’altro (le due parti in cui daessi e diviso il ciclo) e quindi κ(G) ≥ 2 per ogni grafo hamiltoniano.Da questo controesempio emerge anche la seguente proposizione, che abbiamo appena dimostrato.
Proposizione 22 Affinche G sia hamiltoniano e necessario che κ(G) ≥ 2.
Sembrerebbe dunque che anche la connettivita giochi un ruolo nello stabilire quando un grafo ehamiltoniano, ma non e sufficiente chiedere una alta connettivita: il grafo bipartito Kk,n con k < ne k−connesso, ma se k ≠ n non e hamiltoniano. Infatti, un ciclo in un grafo bipartito ha lunghezzapari, perche visita, alternatamente, i due insiemi di vertici e dunque ne comprende tanti dell’unoquanti dell’altro. Per cui in Kk,n un ciclo avra al massimo lunghezza 2k e se n ≠ k questo non eabbastanza per essere un ciclo hamiltoniano, che dovrebbe avere lunghezza n + k. Certo pero valela seguente proposizione.
Proposizione 23 Se G ha n vertici e κ(G) ≥ n/2, allora G e hamiltoniano.
Dim : Sappiamo che κ(G) ≤ d(v) per ogni v ∈ V (G), quindi n/2 ≤ κ(G) ≤ δ(G) e dunque possiamoapplicare la proposizione precedente. ◻
La connettivita e comunque legata all’hamiltonianita: infatti supponiamo che κ(G) = k, alloravuol dire che esiste un insieme S di k vertici la cui eliminazione sconnette G; se poi G e anchehamiltoniano, allora esiste un ciclo C che contiene tutti i vertici di G. Consideriamo solo C etogliamo da questo i vertici di S; avendo tolto k vertici da un ciclo, otterremo al massimo kcomponenti connesse e dunque anche da G, eliminando S, si devono ottenere al piu k componenticonnesse. Abbiamo cosı dimostrato la seguente proposizione.
Proposizione 24 Se G e hamiltoniano, allora per ogni insieme di vertici S non vuoto si deveavere che
c(G ∖ S) ≤ ∣S∣
31
dove c(G ∖ S) e il numero delle componenti connesse del grafo ottenuto da G eliminando i verticidi S.
Ovviamente, la condizione sul numero di componenti connesse e necessaria, ma non sufficiente; adesempio, basta considerare il grafo di Petersen in Figura 25. In questo grafo, comunque si tolgaun insieme di vertici S si avra c(G ∖ S) ≤ ∣S∣ (provare per credere!) ma non e hamiltoniano.
Figura 25: Grafo di Petersen
6.1 Esercizi
Esercizio 1 Trovare un grafo hamiltoniano, ma non euleriano.
Esercizio 2 Trovare un grafo euleriano, ma non hamiltoniano.
Esercizio 3 Trovare un grafo euleriano e hamiltoniano che non sia un ciclo.
Esercizio 4 Trovare un ciclo hamiltoniano in K7.
Dato un grafo G, definiamo il grafo G2 come segue: V (G) = V (G2) e due vertici x, y sono connessida un arco in G2 se e solo se lo sono anche in G oppure se esiste un cammino tra loro in G compostoda 2 archi.
Esercizio 5 Sia G =K2,5; dimostrare che G2 e hamiltoniano.
7 Il teorema dei matrimoni
Un matching4 per un grafo G e un sottografo M composto solo di archi indipendenti, ovvero senzaestremi in comune. Se V (M) = V (G), M si dice perfect matching o 1−fattore.In generale un k−fattore e un sottografo di G che sia k−regolare e contenga tutti i vertici di G. Adesempio, un 2−fattore connesso e un ciclo che contiene tutti i vertici, ovvero un ciclo hamiltoniano.
1
23
4
5 6
1
23
4
5 6
1
23
4
5 6
Figura 26: In rosso, un 1−fattore, un 2−fattore e un 3−fattore in K6
Il caso piu naturale in cui cercare di ottenere un perfect matching e quello di un grafo bipartito;ad esempio, una simile questione sta alla base del problema 2. Altro problema in qualche senso
4Dall’inglese to match, ovvero accoppiare.
32
storico e il problema dei matrimoni, in cui i vertici del grafo rappresentano uomini e donne e gliarchi sono preferenze. In astratto, si tratta, dati due insiemi, di stabilire tra essi una bigezione,con vincoli su quali elementi di un insieme possono corrispondere ad un certo elemento dell’altroinsieme.Supponiamo dunque di avere un grafo bipartito G e sia {A, B} la partizione dei vertici; se ∣A∣ = ∣B∣,possiamo cercare di trovare un perfect matching, altrimenti, supponendo che ∣A∣ < ∣B∣, potremo alpiu ottenere un matching che contenga tutti i vertici di A, che sara detto matching per A.
Supponiamo che ci sia un matching M per A nel grafo bipartito G; allora, sicuramente, ognisottoinsieme S di A ha abbastanza adiacenze in B, ovvero
∣NG(S)∣ ≥ ∣S∣
dove NG(S) e l’insieme dei vertici adiacenti a S in G (che quindi si trovano tutti in B). Il teoremadei matrimoni, dimostrato da Hall nel 1935, afferma che una simile condizione (che chiamiamocondizione del matrimonio) e anche sufficiente a garantire l’esistenza di un matching per A.
Proposizione 25 (Hall) G contiene un matching per A se e solo se ∣NG(S)∣ ≥ ∣S∣ per ogni S ⊆ A.
Dim : Abbiamo gia detto come, in presenza di un matching per A, debba valere la condizione delmatrimonio; proviamo a dimostrare il viceversa.Consideriamo la seguente famiglia di sottografi
M = {H ∶ V (H) = V (G), H rispetta la condizione del matrimonio}
ovvero dei sottografi che contengono tutti i vertici di G e ancora rispettano la condizione delmatrimonio, ovvero tali che
∣NH(S)∣ ≥ ∣S∣ ∀ A ⊆ S
Scegliamo da M un sottografo H con meno archi possibile; per la condizione di matrimonio
dH(a) = NH({a}) ≥ 1
per ogni a ∈ A; vogliamo dimostrare che dH(a) = 1. Supponiamo per assurdo che a abbia duedistinti vertici adiacenti in H, siano b1, b2; allora, poiche H ha il minimo numero possibile diarchi, cancellando uno tra (a, b1) e (a, b2) si ottiene un grafo che non rispetta la condizione delmatrimonio e dunque esiste un insieme Ai , i = 1,2 (a seconda che si tolga uno o l’altro arco)tale che ∣Ai∣ > ∣Bi∣ dove Bi e l’insieme dei vertici adiacenti ad Ai nel sottografo ottenuto da Heliminando (a, bi). Ovviamente a ∈ Ai (perche gli intorni degli altri vertici rimangono uguali).Ora, poiche b1 ∈ B2 e b2 ∈ B1, si ha che NH(A1 ∩A2) ⊆ B1 ∩B2 e NH(A1 ∪A2) = B1 ∪B2 e dunque
∣NH(A1 ∩A2 ∖ {a})∣ ≤ ∣B1 ∩B2∣ = ∣B1∣ + ∣B2∣ − ∣B1 ∪B2∣ =
= ∣B1∣ + ∣B2∣ − ∣NH(A1 ∪A2)∣ ≤ ∣A1∣ − 1 + ∣A2∣ − 1 − ∣A1 ∪A2∣ = ∣A1 ∩A2 ∖ {a}∣ − 1
ma questo viola la condizione del matrimonio e questo e assurdo.Dunque dH(a) = 1 per ogni a ∈ A; inoltre non ci possono essere due diversi archi che giungonoallo stesso vertice in B, altrimenti verrebbe ancora violata la condizione del matrimonio. Questosignifica che H e un matching per A. ◻.
Dunque, Kn,n ammette un perfect matching e Kk,n ammette un matching per l’insieme di verticipiu piccolo.
Proposizione 26 Un grafo k−regolare e bipartito ha un pefect matching.
Dim : ∣A∣ = ∣B∣, in quanto k−regolare. Inoltre, consideriamo S sottoinsieme di A, allora da essopartiranno k∣S∣ archi distinti, tutti con un estremo in NG(S), ma in NG(S) arriveranno k∣NG(S)∣archi (provenienti o meno da S), per cui k∣S∣ ≤ k∣NG(S)∣, da cui la condizione del matrimonio edunque la tesi. ◻
Questo teorema, molto versatile, non schematizza pero perfettamente il problema da cui e nato:e naturale pensare che, ad esempio, un uomo non solo abbia un insieme di donne che vorrebbesposare, ma anche che tra di esse abbia delle preferenze; per illustrare anche questa variabile,
33
supponiamo che, oltre al grafo bipartito, venga anche assegnata, per ogni vertice v, una sorta diclassifica degli archi uscenti da v. Se e, f sono archi uscenti da v, diremo che e e preferibile a frispetto a v e scriveremo che e ≥v f se e viene prima di f in questa classifica.L’insieme di tutte queste classifiche, su ogni insieme di archi uscenti da un vertice, si dice insiemedi preferenze su G.Diciamo che un matching M e stabile per un certo insieme di preferenze se per ogni arco e non inM esiste un arco f in M tale che e ed f hanno un vertice v in comune e f ≥v e. Nel 1962, Gale eShapley hanno dimostrato il seguente risultato, a volte detto teorema stabile dei matrimoni5.
Proposizione 27 (Gale, Shapley) Per ogni insieme di preferenze, G ammette un matchingstabile.
Noi non daremo la dimostrazione di questo risultato, poiche l’idea di base e semplice (costruire unpasso per volta il matching, ogni volta migliorando il piu possibile la situazione in ogni vertice),ma vi sono molti dettagli da sistemare con cura. Notiamo che il matching ottenuto puo non essereun perfect matching, anche se nel grafo questo e a priori possibile.
Vediamo ora un corollario del teorema dei matrimoni, dimostrato per la prima volta in altro mododa Petersen nel 1891.
Proposizione 28 (Petersen) Ogni grafo 2k−regolare ha un 2−fattore.
Dim : Supponiamo che G sia 2k−regolare, senza perdere di generalita, che sia connesso. Allorasappiamo che (visto che ogni vertice ha valenza 2k) G ammette un percorso euleriano v0 . . . , vl = v0;costruiamo un nuovo grafo G′ in cui per ogni vertice vi di G ci sono due vertici, v+i e v−i . Inoltre,se nel percorso euleriano l’arco (vi, vj) compare come vivj (seguendo il percorso da v0 a vl), allorain G′ aggiungiamo l’arco (v+i , v−j ), altrimenti se compare come vjvi aggiungiamo l’arco (v+j , v−i ).
vi
v−i v+i
Figura 27: Costruzione del grafo G′.
In questo modo il grafo G′ e k−regolare e bipartito e dunque ammette un perfect matching M ′;cancellando i + e i − in M ′ (ovvero collassando v+i e v−i ad un solo vertice vi per ogni i) si ottieneun 2−fattore di G. ◻
7.1 Applicazioni del teorema di Hall
Vediamo in questa sezione alcuni utilizzi del teorema dei matrimoni al di fuori della vera e propriateoria dei grafi, nel piu ampio contesto della combinatoria, ovvero la teoria dei conteggi.Dato un insieme S e una sua famiglia di sottoinsiemi {S1, S2, . . . , Sk} (non necessariamente distinti),diciamo trasversale un sottoinsieme T di k elementi che ha uno e un solo elemento in comune conogni Si. Ad esempio, se S = {1, . . . ,6}, dati S1 = S2 = {1,2}, S3 = {3,4}, 4 = {1,2,4,5}, possiamoporre T = {1,2,3,4}; se pero aggiungiamo S5 = {2,4}, non potremo piu trovare nessun trasversale.Dal teorema di Hall otteniamo il seguente risultato.
5O forse, poiche in ogni coppia almeno uno degli elementi ha ottenuto la sua prima preferenza, teorema deimatrimoni stabili
34
Proposizione 29 Dato un insieme S e una collezione di n sottoinsiemi finiti e non vuoti, questiammettono un trasversale se e solo se l’unione di qualsiasi k di questi sottoinsiemi ha almeno kelementi.
Dim : Costruiamo un grafo bipartito il cui insieme di vertici e dato da S ∪ {1, . . . , n} e gli archisono del tipo (s,m) dove s ∈ Sm; un matching per {1, . . . , n} e un modo per abbinare ad ogniintero tra 1 e n un elemento di S, di modo che l’elemento abbinato ad i stia in Si, quindi si creaun trasversale. E viceversa, dato un trasversale, abbiamo un matching.Dunque, esiste un trasversale se e solo se esiste un matching, quindi se e solo se per ogni insiemeY ⊆ {1, . . . , n} si ha ∣N(Y )∣ ≥ ∣Y ∣, ovvero se e solo se comunque scelti k sottoinsiemi (associati agliinteri in Y ) la loro unione (che e N(Y )) ha almeno k elementi. ◻
Il precedente risultato puo sembrare abbastanza inutile, visto cosı; vediamone un’applicazione. Unrettangolo latino e una tabella m × n in cui compaiono i numeri da 1 a n (supponendo m ≤ n) dimodo che i numeri su ogni riga e su ogni colonna siano tutti diversi.Se poi m = n, questa tabella si dice quadrato latino.
Proposizione 30 Se M e un rettangolo latino m × n (con m < n), allora posso estendere M adun quadrato latino aggiungendo n −m righe.
Dim : Ci bastera dimostrare che possiamo estendere M di una riga e poi ripetere il ragionamento.Chiamiamo Ai l’insieme dei numeri tra 1 e n che non compaiono nella i−esima colonna di M ;poiche i numeri su una colonna sono tutti diversi, Ai avra n −m elementi per ogni i.Ora prendiamo un insieme di colonne Ai1 , . . . ,Aik ; vogliamo verificare che la loro unione contengaalmeno k elementi. Ognuna delle k colonne contiene n −m numeri e del resto un numero non puotrovarsi in due diverse colonne e sulla stessa riga, quindi al piu un numero puo ripetersi n −mvolte, dunque ci sono almeno k numeri distinti tra le k colonne.Questo vuol dire che possiamo applicare la proposizione precedente e trovare un trasversale T allafamiglia di insiemi A1, . . . ,An; questo trasversale e la riga da aggiungere. Possiamo portare avantiquesto procedimento fintantoche m < n e dunque possiamo ottenere un quadrato. ◻
8 Teoria di Ramsey
Una 2−colorazione di un grafo e l’aver assegnato ad ognuno dei suoi archi un colore scelto tra dueassegnati o, se vogliamo essere piu prosaici, e l’aver scelto un sottoinsieme di archi (che sarannoquelli, ad esempio, rossi, mentre il complementare sara blu). Ad esempio, le seguenti sono duepossibili colorazione di K6.
Abbiamo visto nel problema 6 che, qualunque sia la colorazione di K6, possiamo sempre trovare untriangolo rosso oppure uno blu. Il problema puo essere posto in generale: dati due numeri naturalis, t, qual e il minimo n tale che Kn, comunque colorato con 2 colori, contienga sicuramente o unKs rosso o un Kt blu?Tale minimo valore di n si indica con R(s, t) e si dice numero di Ramsey ; la conclusione delproblema 6 si puo riassumere dicendo che R(3,3) = 6. Avevamo infatti non solo mostrato cheogni 2-colorazione di un K6 contiene un triangolo monocromatico, ma anche che esiste almeno una2-colorazione di un K5 per cui non vi sono triangoli monocromatici.Notiamo che R(s, t) = R(t, s) e che R(s,1) = R(1, s) = 1, R(2, s) = R(s,2) = s: ogni K1 e mono-cromatico, non avendo archi, mentre ogni Kn con n ≥ 2 contiene un K2 (ovvero un arco) rosso (oblu), oppure e monocromatico blu (o rosso); ora mostriamo che questi numeri di Ramsey esistono,ovvero che ogni R(s, t) e finito.
35
Proposizione 31 Per ogni valore intero ≥ 2 di s, t si ha
R(s, t) ≤ R(s − 1, t) +R(s, t − 1) .
Dim: Vogliamo dimostrare che, se poniamo n = R(s−1, t)+R(s, t−1) e consideriamo una qualsiasi2-colorazione di Kn, allora possiamo trovare un Ks di un colore oppure un Kt dell’altro colore.Fissiamo dunque una 2-colorazione su Kn.Sia v un vertice di Kn; definiamo
Rv = {w ∈ V (G) ∶ l’arco {v,w} e rosso}
Bv = {w ∈ V (G) ∶ l’arco {v,w} e blu} .Ora, ovviamente Rv ∪ Bv = NG(v) e dunque ∣Rv ∣ + ∣Bv ∣ = n − 1 (sono insiemi disgiunti); poichen = R(s−1, t)+R(s, t−1), si deve avere che ∣Rv ∣ ≥ R(s−1, t) o ∣Bv ∣ ≥ R(s, t−1). Supponiamo di esserenel primo caso; allora ∣Rv ∣ ≥ R(s, t−1). Consideriamo il sottografo GR di G formato considerando ivertici in Rv e, su di esso, la 2-colorazione indotta da quella di G; poiche ∣GR∣ = ∣Rv ∣ ≥ R(s−1, t), sidanno due casi: o GR contiene un Kt blu, oppure contiene un Ks−1 rosso. Nel primo caso, abbiamofinito, poiche tale Kt blu e contenuto anche in G, mentre nel secondo caso ci basta considerare ilgrafo Ks ottenuto aggiungendo a quel Ks−1 il vertice v: poiche tutti gli archi dai vertici in Rv a vsono rossi, tale grafo sara un Ks monocromatico in G.Il caso in cui invece si abbia ∣Bv ∣ ≥ R(s, t − 1) e completamente simmetrico. ◻Osserviamo che la precedente proposizione, unita al fatto che R(s,1) = R(1, s) = 1 e R(s,2) =R(2, s) = s, ci permette di concludere che
R(s, t) ≤ (s + t − 2
s − 1) .
E’ infatti immediato constatare che il binomiale soddisfa esattamente le stesse condizioni iniziali e
(s + t − 2
s − 1) = ((s − 1) + t − 2
s − 2) + (s + (t − 1) − 2
s − 1)
per la nota proprieta del triangolo di Tartaglia. Dunque, ad esempio,
R(k, k) ≤ (2k − 2
k − 1) = (2k − 2)!
(k − 1)!(k − 1)!= 1 ⋅ 3 ⋅ 5 ⋅ . . . ⋅ 2k − 3
1 ⋅ 2 ⋅ 3 ⋅ . . . ⋅ k − 1
2 ⋅ 4 ⋅ . . . ⋅ 2k − 2
1 ⋅ 2 ⋅ . . . ⋅ k − 1≤ 2k−12k−1 = 4k−1 .
Esponiamo ora un risultato che afferma che R(s, s) non puo essere troppo piccolo, in particolarenon puo essere una funzione polinomiale di s.
Proposizione 32 Se s ≥ 4, R(s, s) > 2s/2.
Dim: Dimostriamo che, colorando a caso gli archi di un Kn con n ≤ 2s/2, allora c’e una probabilitanon nulla che non vi sia ne un Ks blu, ne un Ks rosso.Ogni arco ha probabilita 1/2 di essere colorato di blu e 1/2 di essere colorato di rosso; sianoG1, . . . ,GN tutti i Ks contenuti in Kn, dove
N = (ns) .
Ora, la probabilita che Gj sia monocromatico rosso e
p = (1
2)(s2)
e dunque la probabilita che uno dei Gj sia monocromatico rosso e minore o uguale a Np (infattinon sono eventi indipendenti e dunque sommando le probabilita otteniamo una stima dall’altodella probabilita che accada almeno uno di loro).Allo stesso modo, la probabilita che uno dei Gj sia blu e minore o uguale a Np, essendo unasituazione perfettamente simmetrica. A questo punto, e ovvio che la probabilita che uno dei Gj
sia o monocromatico rosso o monocromatico blu e minore o uguale a
2Np = 2(ns)(1
2)(s2)= 2
n!
s!(n − s)!1
2s(s−1)/2≤ 2
ns
s!
1
2s(s−1)/2,
36
poiche n ≤ 2s/2, si ha che ns ≤ 2s2/2 e dunque
2Np ≤ 2s2/2
s!
1
2s(s−1)/2= 21+s/2
s!
e se s ≥ 4 si osserva facilmente che 1 + s/2 < s e dunque 21+s/2 < 2s < s!.Se ora ricordiamo la definizione “ingenua” di probabilita come
casi favorevoli
casi possibili
vediamo che i casi favorevoli, ovvero le 2-colorazioni di Kn in cui esiste un Ks monocromatico,sono meno delle totali possibili 2-colorazioni. Dunque esiste almeno una colorazione in cui non sitrova un Ks monocromatico, ovvero R(s, s) > n. ◻
Sui numeri di Ramsey si conosce ben poco, soprattutto in ambito elementare. Alcuni valori sononoti:
R(3,3) = 6, R(3,4) = 9, R(4,4) = 18, R(4,5) = 25
mentre per altri casi sono note solo limitazioni sul valore, come ad esempio
43 ≤ R(5,5) ≤ 49 .
Varianti dei numeri di Ramsey si ottengono considerando r-colorazioni e si indicano conR(s1, . . . , sr);inoltre vi sono risultati simili a quelli della teoria di Ramsey nel caso di grafi completi con un numeroinfinito di vertici.Infine, presentiamo uno dei vari risultati che si ispirano ai numeri di Ramsey, in questo caso nonsolo come tipo di problema, ma anche come tecnica di dimostrazione.
Proposizione 33 (Schur) Fissato r ≥ 2, esiste n > 3 tale che, comunque colorando di r coloriogni numero in {1, . . . , n}, esistono sempre tre interi 1 ≤ x, y, z ≤ n dello stesso colore e tali chex + y = z.
Dim: Sia n = R(3, . . . ,3) (numero di Ramsey con r colori); sia c ∶ {1, . . . , n} → {1, . . . , r} lafunzione che associa ad ogni intero il suo colore e definiamo una r-colorazione di Kn come segue.Numerando i vertici di Kn, l’arco che connette i vertici i e j verra colorato col colore c(∣i − j∣).Allora, poiche n = R(3, . . . ,3), esiste almeno un triangolo monocromatico in Kn; siano a, b, c i trevertici e possiamo assumere che a < b < c. Se poniamo x = b − a, y = c − b, z = c − a, otteniamo chex + y = z e che
c(x) = c(b − a), c(y) = c(c − b) c(z) = c(c − a)
sono i colori dei lati del triangolo e quindi sono tutti uguali. ◻
8.1 Esercizi
Esercizio 1 Si cerchi un esempio di 2-colorazione di K8 che non contenga ne un K3 rosso ne unK4 blu.
Esercizio 2 Data una qualsiasi 2-colorazione di Kn, si dimostri che c’e un ciclo Hamiltoniano chee monocromatico oppure e fatto di due cammini monocromatici.
Esercizio 3 Sia T un albero con m vertici e sia N = (m − 1)(n − 1) + 1; si dimostri che per ogni2-colorazione di KN possiamo trovare una copia di T monocromatica rossa oppure una copia diKn monocromatica blu.
Esercizio 4 Dimostrare che per ogni k ∈ N esiste n ∈ N tale che, considerando l’insieme X = {A ⊂{1, . . . , n} ∶ ∣A∣ = 3} e colorando ogni suo elemento di rosso o blu, esiste sempre un sottoinsiemeB ⊆X tale che ∣B∣ = k e ogni A ∈X con A ⊂ B e dello stesso colore.
37
9 Planarita
Diciamo che un grafo e planare se “possiamo disegnarlo sul piano senza far incrociare gli archi, senon nei vertici”; tale disegno e detto rappresentazione piana. Ad esempio, consideriamo il grafoK4:
sebbene questo disegno non sia una rappresentazione piana, il grafo K4 e planare, infatti possiamorappresentarlo in una delle seguenti forme
Allo stesso modo, i grafi ciclici, gli alberi e quelli che rappresentano i solidi platonici sono planari,come si puo verificare controllando le rappresentazioni fornite nelle pagine precedenti. D’altraparte, abbiamo anche esempi di grafi che sembrano non essere proprio planari, ad esempio Kn conn ≥ 5, il grafo di Petersen, K3,3 e piu complicati grafi bipartiti.Il fatto pero che non riusciamo ad immaginarci una rappresentazione planare di questi grafi non euna dimostrazione del fatto che non ne abbiano una. Cercheremo, nel seguito, di capire un pocoquali strumenti si possano usare per determinare la planarita di un grafo.
Consideriamo il grafo planare G; una sua rappresentazione piana divide il piano in un numerofinito di parti, dette faccie, di cui una illimitata. Ad esempio, K4 divide il piano in 4 faccie, ungrafo ciclico in 2. Quanto segue e un enunciato classico, attribuito ad Eulero.
Proposizione 34 (Eulero) Se G e un grafo planare connesso e indichiamo con V il numero divertici, E il numero di archi e F il numero di faccie di una sua rappresentazione piana, si haV + F = E + 2.
Dim: Se E = 0 allora V = F = 1 e la formula e vera; se G e un albero, allora F = 1, V = n eE = n − 1, quindi ancora la formula e verificata. Ora supponiamo di averlo mostrato per tutti igrafi con meno di E archi e supponiamo che G sia un grafo con E archi che contenga almeno unciclo (ovvero che non sia un albero); sia e un arco di G che appartiene ad un ciclo e consideriamoG ∖ e. Tale grafo e planare, ha V vertici, E − 1 archi e F − 1 faccie, quindi sappiamo che per esso(che ha meno archi) deve valere V + (F − 1) = (E − 1) + 2, ovvero V + F = E + 2, che e quello chevolevamo dimostrare. ◻
Questa formula, che ha una ovvia interpretazione anche in termini di poliedri convessi (ad ognipoliedro convesso corrisponde “naturalmente” un grafo planare), permette di ricavare alcunelimitazioni che i grafi planari devono rispettare.
Proposizione 35 Se G e un grafo planare connesso con almeno 3 vertici, allora E ≤ 3V − 6.
38
Dim: Ogni arco sta sul bordo di 2 faccie e, del resto, ogni faccia ha almeno 3 archi sul propriobordo, quindi 2E ≥ 3F , da cui
2 +E = V + F ≤ V + 2
3E ⇒ E ≤ 3V − 6 ,
che e la tesi. ◻
Proposizione 36 Se G e un grafo planare connesso senza triangoli, allora E ≤ 2V − 4.
Dim: Per lo stesso ragionamento della proposizione precedente, poiche ogni faccia ha almeno 4lati, si ha F ≤ E/2. Con lo stesso conto di prima, si ottiene la tesi. ◻
Notiamo che dalla Proposizione 35 segue il fatto che K5 non puo essere planare: il grafo completosu 5 vertici ha V = 5, E = 10 e dunque, se fosse planare, si dovrebbe avere che 10 e minore di3V − 6 = 15 − 6 = 9, il che e assurdo.D’altra parte, K3,3 rispetta questa condizione, in quanto per esso V = 6 e E = 9, che e minore di3V − 6 = 18 − 6 = 12.La non planarita di K3,3 segue dalla Proposizione 36: infatti K3,3, essendo bipartito, non puocontenere cicli di lunghezza dispari e dunque in particolare triangoli, per cui si deve anche avereche E = 9 sia minore di 2V − 4 = 12 − 4 = 8, il che e assurdo.
Proposizione 37 Sia G un grafo planare connesso. Allora G contiene almeno un vertice di grado5 o meno.
Dim: Sappiamo che E ≤ 3V − 6. Supponiamo che ogni vertice abbia grado maggiore o ugualea 6, allora 2E ≥ 6V (perche in ogni vertice arrivano almeno 6 archi, ma ogni arco ha per estremiesattamente due vertici) e dunque E ≥ 3V . Ma questo e assurdo, dunque c’e almeno un vertice digrado 5. ◻
Purtroppo tutti questi risultati, seppur utili in casi particolari, non danno una completa caratte-rizzazione dei grafi planari; allo scopo di enunciare un criterio di planarita, dobbiamo introdurre ilconcetto di minore.Il grafo H si dice minore di G se puo essere ottenuto da G tramite le seguenti mosse (ripetute ecombinate tra loro un numero finito di volte):
i. eliminare un arco
ii. eliminare un vertice (e quindi tutti gli archi che vi incidono)
iii. contrarre un arco.
L’ultima operazione ha forse bisogno di qualche spiegazione. Prendiamo ad esempio il seguentegrafo
Per contrarre l’arco rosso, innanzitutto identifichiamo i suoi due estremi, ottenendo
39
ed ora cancelliamo i cappi e identifichiamo gli archi doppi; il grafo risultante e
Ad esempio, K5 e un minore del grafo di Petersen, ottenuto contraendo gli archi rossi.
Si puo dimostrare (e non e difficile, solo noioso) che, se G e planare, anche ogni minore di G eplanare. Dunque, il grafo di Petersen di sicuro non e planare, poiche K5 non lo e. Vediamo inoltreche, contraendo gli archi rossi ed eliminando gli archi blu, possiamo realizzare K3,3 come minoredel grafo di Petersen:
40
In generale, la presenza di K5 o K3,3 (o di entrambi!) e esattamente l’ostruzione alla planarita.
Proposizione 38 (Kuratowski, Wagner) Un grafo e planare se e solo se K5 e K3,3 non sonominori di G.
La dimostrazione di questo risultato, data da Kuratowski in una formulazione leggeremente diversae raffinata in questa versione da Wagner nella propria tesi di dottorato, e oltre lo scopo di questenote.
9.1 Colorabilita
Definiamo il numero cromatico di un grafo G (planare o meno) come il minimo numero di coloriche dobbiamo usare per colorare i vertici di G se vogliamo che gli estremi di un arco siano sempredi colori diversi. Indichiamo tale numero con χ(G). Ad esempio, χ(C4) = 2, infatti deve esserealmeno 2 poiche esiste almeno un arco, inoltre
e un esempio di colorazione che rispetta le condizioni. Ovviamente si ha che, se G contiene Kn
come sottografo, allora χ(G) ≥ n; d’altra parte, se G ha N vertici, allora χ(G) ≤ N , ma questalimitazione e assai grossolana.
Proposizione 39 Sia G un grafo connesso in cui ogni vertice ha valenza al massimo k, alloraχ(G) ≤ k + 1.
Dim: Procediamo per induzione sul numero di vertici; sicuramente, k + 1 colori bastano percolorare un grafo con al massimo k + 1 vertici. Supponiamo dunque che G abbia n > k + 1 vertici eche noi sappiamo colorare con k+1 colori ogni grafo con meno di n vertici in cui ogni vertice abbiavalenza al piu k.Prendiamo un vertice x di G e togliamolo. Per ipotesi induttiva sappiamo colorare quel che restacon k + 1 colori; ma x in G ha al piu valenza k e dunque ha al piu k vertici collegati con lui,dunque c’e almeno un colore che non abbiamo usato tra i vicini di x. Assegnamo tale colore ad xe abbiamo finito. ◻
In realta, si puo dimostrare che, se G non e ne un grafo ciclico con un numero dispari di vertici,ne un grafo completo, allora χ(G) ≤ k, se k e la massima valenza. Il problema di colorare un grafoe, in generale, molto complicato e vi sono esempi di numero cromatico che vanno da un estremo(2) all’altro (il numero di vertici).Per i grafi planari, pero, si puo dire qualcosa in piu.
Proposizione 40 Se G e un grafo planare, allora χ(G) ≤ 5.
Dim: Procediamo per induzione sul numero di vertici; per il grafo con un solo vertice, il risultatoe ovvio. Per la Proposizione 37, esiste almeno un vertice in G con grado minore o uguale a 5.Chiamiamolo x. Allora G′ = G ∖ {x} ha un vertice in meno e dunque, per ipotesi, puo esserecolorato con 5 colori.Se i vicini di x in G sono colorati con al piu 4 colori, abbiamo finito, poiche possiamo attribuiread x il quinto colore; altrimenti, chiamiamo ordinatamente in senso orario y1, y2, y3, y4, y5 i vicinidi x e supponiamo che siano colorati con i colori 1,2,3,4,5 rispettivamente.Consideriamo il sottografo G1,3 formato da tutti e soli i vertici di G′ colorati coi colori 1 e 3 e gliarchi che li collegano; se y1 e y3 non sono connessi da un cammino in G1,3, basta scambiare i colori1 e 3 nella componente di G1,3 che contiene y1. In questo modo, y1 e y3 saranno entrambi coloraticol colore 3 e potremo colorare x col colore 1.Se invece y1 e y3 sono collegati in G1,3, allora esiste un ciclo che del tipo xy1 . . . y3x che passa solo inG1,3, escluso il punto x; per planarita, y2 e y4 non possono essere collegati in G2,4, che e sconnesso
41
y1
y2
y3
y4
y5
x
⋯⋮
⋯⋯
⋱
Figura 28: Se esiste un cammino in G1,3 (qui in rosso e verde) tra y1 e y3, allora y2 e y4 sonosconnessi in G2,4 (in rosa e blu), per planarita
da G1,3. Infatti il ciclo ottenuto sopra delimita una regione di piano che contiene solo y2 e non y4e G2,4 non puo avere archi o vertici in comune con G1,3; dunque esistono almeno due componenticonnesse di G2,4, una contenente y2 e delimitata dal ciclo trovato sopra ed una contenente y4.Dunque possiamo scambiare i colori 2 e 4 nella componente di G2,4 che contiene y2; potremo alloraattribuire ad x il colore 2. Questo esaurisce i casi possibili e produce una colorazione di G con 5colori. ◻
Quindi, bastano 5 colori per colorare qualunque grafo planare. In realta vale un risultato piu forte.
Proposizione 41 (Appel and Haken) Per ogni grafo planare G si ha χ(G) ≤ 4.
Questo lieve miglioramento rispetto al risultato precedente e in realta assai difficile da ottenere enella dimostrazione originale fu impiegato un computer per verificare i quasi 2000 casi a cui erastato ridotto il teorema.
9.2 Esercizi
Esercizio 1 Trovare un grafo G con χ(G) = 2 che abbia un vertice di valenza 1000.
Esercizio 2 Dimostrare che ogni poliedro convesso puo essere associato ad un grafo che abbiavertici, archi e faccie nello stesso numero in cui il poliedro ha vertici, spigoli e faccie.
Esercizio 3 Sia G un grafo planare e siano {f1, . . . , fn} le sue faccie. Il grafo duale G∗ ha comevertici l’insieme {f1, . . . , fn} e {fi, fj} e un arco di G∗ se e solo se esiste un arco di G che sta nelbordo di fi e fj contemporaneamente. Dimostrare che G∗ e planare.
Esercizio 4 Dimostrare che esistono solo 5 grafi di poliedri regolari, ovvero grafi planari regolariin cui ogni faccia abbia lo stesso numero di archi sul bordo.
Esercizio 5 Trovare un grafo G che non contenga triangoli e tale che χ(G) = 4.
Esercizio 6 Dimostrare che, se χ(G) = k, allora esistono almeno k vertici di valenza almeno k − 1.
42
Indice
1 I problemi di un museo 1
2 Pensiamoci un po’ 22.1 La visita guidata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2 I 5 lavori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Scultura vs Pittura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 Controllando gli allarmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.5 Ristrutturazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.6 Vicini di casa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Un po’ di teoria 103.1 Qualche grafo speciale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Grafi isomorfi, sottografi, cicli e cammini . . . . . . . . . . . . . . . . . . . . . . . . . 133.3 I numeri di un grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.4 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Alcune proprieta elementari 184.1 Alberi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.2 Grafi bipartiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5 Connessione e cammini 255.1 Percorsi euleriani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.2 Grafi 2−connessi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6 Grafi hamiltoniani 306.1 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
7 Il teorema dei matrimoni 327.1 Applicazioni del teorema di Hall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
8 Teoria di Ramsey 358.1 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
9 Planarita 389.1 Colorabilita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419.2 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
43
