PRIMENE RAČUNARA - decembar 2003.

1. Odrediti najmanji i najveći broj čvorova koje može da ima AVL stablo visine h.

2. Dat je aciklički usmereni graf G = (V, E). Konstruisati algoritam linearne složenosti koji utvrdjuje da li graf G sadrži neki Hamiltonov put. Prost put je Hamiltonov ako sadrži sve čvorove grafa.

3. Dato je n pravougaonika u ravni sa stranicama paralelnim osama. Konstruisati algoritam složenosti O(n log n) koji nalazi sve pravougaonike sadržane u nekom drugom pravougaoniku.

4. Nezavisan skup u grafu G = (V, E) je podskup čvorova grafa u kome izmedju ma koja dva njegova elementa ne postoji grana. Neka je dat neusmereni povezan graf G = (V, E) i prirodan broj k. Potrebno je ustanoviti da li G sadrži kliku veličine k i nezavisni skup veličine k. Dokazati da je ovaj problem NP -kompletan.