Graf

Un **graf** G=(V,E) a l'é na strutura algébrica ch'a consist ëd n'ansem nen veuid V e d'un sot-ansem E \subseteq [V]^2, anté che [V]^2 a l'é la famija dij sot-ansem ëd V ëd doi element.

J'element ëd V a son ciamà ij *vértes* ëd G; j'element d'E a son soe *bande*.

Ël concet ëd graf a l'ha un përfond d'aplicassion.
A l'é dovrà, për esempi, ant la modelisassion dj'anterassion sossiaj e biològiche, l'organisassion dj'orari, le rej ëd comunicassion, l'anàlisi dij cost, ij sistema ëd difèisa compless.

### Chèiche definission
Si e= \{ u,v \}\in E, ij vértes u,v a son dit *adiacent* (l'un l'àutr) e *ancident* a e (e e a l'é dita *ancidenta* an v).
Doe bande a son *adiacente* s'a l'han giusta un vértes comun.

Dàit v \in V, ël nùmer d_G(v) dle bande ëd G ancidente an v a l'é ciamà ël *gré* ëd v.
Si d_G(v)=1, v a l'é dit *vértes terminal*.
Si r a l'é 'n nùmer natural e d_G(v)=r për minca v \in V, antlora ël graf a l'é dit r-regolar.

Un *sot-graf* ëd G=(V,E) a l'é un graf H=(W,F) con W \subseteq V,F \subseteq E.
Si W=V as dis che H a *génera* G.

Na *caminà* ëd longheur k ant ël graf a l'é na sequensa ëd vértes (u_0, \ldots ,u_k) anté che  \{ u_i,u_{i+1} \}\in E për minca valor dl'ìndes i.

### Esempi
*Un *senté* P_n a consist d'n \geq 2 vértes p_1, \ldots ,p_n e d'n-1 bande  \{ p_i,p_{i+1} \} . Donca, un senté a l'é na caminà anté che tuti ij vértes a son diferent antra 'd lor; ël nùmer n a l'é la longheur dël senté.
*Na *stèila* S_n a consist d'n \geq 2 vértes e d'n-1 bande, con un vértes ëd gré n-1 e tuti j'àutri vértes ëd gré 1.
*Un *sicl* C_n a consist d'n \geq 3 vértes  c_1, \ldots ,c_n e d'n bande  \{ c_1,c_2 \} , \ldots , \{ c_{n-1},c_n \} , \{ c_n,c_1 \} . Ël nùmer n a l'é la longheur dël sicl. Donca un sicl a l'é na caminà anté che mach ël prim e ël darié vértes a coincido.
*Ël *graf complet* ansima a n'ansem V ëd vértes a l'é ël graf anté che tuti ij vértes antra 'd lor diferent a son adiacent.
*Dàit G=(V,E), ël *graf complementar* ëd G a l'é ël graf H=(V,[V]^2-E); visadì H a l'é otnù dai midem vértes ëd G, ma an butand na banda anté ch'a-i era nen e an gavandla anté ch'a-i era.
*Ël graf ëd Petersen.
*Ël graf dl'aperitiv.

### Chèich arzultà elementar
Ël prim teorema sì-dapress a l'é ëdcò dit ël *prim teorema dla teorìa dij graf*.

**Teorema.** Ch'as consìdera un graf finì G=(V,E), anté che V= \{ v_1, \ldots ,v_n \}  e E a l'ha m element.
Antlora
: \sum_{i=1}^nd_G(v_i)=2m.

*Dimostrassion.*
An fasend l'adission dij gré dij vértes, minca banda a l'é contà doe vire.

**Teorema.** Ant un graf finì a-i son almanch doi vértes ch'a l'ha ël midem gré.

*Dimostrassion.* Ciamoma k ël nùmer dij vértes dël graf.
S'a-i é dij vértes ëd gré 0 a-i peul nen essie ëd vértes ëd gré n-1 e ij gré possìbij a son 0,1,...,n-2.
Si, nompà, gnun vértes a l'ha gré 0, ij gré possìbij a son 1,2,...,n-1.
An tuti doi ij cas, a-i son pì 'd vértes che gré possìbij, donca almanch doi vértes a devo avèj ël midem gré.

### Isomorfism
Ij graf G_1=(V_1,E_1),G_2=(V_2,E_2) as diso *isomorf* s'a-i é na bijession f:V_1 \to V_2 tal che  \{ u,v \}\in E_1 \Leftrightarrow\{ f(u),f(v) \}\in E_2.
Na fonsion f parèj a l'é ciamà isomorfism antra G_1 e G_2.
N'isomorfism antra 'n graf e chiel-midem a l'é dit *automorfism*.

Donca doi graf a son isomorf cand, gavà për la natura dij sò vértes, a son an efet l'istess graf.

### Graf tacà
Ch'as consìdera un graf G=(V,E) e ch'as pijo doi vértes diferent u,v \in V.
Un *senté* ch'a gionz u a v a l'é minca sequensa (v_0, \ldots ,v_r) ëd vértes tuti diferent tal che v_0=u,v_r=v e  \{ v_i,v_{i+1} \}\in E per tuti j'i.

La relassion  \equiv , definìa an butand u \equiv v si e mach si u=v opura u e v a son gionzù da chèich senté, a l'é na relassion d'equivalensa ansima a G.
Le class d'equivalensa as ciamo *componente* (o *componente tacà*) ëd G.
Ël graf as dis *tacà* s'a-i é mach na componenta, visadì si minca cobia d'element diferent a l'é gionzùa da chèich senté; dësnò ël graf a l'é *dëstacà*.

Ant un graf tacà G as peul definisse na distansa antra minca cobia ëd vértes u,v, an butandla 0 si u=v, dësnò ugual a la longheur dël senté pì curt ch'a gionz u e v.
An sa manera, G a ven në spassi métrich.

### Matris d'adiacensa
Ch'as consìdera un graf finì G=(V,E) e n'enumerassion dij sò vértes V= \{ v_1, \ldots , v_n \} .
La *matris d'adiacensa* corëspondenta a l'é la matris quadrà A(G)=(a_{ij}) d'órdin n definìa an butand a_{ij}=1 si  \{ v_i,v_j \}\in E e a_{ij}=0 si  \{ v_i,v_j \}\notin E.
As agiss donca ëd na matris simétrica dont la diagonal prinsipal a l'é tuta 0 e ch'a dipend da l'enumerassion dij vértes.

Ël teorema sì-dapress a fa vëdde che doi graf finì a son isomorf si e mach si soe matris d'adiacensa a son përmutassion-sìmij.

**Teorema.** Ij graf finì G_1=(V_1,E_1),G_2=(V_2,E_2) a son isomorf si e mach si, fissà n'enumerassion dij sò vértes, a-i é na matris ëd permutassion P tal che A(G_1)=P^{-1}A(G_2)P.

*Dimostrassion.* Si G_1,G_2 a l'han nen ël midem nùmer ëd vértes, a peulo nì esse isomorf, nì avèj matris d'adiacensa sìmile.
As peul donca ipotisé che V_1=V_2= \{ 1, \ldots ,n \} .
Ch'as denòto A(G_1)=(a_{ij}),B(G_2)=(b_{ij}).

Butoma che G_1,G_2 a sio isomorf e pijoma n'isomorfism f: \{ 1, \ldots ,n \}\to\{ 1, \ldots ,n \} .
A-i na ven che  \{ i,j \}\in E_1\Leftrightarrow\{ f(i),f(j) \}\in E_2, visadì a_{ij}=b_{f(i)f(j)}.
Definioma P=( \delta_{if(j)} ).
Antlora l'element ëd pòst (i,j) an P^{-1}A(G_2)P a l'é
: \sum_{s,t=1}^n(P^{-1})_{is}(A(G_2))_{st}P_{tj}= \sum_{s,t=1}^n \delta_{sf(i)}b_{st} \delta_{tf(j)}=b_{f(i)f(j)}=a_{ij},
visadì P^{-1}A(G_2)P=A(G_1).
A l'anvers, si P a l'é na matris ëd përmutassion tal che A(G_1)=P^{-1}A(G_2)P, ch'as definissa na bijession f: \{ 1, \ldots ,n \}\to\{ 1, \ldots ,n \} an butand f(j) ugual al pòst ëd la riga dl'ùnich 1 ch'a-i compariss ant la colòna j.
Donca
: \{ i,j \}\in E_1 \Leftrightarrow a_{ij}=1 \Leftrightarrow 1=(P^{-1}A(G_2)P)_{ij}=b_{f(i)f(j)} \Leftrightarrow
: \Leftrightarrow\{ f(i),f(j)\}\in E(G_2),
ch'a veul dì che f a l'é n'isomorfism antra G_1 e G_2.

An particolar, si G_1,G_2 a son isomorf, soe matris d'adiacensa a son sìmile e donca a l'han ël midem polinòmi caraterìstich, visadì
:det(A(G_1)-xI)=det(A(G_2)-xI),
anté che I a l'é la matris dl'identità.

### Colorassion
Na *colorassion* d'un graf G=(V,E) a l'é na fonsion f da V an n'ansem C, dit ansem dij *color*.
Si C a l'ha r element, antlora f as ciama n'r-colorassion.
La colorassion f a l'é *pròpia* si vértes adiacent a l'han color diferent, visadì si  \{ u,v \}\in E \Rightarrow f(u) \neq f(v).

Ël *nùmer cromàtich* χ(G) ëd G a l'é la mìnima cardinalità ëd n'ansem ëd color C tal ch'a-i sia na colorassion pròpia f:V \to C.
La determinassion ëd χ(G) a l'é un dij problema NP-complet clàssich.

Për conté vàire r-colorassion pròpie a-i son d'un graf a peul ven-e a taj ël teorema sì-dapress.
Ch'as denòta p(G,r) ël nùmer d'r-colorassion pròpie ëd G.

**Teorema d'ardussion cromàtica.**
A val la relassion p(G,r)=p(G_1,r)-p(G_2,r), anté che G_1 a l'é otnù da G an gavand na banda {u,v} e G_2 a l'é otnù da G_1 an identificand ij vértes u,v.

Ës teorema a përmet d'arporté ël cont ëd p(G,r) a col për graf ch'a l'han viaman men ëd bande e ëd vértes.
A-i na ven che f(r)=p(G,r) a l'é un polinòmi a coefissient antregh, dit *polinòmi cromàtich* ëd G.
Dagià che f(0)=f(1)=...=f(χ(G)-1)=0 e che f(m) \neq 0 për tut m \geq\chi (G), a-i son d'esponent antregh positiv e_0,e_1, \ldots ,e_{ \chi (G)-1} e un polinòmi q(r) taj che
:f(r)=r^{e_0}(r-1)^{e_1} \cdot\ldots\cdot (r-\chi (G)+1)^{e_{ \chi (G)-1}}
andoa q a l'ha gnun-e rèis antreghe positive.

#### Graf bipartì
Si  \chi (G)\leq 2, antlora G as dis un *graf bipartì*.
Si χ(G)=1, antlora G a l'é n'ansem indipendent; si χ(G)=2, antlora G a l'é l'union ëd doi ansem indipendent disgionzù.

**Esempi.**
*Un *graf bipartì complet* K_{nm} ansima a (n,m) element a l'é l'union ëd doi ansem indipendent disgionzù V_1,V_2, ël prim con n element, lë scond con m element, anté che tuti ij vértes ëd V_1 a son adiacent a tuti ij vértes ëd V_2.
*Na stèila S_n a l'é un graf bipartì complet ansima a (1,n-1) element.

**Teorema.** Un graf a l'é bipartì si e mach si a l'ha gnun sicl ëd longheur dëscobia.

*Dimostrassion.* Un graf ch'a conten un sicl ëd longheur dëscobia a peul nen esse bipartì, dagià ch'a-i van almanch tre color për colorelo.
A l'anvers, suponoma che G a l'abia n vértes e a conten-a gnun sicl ëd longheur dëscobia.
Si n \leq 2, antlora G a l'é bipartì.
Dësnò, a basta fé vëdde che minca component tacà ëd G a l'é bipartìa e donca as peul fé cont che G a sia tacà.
Fissà un vértes u, për minca vértes w ch'as colora w con 0 si u=w opura la distansa antra u e w a l'é cobia; dësnò ch'as colora w con 1.
A venta fé vëdde che costa a l'é na colorassion pròpia.
S'a fussa pa parèj, a vorërìa dì ch'a-i son doi vértes adiacent w_1,w_2 con ël midem color; donca soa distansa da u a dev esse l'istessa, disoma r.
Ch'as pijo donca doi senté (x_0, \ldots ,x_r),(y_0, \ldots ,y_r), ël prim da w_1 a u, lë scond da w_2 a u.
Ch'as denòta k ël prim valor tal che x_k=y_k.
Antlora  \{ x_0, \ldots ,x_k,y_{k-1}, \ldots ,y_0 \}  a sarìa un sicl ëd longheur dëscobia 2k-1, e sòn a l'é na contradission.

### Criche e ansem indipendent
Na *crica* ant un graf G a l'é un sot-ansem dij vértes ch'a son tuti, doi a doi, adiacent antra 'd lor.
N**ansem indipendent'' a l'é 'n sot-ansem dij vértes ch'a son tuti, doi a doi, nen adiacent antra 'd lor.<br>
Për un graf finì G, ël ''nùmer ëd crica'' ω(G) a l'é la cardinalità dla crica pì gròssa ëd G; ël ''nùmer d'indipendensa'' α(G) a l'é la cardinalità dël pì gròss ansem indipendent.

===Erbo===
Un graf sensa sicl as ciama ''foresta''. Na foresta tacà as ciama ''erbo''.
Da la definission, a-i ven che minca erbo a l'é 'n graf bipartì.<br>
An n'erbo, minca cobia ëd vértes distint u,v a l'é gionzùa da 'n senté ùnich: an efet, un senté a dev ess-ie, dagià che n'erbo a l'é tacà; s'a-i na fusso doi diferent, as otenrìa un sicl.

**Proposission.** An n'erbo T finì con pì che n'element a-i son almanch doi vértes terminaj.

''Dimostrassion.'' Ch'as consìdero doi vértes u,v ëd T dont la distansa a sia ugual al diàmeter; ciamoma w ël penùltim vértes ëd l'ùnich senté ch'a gionz u a v.
Donca v,w a son adiacent.
Si v a l'èissa n'àutr vértes adiacent, ciamomlo t, l'ùnich senté ch'a gionzrìa u a t a sarìa col ch'a passa për w e v.
Ma antlora la distansa antra u e t a sarìa pì gròssa dël diàmeter e sòn a l'é na contradission.<br>
Ant l'istessa manera as fa vëdde che u a l'ha mach un vértes adiacent.

**Teorema.** Ël polinòmi cromàtich ëd n'erbo T con n vértes a l'é <math>p(T,x)=x(x-1)^{n-1}</math>.

''Dimostrassion.'' Për [[andussion]] ansima a n.
Si n=1, antlora p(T,x)=x.
Si n>1, ch'as consìdera un vértes terminal u e ch'as consìdera l'ùnica banda {u,w} ancidenta an u.
Ch'as denòta T' l'erbo otnù da T an gavandje la banda {u,w} e <math>T''</math> col otnù an identificand ij vértes u,w.
An armarcand che T' a l'ha doe componente, dont un-a formà mach dal vértes u e l'àutra isomorfa a <math>T''</math>, për ël teorema d'ardussion cromàtica i otnoma
:<math>p(T,x)=p(T',x)-p(T'',x)=</math>
::<math>=xp(T'',x)-p(T'',x)=</math>
::<math>=(x-1)p(T'',x)=(x-1)x(x-1)^{n-2}</math>,
anté che al darié passage i l'oma dovrà l'ipòtesi andutiva.

==Multi-graf==
Ël concet ëd graf as peul generalisesse a col ëd **multi-graf''', an lassand che doi vértes a sio gionzù da pì che un-a banda.
Na formalisassion possìbila për un multi-graf M a l'é donca ëd n'ansem ëd vértes V_M, dotà ëd na fonsion f_M:[V_M]^2 \to \mathbb N  ch'a conta vàire bande a-i son antra minca cobia ëd vértes.
Tanme cas particolar, si la plancia d'f a l'é contnùa an {0,1} i l'oma torna un graf.

N'isomorfism antra doi multi-graf M,N a l'é antlora na bijession  \varphi : V_M \to V_N tal che f_M( \{ a,b \} )=f_N( \{ \varphi (a), \varphi (b) \} ) për minca a,b \in V_M.

Categorìa:Àlgebra