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

• #6962 P.H. senior tag bambano #6960

  Új Válasz 2013-04-16 22:46:23 #6962

  Ú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 #6960 üzenetére

  A "Szerk"-edre mondtam gyakorlatilag, hogy nem ez bonyolult (ha a bemeneti pontok fokszáma 2):
  1 <-> 2 <->...<-> n-1 <-> n <-> 1
  Ha mindegyik mindegyikkel össze van kötve (a pontok fokszám n-1), és abból kell kiválasztani a gyűrűt, az már az. Ha pedig nincsenek előre definiáltan összekötve, akkor végtelen a fokszám: bármerre indulsz el, eljuthatsz bármely más ponthoz (ezért célszerű összekötnünk mindent mindennel közvetlenül és ebből kiindulni: miért indulnál el pl. az ellenkező irányba? Az csak egyrészt hosszabb élt eredményez, és a fenti triviális megoldást).
  A 'legrövidebb' pedig vonatkozik a szélsőséges esetekre: egy egyenesre eső pontokra, szimmetrikus bináris fákra, stb.

  Nyilván ha van egy bármilyen (nem szükségesen legrövidebb) megoldásod, ott már lehet 'törni' pl. a metszésnek köszönhetően. Ez ugyanaz, mint kiindulni 2 pontból és mindig a legjobb helyre beilleszteni a következő pontot (ez sem polinomiális, mert n pontos gyűrűnél legrosszabb esetben n-1! próbát jelent - ha a próba mindig metsz a meglevő gyűrűvel az említett szélsőséges esetekben ).

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