Ingegneria Energetica - Analisi e Geometria 1

I grafi

Divided by topic

Assegnato un insieme X, conjXj 2, verra denotato conP 2( X) l'insieme dei sottoin- siemi diXdi cardinalita 2. Denizione 1.Si dicegrafouna terna ordinataG= (V ; L; '), doveVe un insieme tale chejVj 2, i cui elementi sono dettiverticionodi,Le un insieme non vuoto, i cui elementi sono dettilatioarchi, e ':L!P 2( V): Sel 1; : : : ; l h2 Lsono lati diGtali che'(l 1) =


='(l h) = fv; wg 2P 2( V), si dice che tra i verticivewc'e unlato multiplo. Se'e ingettiva, il grafoGsi dicesemplice. NomenclaturaSiaG= (V ; L; ') un grafo. Sel2Le'(l) =fv; wg, si dice chevew sonoestremidile i due verticivewsi diconoadiacenti. Un vertice che non sia estremo di alcun lato si diceisolato. Se due lati hanno un estremo in comune, allora si dice che sonoincidenti. Inne,jVjsi diceordinediG. Osservazione 1.Viene esclusa da questa trattazione la possibilita di considerare il caso limite di gra con vertici tutti isolati, perche l'insieme dei lati e non vuoto. Inoltre viene escluso il caso che un vertice sia adiacente a se stesso, visto che l'applicazione'e a valori inP 2( V). Nota BeneNel seguito si considereranno esclusivamente gra niti, vale a dire con insieme dei vertici e insieme dei lati entrambi niti. In tal caso i gra possono essere rappresentati mediante un diagramma. Si osservi che ci sono diverse rappresentazioni di uno stesso grafo. Denizione 2.SianoG= (V ; L; ') un grafo,v2V. Si dicegradoovalenzadivil numerod(v) dei lati dei qualive estremo. Un vertice si diceparise il suo grado e pari, si dicedisparise il suo grado e dispari. Esempio 1.Si consideri il grafoG= (V ; L; '), doveV=fa; b; cg,L=fl 1; l 2; l 3; l 4; l 5g e':L!P 2( V) e cos denita: '(l 1) = '(l 2) = fa; bg;'(l 3) = '(l 4) = fb; cg;'(l 5) = fa; cg: Una rappresentazione diGe la seguente:  a b c l1 l 2l 3l 4 l5 I gradi dei vertici diGsono:d(a) = 3;d(b) = 4;d(c) = 3: Esempio 2.Si consideri il grafo sempliceG= (V ; L; '), doveV=fa; b; c; d; e; f ; gg, L=fl 1; l 2; l 3; l 4; l 5; l 6; l 7; l 8; l 9g e':L!P 2( V) e tale che '(l 1) = fa; fg; '(l 2) = fa; eg; '(l 3) = fa; bg; '(l 4) = fb; dg; '(l 5) = fb; cg; '(l 6) = fc; gg; '(l 7) = fd; gg; '(l 8) = fd; eg; '(l 9) = ff ; gg: Il grafoGsi puo rappresentare gracamente nel modo seguente: 1 2 g abd f ce l1l 2 l3l 4 l5l 6 l 7 l8 l 9     e ee ee e !!! !!! !!!       % % %% %% S S S S! ! ! ! ! ! ! ! ! I gradi dei vertici diGsono: d(a) = 3;d(b) = 3;d(c) = 2;d(d) = 3;d(e) = 2;d(f) = 2;d(g) = 3: Osservazione 2.Si osservi che un grafo sempliceG= (V ; L; ') puo essere individuato soltanto dall'insiemeVdei suoi vertici e dall'insiemeLdei suoi lati. Infatti, se'e ingettiva, si puo identicareLcon la sua immagine'(L) inP 2( V). Quindi, nel seguito, un grafo semplice verra indicato conG= (V ; L): Denizione 3.SiaG= (V ; L; ') un grafo, conV=fv 1; : : : ; v ng . Si dicematrice di adiacenza diGla matriceA= (ai j), i; j= 1; : : : ; n, quadrata di ordinen, con ai j= numero dei lati aventi v ie v jcome estremi : Osservazione 3.Si osservi la matrice di adiacenza e una matrice simmetrica. Inoltre, seGe un grafo semplice, gli elementi della matrice di adiacenza sono 0 o 1. Inne, per ognii= 1; : : : ; n, la somma degli elementi dellaima riga (o colonna) della matrice di adiacenza corrisponde al grado del verticev i. Denizione 4.SiaG= (V ; L; ') un grafo, conV=fv 1; : : : ; v ng ,L=fl 1; : : : ; l hg . Si dicematrice di incidenza diGla matriceA= (aj i), j= 1; : : : ; h; i= 1; : : : ; n, di tipo (h; n) con aj i=( 1 sev ie estremo di l j 0 sev inon e estremo di l j . Osservazione 4.Si osservi che, per ognii= 1; : : : ; n, la somma degli elementi della ima colonna della matrice di incidenza corrisponde al grado del verticev i. Esempio 3.La matrice di adiacenza del grafo dell'Esempio 1 e: 0 @0 2 1 2 0 2 1 2 01 A dove si e consideratov 1= a; v 2= b; v 3= c. Invece la matrice di incidenza e: 0 B B B B @1 1 0 1 1 0 0 1 1 0 1 1 1 0 11 C C C C A 3 Esempio 4.Le matrici di adiacenza e di incidenza del grafo dell'Esempio 2 sono rispet- tivamente: 0 B B B B B B B B @0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 01 C C C C C C C C A0 B B B B B B B B B B B B @1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 11 C C C C C C C C C C C C A Proposizione 1.(Lemma del le strette di mano) SiaG= (V ; L; ')un grafo. Risulta: (1)X v2Vd (v) = 2jLj: Dimostrazione.La somma X v2Vd (v) si dicegrado complessivo diGe rappresenta il numero di tutti i possibili \estremi di lato". Poiche ogni lato ha due estremi, si ottiene (1). Proposizione 2.Il numero dei vertici dispari di un grafo e pari. Dimostrazione.SiaG= (V ; L; ') un grafo. PoicheVe nito, senza ledere la generalita si puo porre:V=fv 1; : : : ; v ng . SianoV de V prispettivamente i sottoinsiemi di Vformati dai vertici pari e dai vertici dispari. Si ha, ovviamente,V d[ V p= V,V d\ V p= ;, per cui si puo porreV d= fv 1; : : : ; v sg ,V p= fv s+1; : : : ; v ng . Risulta: 2jLj=X v2Vd (v) =n X i=1d (v i) =s X i=1d (v i) +n X i=s+1d (v i) da cui si has X i=1d (v i) +n X i=s+1d (v i) = 2 jLj e quindi (2)s X i=1d (v i) = 2 jLj n X i=s+1d (v i) : Si osservi cheP n i=s+1d (v i) e la somma dei gradi dei vertici pari, per cui e un numero pari. Segue che il termine a destra dell'uguale in (2) e pari e dunque e pari anche quello a sinistra, che rappresenta la somma dei gradi dei vertici dispari. Ma la somma di numeri dispari e pari solo quando il numero degli addendi e pari: cio prova che il numero dei vertici dispari diGe pari. Esercizio 1.Esiste un grafo sempliceG= (V ; L), conV=fv 1; v 2; : : : ; v 15g , in modo tale che per ogni 1 = 1;2; : : : ;15,d(v i) = i? Denizione 5.Si diceregolaredi gradodun grafo sempliceG= (V ; L) tale che ogni suo vertice abbia gradod. SeGha ordinened e regolare di gradon1 si dicecompleto. Osservazione 5.SeG= (V ; L) e un grafo di ordinen, regolare di gradod, allora jLj=12 nd . In particolare seGe completo allorajLj=12 n (n1). Il grafo regolare completo di ordinensi denota conK n. I seguenti diagrammi mostrano gra regolari. In particolare i gra n.1,2,4,6 sono i gra completiK 2; K 3; K 4; K 5rispettivamente. 4 n.1 n.2 n.3 n.4 n.5 n.6               T T T T    @ @ @ @ @@ @ @ @ @ @      L L LL LLQ QQQ Q   Osservazione 6.Si osservi che sono completi tutti e soli i gra aventi i vertici adiacenti a due a due. Esercizio 2.Esiste un grafo di ordine 9, regolare di grado 5? Denizione 6.SianoG= (V ; L; ') un grafo,v 0; v h2 V. Si dicecamminodav 0a v h una successionel 1; : : : ; l hdi lati di Gdistinti, tali che per ogni i2 f1; : : : ; h1g,l irisulti incidente al i+1e '(l 1) = fv 0; v 1g ; : : : ; '(l h) = fv h1; v hg ; il numerohdei lati, si dice lunghezza del cammino. Sev 0= v hsi parla di circuitodi lunghezzahdav 0a v 0. Osservazione 7.SianoG= (V ; L; ') un grafo,v2V. Esiste un unico cammino di lunghezza 0 (ovvero privo di lati) davavche si dicecammino nul lo davav. SianoG= (V ; L; ') un grafo,v; w2V. In generale ci sono piu cammini davaw, e di diversa lunghezza. Cio giustica la seguente: Denizione 7.SianoG= (V ; L; ') un grafo,v; w2V. Si dicegeodetica davawun cammino di lunghezza minima davaw. La lunghezza di una geodetica davawviene dettadistanza travew. Esempio 5.Nel grafo dell'Esempio 2, si possono considerare i seguenti cammini dae ag:c 1= l 2; l 3; l 4; l 7di lunghezza 4, c 2= l 2; l 1; l 9di lunghezza 3, c 3= l 2; l 3; l 5; l 6di lunghezza 4 ec 4= l 8; l 7che ha lunghezza 2 ed e una geodetica (in questo caso l'unica) daeag. Quindi la distanza traeege 2. Denizione 8.Un grafoG=fV ; L; 'gsi diceconnessose comunque si considerino due verticiv; w2Vesiste un cammino davaw. Osservazione 8.I gra degli esempi considerati no a questo punto sono tutti connessi. Denizione 9.SianoG= (V ; L; ') un grafo,V0 V,L0 L. Si dice che (V0 ; L0 ) e un sottografo diGse8l2L0 si ha'(l) =fv; wg, conv; w2V0 . In altre parole, perche (V0 ; L0 ) sia un sottografo, gli estremi di ogni lato diL0 devono essere inV0 . Questo permette di aermare che (V0 ; L0 ) e a sua volta un grafo. Esempio 6.Si consideri il grafoGdell'Esempio 10. La coppia (V0 ; L0 ), doveV0 = fa 1; a 2; a 3; a 6g ,L0 =fl 4; l 5; l 10; l 11g , e un sottografo diG. Invece la coppia (V0 ; L00 ), dove L00 =fl 4; l 5; l 10; l 9g non forma un sottografo, in quanto l'estremo a 5di l 9non appartiene aV0 . Si vede in gura la rappresentazione di (V0 ; L0 ) e quella di (V0 ; L00 ) (anche se non avrebbe senso, perche non forma un grafo). 5 l4 l 5   l 10 l11 (V0 ; L0 )  S S S S a1 a 2a 3 a6 l4 l 5 l9   l 10 (V0 ; L00 )non sottograf oS S S Sa 1 a 2a 3 a6 Denizione 10.SianoG=fV ; L; 'gun grafo,v2V. Si dicecomponente connessa di vl'insieme Cv= fw2V: esiste un cammmino davawg: Osservazione 9.SeG=fV ; L; 'ge un grafo connesso, allora8v2V,C v= V. Osservazione 10.SianoG=fV ; L; 'gun grafo,v2V. Se si pone L0 =fl2L: gli estremi dilsono entrambi inC vg allora si vede che la coppia (C v; L0 ) e un sottografo diG. Esempio 7.Il grafoGrappresentato nella seguente gura non e connesso:  a b c l3 l 2l 4 l1 l5l 6 l8l 6 l7 d e f gE EEEE    G Infatti non esiste un cammino tra i verticiceg, per esempio.Gpresenta due componenti connesseC a= fa; c; bg,C d= fd; e; f ; gg. I sottogra da esse individuati sono (C a; L0 ) e (C d; L "), doveL0 =fl 1; l 2; l 3; l 4g ,L" =fl 5; l 6; l 7; l 8g . Denizione 11.SiaGun grafo. Si diceEulerianoun cammino o un circuito che contenga tutti i lati diG. La teoria dei gra fu originata da Eulero grazie ad un problema pratico: il famoso problema dei ponti di Konisberg, schematizzato in gura: A B C DA A A C CCC D D La citta di Konisberg e attraversata da un ume nel quale ci sono due isole, C e D della gura, collegate alle rive A e B e tra loro da sette ponti. Eulero si pose il seguente problema: e possibile partire da un punto e ritornare allo stesso punto percorrendo tutti 6 i sette ponti una sola volta e passando per le due isole e per le due rive? La situazione geograca si puo rappresentare con il seguente diagramma:    P PP PPP PP PP      A B C D f ig:1 e pertanto il problema di Eulero si traduce nel capire se esiste un circuito Euleriano del grafo rappresentato dal precedente diagramma. La risposta venne data da Eulero stesso. Teorema 1.(Eulero 1736) Un grafo privo di vertici isolati ammette un circuito Eule- riano se e soltanto se e connesso e non ha vertici dispari. Quindi la risposta al problema dei ponti di Konisberg e negativa, poiche i vertici del grafo che lo schematizza sono tutti dispari. Usando il Teorema di Eulero si puo provare il seguente risultato. Teorema 2.Un grafo privo di vertici isolati ammette un cammino Euleriano se e soltanto se e connesso e ha 0 o 2 vertici dispari. Esempio 8.Il grafo dell'esempio 1 ammette un cammino Euleriano, in quanto ha 2 vertici dispari: per esempiol 3; l 4; l 5; l 2; l 1e un cammino Euleriano. Denizione 12.SiaG= (V ; L; ') un grafo. Si diceHamiltonianoun cammino o un circuito che passi per ogni vertice diGuna sola volta (ad esclusione al piu del primo vertice del cammino, se si tratta di circuito). Osservazione 11.Non ci sono criteri generali che permettano di stabilire se un grafo ammette un cammino Hamiltoniano. Si vede che tutti i gra completi ammettono un cammino Hamiltoniano, mentre non ammettono cammini Euleriani tutti i gra completi di ordinenpari,n4, perche hanno un numero di vertici dispari superiore a 2. Esempio 9.Il seguente grafo semplice    a bcd efT T T T a aaaa a T T T T aa aaaa non ammette un cammino Hamiltoniano, ma ammette un circuito Euleriano perche non ha vertici dispari. Quindi, ci sono esempi di gra che ammettono cammini Hamilto- niani ma non Euleriani ed esempi di gra che ammettono cammini Euleriani ma non Hamiltoniani. Denizione 13.Due graG= (V ; F; '),G0 = (V0 ; F0 ; '0 ) si dicono isomor se esiste un'applicazionef:V[L!V0 [L0 7 tale chef(V) =V0 ,f(L) =L0  8l2Ltale che'(l) =fv; wg 2P 2( V) risulti'0 (f(l)) =ff(v); f(w)g. Osservazione 12.Si verica che se due gra sono isomor allora hanno: (a) lo stesso numero di vertici e lo stesso numero di lati (b) lo stesso numero di vertici di grado ssato(c) lo stesso numero di cammini di lunghezza ssata. Nessuna di queste condizioni e suciente (da sola) per aermare che due gra siano isomor. Si osservi inne che vertici di ugual grado nei due gra non possono avere distanze diverse. Esempio 10.I graG= (V ; L; ')G0 = (V0 ; L0 ; '0 ) rappresentati nella seguente gura sono isomor. l1l 2 l 3 l4 l 5l 6 l7 l8 l 9     l 10 l11G G 0   S S S S   S S S Sa 1a 4 a 2a 3 a6a 5 m1 m 11 m10 m8 m 5 m 4 m6m 3 m 9 m2 m7 v 1 v2 v3 v5 v 4v 6Z ZZZ @ @ @ @       Come facilmente si verica, l'isomorsmo e realizzato dall'applicazionef:V[L!V0 [L0 tale che per ognii= 1; : : : ;6 risultif(a i) = v ie per ogni j= 1; : : : ;11,f(l j) = m j. Esempio 11.I graGeG0 in gura v G G0          L LLL LLL e e ee ee e T T T T T T T   hanno entrambi 6 vertici e 9 lati, pero non sono isomor perche Gha il verticevdi grado 5, mentre i vertici diG0 hanno al massimo grado 4. Denizione 14.Un grafo sempliceG= (V ; L) si dicebipartitose esistono due sottoin- siemiV 1e V 2di Vtali che 1.V 1\ V 2= ;,V 1[ V 2= V 2.8v; w2V 1, vewnon sono adiacenti 3.8v; w2V 2, vewnon sono adiacenti. Quando 1.,2.,3. sono vericate,V 1e V 2si dicono i due partitidiV. Esempio 12.Il seguente grafo 8 v3 v 2 v 1 v4 v 5   ! !! !!!!!! a a a a a a a a a c cccccccc e bipartito: i due partiti sonoV 1= fv 1; v 2; v 3g eV 2= fv 4; v 5g . Teorema 3.Un grafo e bipartito se e soltanto se non ammette circuiti di lunghezza dispari. Osservazione 13.Si possono individuare i due partitiV 1e V 2ssando un vertice v 0e considerando i due sottoinsiemi diV V1= fv2V: la distanza divdav 0e pari g V2= fw2V: la distanza diwdav 0e dispari g: Naturalmentev 02 V 1: Esempio 13.Il grafo dell'Esempio 9 non ammette circuiti di lunghezza dispari, per cui e bipartito. I due partiti sonoV 1= fa; c; e; fg,V 2= fb; dg, che possono essere individuati ssando, ad esempio, il verticev 0= ae procedendo secondo l'osservazione 13. Esempio 14.Il grafo dell'Esempio 2 non e bipartito: infatti ammette il circuitol 1; l 2; l 8; l7; l 9di lunghezza dispari. Denizione 15.SiaG= (V ; L) un grafo bipartito, con partitiV 1e V 2. Si dice bipartito completose ogni vertice diV 1e adiacente a ogni vertice di V 2. Osservazione 14.Fissatin; m2N , a meno di una diversa rappresentazione, esiste un unico grafo bipartito completo tale chejV 1j =n,jV 2j =m, che si indica conK n;m(o conK m;n). Nella seguente gura sono rappresentati i gra bipartiti completiK 1;1; K 2;1; K 2;2; K 3;2. Si osservino le due diverse rappresentazioni diK 2;2e di K 3;2." "" " b b b b @ @ @ @ @v 1v 2 v 3 v 4v 1v 4 v 3 v2w 1 w 2 w 3 w4 w 5  h h h h hX X X X X l llll h hhhh   w1 w 2 w 3 w4w 5 " " " "" " " "b bbbb bbb f ig: 2 K1;1K 1;2K 2;2K 2;2K 3;2K 3;2                 Denizione 16.Un grafoG= (V ; L; ') si diceplanarese ammette una rappresentazione nella quale i suoi lati si intersecano soltanto negli estremi. Teorema 4.Per un grafo planare aventejVjvertici,jLjlati ejFjfacce, si ha: jVj jLj+jFj= 2 (formula di Eulero): Nel computo delle facce si tiene conto anche di quella esterna. 9 Proposizione 3.Per un grafo planare aventejVjvertici,jLjlati risulta: jLj 3jVj 6 Corollario 1.K 5non e planare. Dimostrazione.PerK 5si ha jLj=12 (5
4) = 10, mentre 3jVj 6 = 156 = 9. Poiche 10>9,K 5non puo essere planare. Osservazione 15.Si dimostra che ancheK 3;3non e planare. K5    @ @ @      L L LL LLQ QQQQ b b b b bb b b b b %%% %% %" " """ e eee ee b b bbb" """ "     K3;3 Teorema 5.(Kuratowski) Un grafo nito e planare se e solo se non ammette sottogra isomor aK 5o a K 3;3. Esempio 15.Sono planari i gra degli Esempi 1, 2, 9, 10, 11; inoltre sono planari K1; K 2; K 3; K 4. In particolare K 4ammette la seguente rappresentazione planare:    K4 P P P P P A A AZ Z Z Z Z Z Z Sono planariK 1;1; K 2;1; K 2;2; K 3;2: in g.2 ci sono anche le rappresentazioni planari diK 2;2e di K 3;2. Inne e planare anche il grafo di g.1, che schematizza il problema dei ponti di Konisberg, Esercizio 3.Si verichi la formula di Eulero per tutti i gra planari menzionati. Proposizione 4.Un grafo con numero di latijLj