Új hozzászólás Aktív témák

• #6960 bambano titán P.H. #6959

  Új Válasz 2013-04-16 22:09:08 #6960

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  bambano

  titán

  LOGOUT blog

  válasz P.H. #6959 üzenetére

  ha bármilyen módon kötjük össze, akkor csak bonyolítjuk a problémát.

  "Olyan gyűrűt keresni viszont ebben a részgráfban, amely nem metszi önmagát, és csak node-ban tudja egyáltalán (nyilván), ez NP-teljes.": mint a korábbi hsz-ek mutatják, nem. NP teljessé max. az teszi, ha hozzávesszük az általad javasolt legrövidebb kitételt is. bár nem vagyok meggyőzve erről sem.

  Szerk: "mint a feladvány is mondja - célszerű azt a részgráfot kiválasztani, amiben minden gép minden géppel közvetlenül össze van kötve": semmi ilyesmit nem mond a feladat, a gyűrű definíciójába beletartozik, hogy a csomópontok fokszáma=2, a minden gép minden géppel közvetlenül össze van kötve esetén meg n-1 a gépek fokszáma.

• #6956 bambano titán P.H. #6954

  Új Válasz 2013-04-16 21:38:01 #6956

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  bambano

  titán

  LOGOUT blog

  válasz P.H. #6954 üzenetére

  csakhogy itt nincs gráf. a tsp kiinduló adata egy gráf, itt meg egy ponthalmaz.

• #6952 bambano titán P.H. #6947

  Új Válasz 2013-04-16 21:19:27 #6952

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  bambano

  titán

  LOGOUT blog

  válasz P.H. #6947 üzenetére

  a tsp-re pont nem vezette vissza, mert a tsp arról szól, hogy adott gráfot kell bejárni, ez meg arról, hogy hogyan építs ponthalmazból gráfot. a tsp-nek nem része az útépítés, szemben pl. ezzel.

• #6951 cucka addikt P.H. #6950

  Új Válasz 2013-04-16 21:18:46 #6951

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  cucka

  addikt

  válasz P.H. #6950 üzenetére

  Ha nem kell a legrövidebbnek lennie, akkor bármelyik kör jó a gráfban, amely vonalak metszése nélkül lerajzolható 2d-ben.
  A baj, hogy az összes kör megkeresése minden bizonnyal np-teljes, szóval más út kéne. (Persze, sanszos, hogy nincs más lehetőség)

  (#6949) bambano
  Gráfról van szó, ahol az élek adottak. Az említett megoldás arra jó, ha van egy csomó pontod és a cél az élek megalkotása úgy, hogy teljesítse a feltételt (lerajzolható metszés nélkül, tartalmazza az összes pontot).

• #6948 cucka addikt P.H. #6947

  Új Válasz 2013-04-16 21:12:58 #6948

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  cucka

  addikt

  válasz P.H. #6947 üzenetére

  Ha kivesszük azt a kitételt, hogy a kapott gyűrű a legrövidebb legyen, akkor is np-teljes marad?
  (Gyanítom, hogy igen, csak alátámasztani nem tudom )

Új hozzászólás Aktív témák