Cykl Hamiltona

[Guardian_McLeavy]

Mam graf dwurzędowy i po różnych tam operacjach dochodze do takiego stanu:

Mam jeden duży cykl, w którym znajdują się dwa mniejsze. Jak teraz przerwać duży cykl, aby wyłuskać mniejsze?

 

Może sprecyzuje mój problem rysunkiem:

 

Jest tu jeden duży cykl zawierający dwa cykle Hamiltona. I obok macierz. Jak sprawdzić, czy duży graf nie jest już cyklem Hamiltona i jeżeli nie, to jak go rozdzielić?

Edytowane 5 Listopada 2006 przez Guardian_McLeavy

[Haquim]

Że tak powiem ,może mógłbyć wyrazić się ciut jaśniej

Przede wszystkim Jak brzmi orginalny problem ?

Bo to co napisałeś to jakieś przekształcenia w trakcie.

[Guardian_McLeavy]

Oryginalny problem. Cóż, problem wyjścia na balu. Kobiety i mężczyźni wskazują na siebie kto chce z kim iść i należy znaleść jak najlepsze rozwiązanie. Na początku odrzucam pary znajdujące się na "brzegach" grafu co jest dosyć proste do wytłumaczenia w macierzy. A mam zrealizować 3 podpunkty, 1 odrzucanie mam, 2 to sprawdzenie czy powstały cykl jest cyklem Hamiltona, jeżeli nie, należy znaleść w nim mniejsze cykle Hamiltona i 3 sprawa, która jest banalna, to przerwanie znalezionych cyklów Hamiltona i wypisanie par. Nie umiem poprostu przerwać jednego dużego cyklu na mniejsze. Powiedzmy nie potrafie tego zrobić patrząc na macierz. Dla przykłądu szukanie końcóek grafu na macierzy to odnajdywanie pojedynczych punktów w macierzy (jedynek) pinowo lub poziomo i eliminowanie 2 krawędzi.

Edytowane 5 Listopada 2006 przez Guardian_McLeavy

[Guardian_McLeavy]

Doszedłem do wniosku, że troche zmienie swój algorytm i nie będize potrzeby szukanie mniejszych cykli. Wystarczy przerwać uzyskany i wkońcu uzyskamy wszystkie pary.

Pozdrawiam.