„A számítástudomány alapjai - Segédanyagok a vizsgához” változatai közötti eltérés
| 281. sor: | 281. sor: | ||
* Kuratowski-gráf: az ötpontú teljes gráf <math>K_5</math> és a három-három pontú teljes páros gráf <math>K_{3,3}</math>. | * Kuratowski-gráf: az ötpontú teljes gráf <math>K_5</math> és a három-három pontú teljes páros gráf <math>K_{3,3}</math>. | ||
* Topologikus izomorfia: két gráf topologikusan izomorf, ha a következő két művelet alkalmazásával izomorf gráfok hozhatók létre belőlük: | * Topologikus izomorfia: két gráf topologikusan izomorf, ha a következő két művelet alkalmazásával izomorf gráfok hozhatók létre belőlük: | ||
*# Egy él "közepére" egy pont beszúrása, vagyis egy él 2-hosszú úttal való helyettesítése. | |||
*# Egy pont "középről" való eltüntetése, vagyis egy 2-hosszú út éllel való helyettesítése. | |||
===Tételek és összefüggések=== | ===Tételek és összefüggések=== | ||
| 292. sor: | 292. sor: | ||
===Algoritmusok, eljárások és egyebek=== | ===Algoritmusok, eljárások és egyebek=== | ||
* Sztereografikus projekció - síkgráf gömbre rajzolása. | * Sztereografikus projekció - síkgráf gömbre rajzolása. | ||
*# Tegyük a gömböt a síkra. | |||
*# Ahol a gömb a síkkal érintkezik, legyen a déli pólus. | |||
*# Az északi pólust összekötjük a síkon a gráf pontjaival. | |||
*# Ahol az egyenesek metszik a gömb felszínét, azok a gömbre rajzolt gráf megfelelő pontjai. | |||
*# Az eljárás megfordítható, ha az északi póluson nincs pont és nem is megy át él. | |||
==11. Dualitás, gyenge izomorfia, Whitney tételei (bizonyítás nélkül), síkgráfok színezése, ötszíntétel== | ==11. Dualitás, gyenge izomorfia, Whitney tételei (bizonyítás nélkül), síkgráfok színezése, ötszíntétel== | ||