Graf hamiltonian

Da Wikipedia.
Drapò piemontèis.png Vos an lenga piemontèisa
Për amprende a dovré 'l sistema dle parlà locaj ch'a varda sì


Sicl hamiltonian ant un dodecàedr

Ch'as consìdera un graf finì G.

Un senté an G ch'a conten tuti ij vértes ëd G as ciama senté hamiltonian.
Un sicl an G ch'a conten tuti ij vértes ëd G as ciama sicl hamiltonian.
Ël graf a l'é dit graf hamiltonian s'a l'ha un sicl hamiltonian.

Da la definission a-i ven dlongh che un graf hamiltonian a l'é tacà, ma as peul disse ëd pì, 'me ch'a fà vëdde ël teorema sì-dapress.

Teorema. Si G a l'é un graf hamiltonian e S a l'é un sot-ansem nen veuid dij vértes ëd G, antlora G-S a l'ha un nùmer ëd componente tacà nen pì grand ëd la cardinalità d'S.

Dimostrassion. A basta osservé che sòn a l'é vera pr'ij sicl.

Un senté hamiltonian ansima a 'n graf. Ël graf a l'é an nèir, ël senté an bleu.

Criteri ëd hamiltonianità[modìfica | modifiché la sorgiss]

A-i son vàire criteri ch'a smon-o dle condission për che un graf finì a sia hamiltonian. Sì-dapress a-i é n'esempi.

Teorema. Consideroma un graf finì G=(V,E) ch'a sia 2-tacà, visadì ch'a sia tacà e che gavandje un vértes qualsëssìa a resta tacà. Suponoma che gnun sot-graf ëd G dla forma H=(W,E \cap [W]^2) a sia isomorf al graf bipartì complet ansima a (1,3) element nì al graf otnù an gionzend un quart vértes a un qualsëssìa dij tre vértes dël graf complet ansima a 3 element. Antlora G a l'é hamiltonian.

Dimostrassion. Dagià che G a l'é 2-tacà, a dev avèj almanch 3 vértes e un sicl. Ciamoma C ël sicl pì longh an G. Si C a passa nen për tuti ij vértes ëd G, a-i dev essie un vértes v an C e n'àutr vértes u fòra ëd C taj che  \{ u,v \}\in E. Ciamoma x e y ij vértes an C adiacent a v. A peul nen esse che  \{ u,x \}\in E nì che  \{ u,y \}\in E, dësnò an giontandje u i trovrìo un sicl pì longh che C. Consideroma antlora H={u,v,x,y}. Si  \{ x,y \}\notin E, H a l'é na stèila su quatr vértes, donca un graf bipartì complet ansima a (1,3) element. Si nopà  \{ x,y \}\in E, antlora H a l'ha la forma dlë scond graf ant la conclusion ëd l'enonsià.