3.1. Se considera graful din figura 4. a.)Sa se precizeze ordinea nodurilor rezultata in urma traversarii prin metoda cautarii prin cuprindere, respectiv prin cautarea in adancime pornind din nodul I. Se va presupune ca nodurile sunt ordonate alfabetic (daca exista mai multe alternative, nodurile se vor selecta in ordine alfabetica). b.) Sa se reprezinte grafic arborii de cautare rezultati. c.) Sa se determine punctele de articulatie
4.1. Sa se scrie un program interactiv care realizeaza prelucrarea unui graf neorientat,cu nodurile caracterizate prin cate o cheie alfanumerica unica, prin urmatoarele comenzi:
Parametrii comenzilor se furnizeaza interactiv si se valideaza.
Graful se va implementa folosind - o matrice de adiacente - structuri de adiacente ( cazul 3 ).
Se vor compara cele doua implementari dpdv al timpilor de executie (operatorul O) si al spatiului de memorie utilizat.
5.1. Se da o lista de persoane ( prin nume ) si pentru fiecare, lista numelor prietenilor. Considerand adevarata sintagma : " L'ami de mon ami c'est mon ami ", sa se gaseasca grupul de prieteni ai unei persoane precizate.
5.2. Sa se realizeze un program care primeste ca date de intrare un graf si determina daca este posibila colorarea nodurilor sale folosind doua culori, alb si negru, astfel incat oricare doua noduri adiacente sa fie colorate diferit. Daca aceasta colorare este posibila, sa se afiseze o solutie a problemei.
Indicatii
De exemplu, graful din figura prezinta o situatie in care colorarea a fost
posibila.
Problema poate fi rezolvata printr-o serie de cautari in adancime, apeland o procedura recursiva cu parametri un nod si o culoare care se doreste sa fie asociata nodului. Daca nodul este deja colorat si are culoarea buna, procedura se intoarce la parintele sau. Daca nodul este deja colorat in cealalta culoare, se termina programul cu concluzia ca graful nu poate fi colorat conform cerintelor. Altfel, daca nodul este necolorat, se coloreaza si se apeleaza procedura recursiva pentru fiecare dintre nodurile adiacente folosind cealalta culoare.
Se pune problema de a demonstra faptul ca daca acest algoritm declara graful necolorabil, intr-adevar nu exista nici o posibilitate de a-l colora. Algoritmul declara graful necolorabil numai cand incearca sa schimbe culoarea unui nod K. Aceasta inseamna ca nodul K a mai fost vizitat anterior. Deoarece cautarea in adancime avanseaza urmand drumuri in graf, inseamna ca exista doua drumuri de la nodul de start la nodul curent. Consideram punctul X in care aceste drumuri au avut ultima divergenta si fie acesta colorat in culoarea C1. Deoarece pe parcursul unui drum se alterneaza culorile, inseamna ca un nod aflat la capatul unui drum format dintr-un numar impar de noduri e colorat in culoarea C2, iar unul aflat la capatul unui drum format dintr-un numar par de noduri este colorat in aceeasi culoare C1 ca si X. Deci cele doua drumuri de la X la K au unul numar par iar celalalt numar impar de noduri, formand impreuna un ciclu cu numar impar de noduri. Se poate usor demonstra prin inductie ca un ciclu cu un numar impar de noduri nu poate fi colorat conform regulei impuse.
5.3. Lucrarile unui congres se desfasoara pe sectiuni. Exista un numar N de sectiuni. La fiecare dintre acestea poate participa un numar nelimitat de persoane. Fiecare persoana poate alege la lucrarile cator sectiuni sa participe si care sunt acestea. Aceste date sunt trimise organizatorilor conferintei in talonul de inscriere. Dezbaterile in cadrul fiecarei sectiuni dureaza H ore. Realizati un program care sa vina in sprijinul organizatorilor conferintei, realizand o planificare a sectiunilor astfel incat congresul sa dureze un timp minim, dand totodata posibilitatea tuturor persoanelor de a lua parte la toate sectiunile la care s-au inscris. Programul va folosi ipoteza simplificatoare ca nu exista planificate nici un fel de pauze.
Indicatii
Aceasta problema poate fi modelata in termeni de grafuri in felul urmator:
Fie graful neorientat G=(N,A), unde N este multimea nodurilor, fiecare
nod corespunde unei sectiuni a conferintei. Intre doua noduri s1, s2 exista un arc
daca exista cel putin o persoana care doreste sa participe la ambele sectiuni, s1
si s2. Problema se pune in a asigna fiecarui nod un "numar de cuanta de timp" (o
cuanta reprezentand durata H a oricarei sectiuni), astfel incat doua noduri
adiacente sa aiba asignate cuante diferite si numarul total de cuante sa fie minim.
Exemplu: Se considera un congres cu 5 sectiuni, A, B, C, D, E. Graful rezultat in urma inscrierilor participantilor este prezentat in figura, impreuna cu o planificare rezultata in urma algoritmului.
Problema se poate rezolva cu ajutorul unui algoritm de tip Greedy. Se sorteaza nodurile in ordinea descrescatoare a gradului lor (gradul unui nod este numarul de arce incidente nodului; gradul maxim il are nodul corespunzator sectiunii care este implicata in cele mai multe conflicte). Algoritmul incepe cu NrCuantaTimp=1, nici un nod nu are inca asignata o cuanta de timp.
Se poate urma urmatoarea procedura iterativa:
* Gaseste nodul k de grad maxim care nu are inca o cuanta asignata, si
nu exista nici un arc intre k si un alt nod avand asignata cuanta curenta
NrCuantaTimp
* Daca un asemenea nod exista, lui ii va fi asignata cuanta cu numarul
curent si procedura se repeta
* Daca nu exista un asemenea nod, si nu s-au terminat toate nodurile,
incrementeaza numarul cuantei curente
5.4. Se considera jocul "scara de cuvinte": fiind date doua cuvinte de 5 litere, C1 si C2, sa se gaseasca "scara cuvintelor" prin care se poate transforma C1 in C2, la fiecare "treapta" fiind permisa inlocuirea unei singure litere. De exemplu, daca C1="carte" si C2="burse", o scara posibila este: carte, curte, curse, burse.
Sa se scrie un program care, fiind dat un dictionar de N=5000 de cuvinte, toate avand acelasi numar (5) de litere, poate fi interogat in mod repetat pentru a afla cea mai scurta scara de cuvinte intre perechi de cuvinte care se dau.
Indicatii
Problema se poate modela cu ajutorul grafurilor in felul urmator: La citirea dictionarului, se construieste un graf avind ca noduri cele N cuvinte. Intre doua noduri C1 si C2 exista un arc daca cele doua cuvinte difera printr-o singura litera.
Interogarea dictionarului pentru gasirea celei mai scurte "scari" de la un cuvant C1 la un cuvant C2 presupune gasirea drumului minim (daca exista) de la C1 la C2. in cazul grafurilor neponderate, aceasta problema se rezolva prin cautarea prin cuprindere. Figura prezinta graful pentru cuvintele: cerne, carne, carte, certe, curte, curbe, curse, burse Cel mai scurt drum intre carte si burse este: carte -> curte -> curse -> burse
