Skóre

Úloha číslo: 3668

Posloupnost \((1{,}1,2{,}2,2{,}4)\)

  • není skóre grafu;
  • je skóre grafu, ten může být i nesouvislý;
  • je skóre grafu, ten musí být souvislý.
  • Řešení

    Pokud ke čtyřcyklu přidáme dva listy, dostaneme jeden z možných grafů s uvedeným skóre.

    Alternativně lze ověřit, že jde o skóre grafu pomocí věty o skóre: \((1{,}1,2{,}2,2{,}4)\to(1{,}0,1{,}1,1)\to(0{,}1,1{,}1,1)\to(0{,}1,1{,}0)\to(0{,}0,1{,}1)\to(0{,}0,0)\)

    Kdyby graf měl být nesouvislý, pak ta komponenta, co obsahuje vrchol stupně 4, musí mít alespoň 5 vrcholů. Graf nemá izolované vrcholy, takže každá komponenta má alespoň dva vrcholy. Dohromady máme ale 6 vrcholů na nichž komponenty uvedených velikostí: alespoň 5 a alespoň 2, vystavět nelze.

  • Odpověď

    Správná odpověď je c.

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