Ú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

  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.

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