Grafos20131-lista2.pdf.txt

Federacia Universitato de Ceará
Scienco Centro
Fako de Komputanta
Algoritmoj por Grafikaĵoj

Dua Listo de ekzercoj

 Ĉiu √ signifas nivelon de malfacileco:
√ facila, meza kaj √ √ √ √ √ malfacila. Supozi grafeo rilataj
G = (V, E), | V | = n, v ∈ V.

Konsideru ne-orientita G kaj kies aro de verticoj estas V, tranĉrando aro estas E. Ankaŭ, konsideri n = | V | kaj m = | E |.

√
1. Disvolvi algoritmo komplekseco O (n + m) por determini la distancon de ĉiu vertico al specifa vertico V r ∈ V. Indiki kion la datumstrukturo estu uzata por reprezenti la grafikaĵo por respekti la komplekseco bezonata.

√ √ √
2. Estu G esti grafeo reprezentita de najbarmatrico kiu uzas 1 malmulto por vertico por G. Entajpu la vojon algoritmo en larĝa G kiu utiligas la sekvajn trajtojn disponebla por operacio de vortoj de B bitoj ĉiu (tipe, B = 32 kaj B = 64 en praktiko): bitlarĝa logika KAJ de la du vortoj (ekzemple, & operatoro C); determino de la unua ne-nulo bito en vorto (ekzemple, builtin FFS kaj simila funkcio en C). Analizi la efekto sur la runtime de la algoritmo.

√ √
3. Determini la komplekseco de la algoritmo akiris en la antaŭa demando por la kazo en kiu G estas reprezentita de najbarmatrico.

√
4.
Disvolvi algoritmo en profundo itinero tra ĉiuj verticoj de grafeo, eĉ se ĝi estas malkonektita.

√ √
5. Alpreni ke G estas duuma arbo. Supozas ke la algoritmo por kalkuli la distancoj r el kiu vertico estas modifita per anstataŭiganta la vosto por ĉelo. Kio proprieto la ordo de trairado de la verticoj de la nova algoritmo posedas? La distancoj estas ankoraŭ kalkulita korekte?
Pruvi viajn respondojn.

√ √
6. Disvolvi algoritmo kiu ricevas kiel enigo G, r ∈ V x ∈ {1, 2,. . ., N}, kaj kalkuli la verticoj de G kiu estas je distanco r estas ne pli grandaj ol x. Determini la komplekseco de via algoritmo.

√ √ √
7. Al orientita grafeo estas grafeo kie la randoj estas direktita, kio signifas, ke, donita du klaraj verticoj u, v ∈ V uv paro diferencas de paro vu. Se G estas direktita grafeo, tiam respondu la sekvajn demandojn:

1. Kiu propraĵo devas esti kontentigitaj de G por povi trovi ordigante V_0, v_1. . ., V_ {n-1} de la verticoj de G n tia ke i <j, tiam vj vidis ∈ E, por mi, j ∈ {0,. . ., N - 1}?

2. kiel uzi la vojo en profundo akiri ordigante kun la propraĵo pli supre (konsiderante ke ĉi tiu varo ekzistas)? (Konsileto: kontrolu la ebleco de dorso randoj)