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

• #6959 P.H. senior tag bambano #6956

  Új Válasz 2013-04-16 21:53:01 #6959

  Ú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

  

  P.H.

  senior tag

  válasz bambano #6956 üzenetére

  Ponthalmaz, amelyeket összeköthetünk bármilyen módon: egyenes szakasszal összekötve megvan a legrövidebb távolságuk, de bármilyen más módon összekötve őket (akár más pontokon keresztül, akár a monitort körbekerülve egy görbével) is létezik él, azaz végtelen (élszámú) a gráf.
  Ebből - 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, ez már véges. "Az lenne a feladat, hogy adott pontokat(csomópontok, node) úgy kéne összekötni, hogy egy gyűrűt alkossanak." Ez nem bonyolult feladat, n node-ra:
  pl. 1 <-> 2 <->...<-> n-1 <-> n <-> 1
  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.

  #6958: ezért mondtam, hogy a metszés jó ötlet. Nem ok nélkül ragaszkodik hozzá

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