1. Rajzolj 1, 1, 2, 2, 3, 3 fokszámú egyszerű gráfokat. Több különböző (nem izomorf) megoldás is van!
  2. Lehetnek-e az alábbiak egy gráf csúcsainak fokszámai?
    • 3, 4, 4, 4, 5
    • 0, 2, 2, 2, 4
    • 1, 1, 2, 2, 4
    • 1, 1, 2, 4, 4
    • 1, 1, 2, 3, 4
  3. Igazoljuk, hogy bármely fa esetén az élek és pontok számának szorzata páros!
  4. Rajzold le az összes nem izomorf 3, 4 és 5 pontú fát!
  5. Igazoljuk, hogy bármely legalább öt csúcsú egyszerű gráf vagy komplementere tartalmaz kört!
  6. Egy héttagú társaságban a házigazda mindenkit ismer, a több vendég pedig pontosan 2-2 embert ismer. Szemléltessük ezt az ismeretségeket gráfként!
  7. Igaz-e, hogy ha egy gráf izomorf a komplementerével, akkor minden pontjának foka páros?
  8. Mely fák izomorfak saját komplementerükkel?
  9. Bizonyítsuk be, hogy egy n pontú fában a másodfokú pontok száma nem lehet pontosan n-3.
  10. Igaz-e a következő állítás: Ha egy 2n pontú egyszerű G gráfban minden pont foka legalább n, akkor G összefüggő.
  11. Legyen G hatpontú egyszerű gráf, melyben minden pont foka legalább négy. Bizonyítsuk be, hogy G bármely négy pontja (alkalmas sorrendben) egy kört alkot.
oktatas/matematika/feladatok/kombinatorika/grafelmelet.txt · Utolsó módosítás: 2019/06/04 13:38 szerkesztette: barnkopf
CC Attribution-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0