Graf hamiltonian

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.

[modìfica] Criteri ëd hamiltonianità

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 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 . Ciamoma x e y ij vértes an C adiacent a v. A peul nen esse che nì che , dësnò an giontandje u i trovrìo un sicl pì longh che C. Consideroma antlora H={u,v,x,y}. Si , H a l'é na stèila su quatr vértes, donca un graf bipartì complet ansima a (1,3) element. Si nopà , antlora H a l'ha la forma dlë scond graf ant la conclusion ëd l'enonsià.