„A számítástudomány alapjai - Segédanyagok a vizsgához” változatai közötti eltérés
| 265. sor: | 265. sor: | ||
===Algoritmusok, eljárások és egyebek=== | ===Algoritmusok, eljárások és egyebek=== | ||
* Mycielski-konstrukció: egy n pontú gráfhoz egy olyan gráfot rendel, amelyben feszített részgráfként szerepel az eredeti gráf és még <math>n+1</math> pont, a következők szerint: | * Mycielski-konstrukció: egy n pontú gráfhoz egy olyan gráfot rendel, amelyben feszített részgráfként szerepel az eredeti gráf és még <math>n+1</math> pont, a következők szerint: | ||
*# Rajzoljuk le az eredeti gráf <math>v_1,...,v_n</math> pontjait a köztük lévő élekkel együtt. | |||
*# Rajzuljunk további n darab, <math>u_1,...,u_n</math> pontot, úgy, hogy az <math>u_i</math> pontnak ugyanazok legyenek a szomszédai, mint amik a <math>v_i</math>-nek is szomszédai <math>\forall i</math>-re. | |||
*# Rajzoljunk továbbá egy w pontot, amelyiket kössünk össze minden <math>u_i</math> ponttal, de ne kössünk össze egy <math>v_i</math>-vel sem. | |||
*# Állítás: ha <math>n\leq 2</math>, olyan gráfot rajzoltunk, ami megfelel a Mycielski-tételnek. | |||
==10. Síkbarajzolhatóság, Euler-féle poliédertétel, Kuratowski tétele (csak könnyű irányban bizonyítani), Fáry-Wagner-tétel (bizonyítás nélkül)== | ==10. Síkbarajzolhatóság, Euler-féle poliédertétel, Kuratowski tétele (csak könnyű irányban bizonyítani), Fáry-Wagner-tétel (bizonyítás nélkül)== | ||