— Dark mode

Tietorakenteet ja algoritmit kevät 2023

Pienin virittävä puu

CSES - Pienin virittävä puu
Tarkastellaan seuraavaa suuntaamatonta verkkoa:
  • Verkossa on solmut $1,2,\dots,N$ ja $N=1000$.
  • Jokaisen solmuparin välillä on kaari. Solmujen $a$ ja $b$ välisen kaaren paino on $\min(a,b)$.
Kuinka painava on verkon pienin virittävä puu?

Perustele lyhyesti vastauksesi:

Viikko 13

Pienin virittävä puuSuurin virittävä puuKomponentitUudet tietSuurin joukkoSamat painotSeinät ja lattiatKaikki puut