Stěny

Úloha číslo: 3670

Uvažujme jen ta nakreslení rovinných grafů, v nichž je každá stěna ohraničena cyklem a různé stěny mohou mít společnou nejvýše jednu hranu. Grafy bez hran neuvažujeme.

V každém takovém grafu \(G\) hledáme vhodný vrchol \(u\) tak, aby jeho odebráním klesl počet stěn co nejvíce. Jaký pokles můžeme vždy zaručit? Pokud platí více možností, vyberte tu nejvyšší.

  • 2
  • 4
  • 6
  • Řešení

    Nejmenší stupeň v grafu \(G\) je 3 – kdyby byl menší, není některá stěna ohraničena cyklem (stupeň 1) nebo některé stěny mají společných více hran (stupeň 2).

    Odebráním vrcholu stupně \(k\) se sloučí \(k\) stěn do jedné, tedy počet stěn klesne o \(k-1\).

    Obecně existenci vrcholu většího stupně nelze zaručit, vizte např. nakreslení \(K_4\).

  • Odpověď

    Správná odpověď je a).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na trénování výpočtu
En translation
	Zaslat komentář k úloze