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