Aktív témák

• #160 concret_hp addikt N4r4ncs #159

  2007-10-14 13:18:54 #160

  Ö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

  

  concret_hp

  addikt

  válasz N4r4ncs #159 üzenetére

  be

  kis próbálkozással találhatsz bejárást. először próbáld bejárni a középső 4*4-es részen kívül eső részt körbekörbe (szóval csinálj több kört, amikor nem lépsz bele a c3-f6 közti négyzetbe) aztán ha megvan akkor a közepe. legalábbis valami ilyen módszer van. de párszor vagy be kell lépni középre, vagy pár mezőt ki kell hagyni a "keretben", mert ugye 4*4-es táblán nem lehet megcsinálni.

  bizonyítás féle:
  keresünk euler utat:
  minden mezőről páros helyre léphetünk, kivéve ami a sarkokkal szomszédos (a2,b1 pl) mert ezekről 3 mezőre léphetünk. na ha ezeket megtrükközzük úgy, hogy azt mondjuk, hogy minket az a2 és a b1 mező esetében a c3 mezőre nem akarunk eljutni, tehát az a2-c3, b1-c3, a7-c6, b8-c6, g8-f6, h7-f6, h2-f3, g1-f3 lépéseken kívüli összes lépésre keresünk euler kört. aminek létezik, mert a gráfunk összes pontjának páros lett a fokszáma (aminek páratlan volt azokét 1-el csökkentettük, a c3, c6, f3, f6 pedig 8 helyett 6 fokszámú lett). olyan gráfokban, melyekben minden fokszám páros, létezik euler kör.

  ha egy gráfban minden élet bejárunk, akkor szükségszerűen minden pontot is érintünk a bejárás során és ezzel meg is vagyunk

  upsz ez mondjuk egy nem jó bizonyítás , mert mindenhova csak 1* kéne lépni. így viszont sima hamilton kör probléma, ami általános esetre nem megoldott. sakktáblára meg lehet mutatni valahoyg biztos, hogy van benne H-kör.
  [itt lehet próbálkozni ]

  [ Szerkesztve ]

  vagy fullba vagy sehogy :D

Aktív témák