Graf - algorytm

Question

Załóżmy że mamy:
https://drive.google.com/file/[...]pVMHEyWGFQUHM/view?usp=sharing

z 1 przejdziemy do 2 albo 3. Zalozmy, ze idziemy do 2, nastepnie 3,4,5,6 i 1 to dlatego przechodzimy przez 3 bo polaczenie 3-1 jeszcze nie bylo uzyte w przeciwienstwie 2-3. Załóżmy teraz, że startujemy z wierzchołka 4 i możemy wybrać 3 albo 5. Zakładamy, że wybieramy 3, następnie pójdziemy do 6, 5 i przerywa ponieważ droga kończy się na połączeniu 4-5. (4-3 była już użyta). Jak polecacie to zrobić? jaki algorytm będzie odpowiednio pasował do sprawdzenia ilości przeskoków dla każdego wierzchołka?  

Answer 1

Graf hamiltonowski ?

Comments

czym on się różni od Eulera?

---

Nie wczytywałem się w te grafy tak bardzo. Kiedyś musiałem coś wykonać na hamiltonowskim a ten pasuje mniej więcej do twojego poroblemu.

---

moglbys powiedziec z czego korzystales? zrodel etc?

---

jednak srednio mi pasuje ;/

---

W WIkipedii powinny być algorytmy do grafów i to czasami z przykładowym pseudokodem.

---

Cięzko mi teraz powiedzieć dokładnie bo używałem tego jakieś 1,5 roku temu przy pisaniu komiwojażera.  Raczej przetrzesywałem internet.