Graf

Da Wikipedia.

Test an lenga piemontèisa

Graf ëd j'anliure dl'Intrada dla Wikipedia piemontèisa, arlevà dal programa http://www.aharef.info/static/htmlgraph/

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.

Graf ëd la Ragnà (30% dël total dle conession esistente)

Ël concet ëd graf a l'ha un përfond d'aplicassion. A l'é dovrà, për esempi, ant la modelisassion dj'anterassion sossiaj.

[modìfica] Chèich 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.

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.

[modìfica] 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 daré vértes a coincido.
Ël graf ëd Petersen.
Ë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.

[modìfica] 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é.

[modìfica] 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.

[modìfica] 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.

[modìfica] 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 i j)$ d'órdin n definìa an butand $a i j = 1$ si $\{ v_i,v_j \}\in E$ e $a i j = 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ìmile.

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 i j), B (G 2) = (b i j)$ .

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 i j = b f (i) f (j)$ . Definioma $P = (δ i f (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ì

d e t (A (G 1) - x I) = d e t (A (G 2) - x I)

anté che I a l'é la matris dl'identità.

[modìfica] 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.

[modìfica] 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 n m$ 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'é par; 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.

[modìfica] 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.
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.

[modìfica] 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ì.
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.
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'é $p (T, x) = x (x - 1) n - 1$ .

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 $T''$ 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 $T''$ , për ël teorema d'ardussion cromàtica i otnoma

p (T, x) = p (T', x) - p (T'', x) =

= x p (T'', x) - p (T'', x) =

= (x - 1) p (T'', x) = (x - 1) x (x - 1) n - 2

anté che al darié passage i l'oma dovrà l'ipòtesi andutiva.

[modìfica] 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$ .

OMMI! Ma io non SO LEGGERE!! E be'? :) È facile leggere una lingua che si parla già. Consulti questa pagina e vedrà, in un attimo anche Lei avrà il suo badge da bogianen :)

St'utent-sì a l'é un bogianen

OMMI! pero si YO no
SE LEER!

¿Y que? :) Es fácil aprender a leer un idioma que ya se habla. Consulte usted esta pagina y verá, en un momento tendrá usted su Badge de Bogianen :)

15.650 artìcoj scrivù e na media ëd pàgine lesùe davzin a 1.750.000 pàgine l'ann!

'cò ti it peule travajé a fé pì granda e bela la wikipedia piemontèisa. Tùit a peulo gionté dj'anformassion, deurbe dij neuv argoment, deje na man aj volontari ch'a travajo ambelessì 'ndrinta. Rintra ant la Piòla e les coma avnì a fé toa part. I soma na gran famija e i l'oma da manca dël travaj ëd tuti. Se it la sente nen dë scrive n'artìcol, a-i son vàire travajòt da fé andova a fa pa da manca d'esse na cima a scrive për podej giuté. Mersì.

BANCHÈT dj'UTISS

Për dì la soa ansima a sta pàgina-sì ch'a-i daga 'n colp col rat ant sël tilèt discussion. Për lasseje un messagi a j'aministrator ch'a varda ambelessì.