Počet hran nesouvislého grafu

Úloha číslo: 3618

Určete minimální a maximální počet hran v grafu na \(n\) vrcholech s \(c\) komponentami.

  • Řešení

    Nejméně hran bude mít takový graf, jehož každá komponenta nebude obsahovat cyklus a bude tedy strom. Takový má \(n-c\) hran.

    Nejvíce hran bude mít graf, kde každá komponenta bude úplný graf. Maxima se dosáhne tehdy, bude-li \(c-1\) komponent jednobodových a jedna na \(n-c-1\) vrcholech.

  • Odpověď

    Graf s \(c\) komponentami msí mít alespoň \(n-c\) hran a nejvýše \(\binom{n-c+1}{2}\).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze