Kruskal és Prim algoritmusa minimális feszítőfát állít elő. A két algoritmus lefutása után, ha ugyanazt az input gráfot kapják bemenetként, akkor az optimális feszítőfa is minden esetben megegyezik.

Adott egy G=(V,E) összefüggő, irányítatlan, élsúlyozott gráf, amelyről tudjuk, hogy |V| = 10 (azaz 10 csúcsa van). A gráfon a Kruskál vagy a Prim algoritmust futtatjuk. Hány élt fog beválasztani az algoritmus, amikor megáll és előállította a minimális feszítőfát?

Adott egy G=(V,E) gráf irányított, vagy irányítatlan gráf, ahol tudjuk, hogy |V| = 12 (azaz V elemszáma 12). Ezen gráfra a mélységi keresés algoritmusát futtatjuk. Mennyi az elhagyási idők maximális értéke?

A szélességi és a mélységi keresésnél az algoritmusok által előállított előd részgráf minden esetben fa lesz.

Helyesen adtuk meg az alábbi irányított gráfhoz tartozó szomszédsági listát?

Adott G = (V, E) irányított vagy irányítatlan gráf és egy kitüntetett "s" kezdő csúcs esetén a szélességi keresés kiszámítja az elérhető csúcsok távolságát (legkevesebb él) s-től.

Helyesen adtuk meg az alábbi irányított gráfhoz tartozó szomszédsági mátrixot?

Egy G=(V,E) irányított gráf szomszédsági mátrixának minden elemét összeadtunk és így 10-et kaptunk. Hány éle van a gráfnak?

Egy G=(V,E) irányítatlan gráf szomszédsági mátrixának minden elemét összeadtunk és így 14-et kaptunk. Hány éle van a gráfnak?

Ritka gráfok ábrázolására rendszerint szomszédsági listákon alapuló reprezentációt választunk, míg a szomszédsági mátrixos ábrázolás előnyösebb lehet sűrű gráfok esetén.