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é.