Hirdetés

  2. Fórumok
  3. Szoftverfejlesztés
  4. Programozás topic
  5. (kiemelt téma)

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

  • bambano bambano titán
    #6960
    #6959 P.H.
    Új Válasz
    Ú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
    bambano
    bambano
    titán
    #6959 P.H.

    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