Ciclu hamiltonian intr-un graf special

[•pauldb]

Se da un graf conex neorientat cu N noduri, fiecare nod avand exact gradul K. Sa se determine un ciclu hamiltonian. 2<=K<=N<=300, K este par. Stie cineva cum se rezolva?

[•byndrsn]

Exista intotdeauna? Adica, este adevarat ca orice graf conex, (2k)-regular este Hamiltonian?
Cred ca raspunsul este nu (cred ca exista un graf conex 4-regular care nu e Hamiltonian: Petersen graph modificat putin). So, poate graful era Hamiltonian pe deasupra (sau K era mai special)?

[•pauldb]

Se poate preciza si ca nu exista un astfel de ciclu. Dar m-am gandit ca trebuie sa existe mereu, deoarece daca K=2, graful=ciclul, daca K>2, atunci apar muchii nefolositoare, dar ciclul ramane. Daca nu m-am gandit bine, ar fi bun un contraexemplu. (Nu prea stiu ce e un Petersen graph).

[•silviug]

Problema pare de pe SGU. Daca e aia pe care o banuiesc eu, nu-ti cerea ciclul hamiltonian ci o multime de cicluri care acopera toate nodurile -- asta e un pic diferit

Btw, ar trebui sa incepem un forum destinat problemelor de pe alte site-uri, in speta cele de acm unde nu gasesti nicio solutie. E un lucru bun sa te chinui la o problema pana iti iese dar uneori parca ai vrea niste hinturi

In ce forum credeti ca e bine sa punem sectiunile? Eu cred ca ceva gen "Informatica->SGU->NUMAR NUME PROBLEMA" ar fi ok.

Silviu

PS: Paul, daca problema e aia de pe SGU iti voi da sugestii in noul forum

Later edit: Am creat sectiunea de Probleme externe. Have fun!

[•pauldb]

Imi cer scuze, nu am inteles bine problema. 

Geniala ideea cu forumul de probleme externe.