Diagonála třetí mocniny matice sousednosti.

Úloha číslo: 3616

Nechť \(G\) je graf bez trojúhelníků a \(A\) jeho matice sousednosti. Jaké prvky má na hlavní diagonále \(A^3\), tj. třetí mocnina \(A\)?

  • Nápověda

    Vzpomeňte si na vztah mezi počtem sledů délky \(k\) mezi dvěma vrcholy a \(k\). mocninou matice souvislosti.

  • Řešení

    Prvky v \(A^3\) odpovídají sledům délky tři mezi odpovídající dvojicí vrcholů. Na diagonále by byly počty trojúhelníků a ty jsou podle předpokladů nulové.

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