Graf hamiltonian

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.
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à.

Categorìa:Àlgebra