Antud on kaalutud graaf

Millise kaaluga serva lisab Primi algoritm oma konstrueeritavasse alamgraafi esimesena?

Olgu G sidus n-tipuline suunamata graaf ja H tema mingi alamgraaf.

Märgi kõik laused, millest järeldub, et H on graafi G toespuu.

Ahne strateegia on algoritmides kasutatav tehnika, mille puhul valitakse

ülesande lahendi konstrueerimisel igal sammul võimalikest variantidest

see, mis on sellel hetkel parim, arvestamata, millised võivad olla

tehtud valiku tagajärjed hilisematel sammudel.

Märgi järgnevatest kõik algoritmid, mis kasutavad ahnet strateegiat.

Kas võib juhtuda, et Primi ja Kruskali algoritm annavad samale graafile

rakendades erineva toespuu?

Olgu G sidus suunamata graaf, mille kõik servad on erineva kaaluga, ning

e graafi G suurima kaaluga serv.

Märgi kõik laused, mis on kindlasti tõesed.

Kruskali algoritmis koostatakse graafi G toespuu graafi servade

läbivaatamise ja valimise teel. Väljavalitud servad moodustavad graafi G

teatava alamgraafi H. Märgi kõik laused, mis on graafi H kohta kindlasti tõesed.

Antud on kaalutud graaf

Punasega on märgitud Kruskali algoritmi esimestel järjestikustel sammudel valitud servad. Millise kaaluga serva lisab Kruskali algoritm konstrueeritavasse alamgraafi järgmisena?

Primi algoritmi rakendamisel graafile G on igal hetkel graafist välja

valitud teatud hulk servi, mis määravad graafi G teatava alamgraafi H.

Märgi kõik laused, mis on graafi H kohta tõesed.