Grafuri orientate . Aplicatii

1. Intr-o clasa sunt n elevi. Dirigintele doreste sa construiasca un sistem de informare in clasa astfel incat fiecare elev sa sa obtina informatia cat mai rapid. Dirigintele anunta un elev (seful clasei). Acesta va anunta alti doi elevi care la randul lor vor anunta fiecare cate trei elevi. In continuare fiecare elev va anunta alti trei.. Sa se scrie un program care construieste o astfel de structura de informare.

2. Numim transpusul unui graf G=(X,U), graful G’ care are aceeasi multime de varfuri, arcele sale fiind arcele lui G, dar avand sens opus. Dandu-se G prin matricea de adiacenta sau prin lista de adiacenta, sa se determine transpusul grafului dat.

3. Sa se genereze matricea drumurilor asociata unui graf

4. Dandu-se matricea drumurilor asociata unui graf orientat sa se determine daca grafula are (si sa se afiseze) varfuri izolate.

5. Fie un graf orientat memorat prin matricea de adiacente. Sa se genereze daca este posibil un graf avand aceeasi matrice a drumurilor dar numar mai mic de arce (eventual numar minim de arce).

6. Un arbore genealogic retine cele m relatii a n persoane: cei 2 stramosi comuni si in continoare perechi care reprezinta ascendent-descendent direct. Sa se afiseze pentru o persoana x:

-ascendentii

-descendentii

-parintele

-fratii

Ex:

Date de intrare:

13

14

1 3

1 4

1 5

2 3

2 4

2 5

3 12

3 7

3 8

8 9

4 10

10 11

5 12

5 13

pt x=8 se afiseaza:

-3,1,2 ascendenti

- 9 descendent

- 3 parinte

-12, 7 frati

7. Elevii unei clase au de scris o compunere la limba franceza. Deoarece doresc sa se inspire unii de la altii, ei isi imprumuta unii altora caietele in care si-au scris temele. Se cunosc perechile de elevi (numerotati de la 1 la n) care si-au imprumutat caietele. Primul din pereche este cel care a dat tema, al doilea – cel care l-a primit. Se considera ca daca X a dat caietul lui Y, iar Y lui Z, tema lui Z este inspirata atat din tema lui X, cat si din tema lui Y. Scrieti un program care sa afiseze:

• La cati colegi a imprumutat caietul fiecare elev si de la cati colegi a imprumutat fiecare
• Caror colegi le-a imprumutat X caietul sau
• Elevul care a dat caietul celor mai multi colegi
• Elevul care a luat cele mai multe caiete pentru a se inspira
• Tema carui elev a inspirat cele mai multe alte teme
• Exista elevi in clasa care nu au dat si nu au primit nici un caiet? Care?
• Se citeste de la tastatura o lista de elevi (nr. lor de ordine). Precizati daca este adevarat faptul ca fiecare elev din lista a imprumutat caietul de la cel care urmeaza imediat dupa el in lista.

8. Baietii dintr-o scoala corespondeaza cu fetele dintr-o alta scoala. Copii sunt numerotati de la 1 la n. Se cunosc perechi de numere (x-y) cu semnificatia: (x ii scrie lui y, nu neaparat si invers). Se stie ca nici un baiat nu corespondeaza cu alt baiat si nici o fata cu alta. Cititi perechile de directii de corespondenta si afisati (daca este posibil) grupa fetelor si grupa baietilor. Copilul 1 este baiat.

9. Intr-un parc de distractii exista un trenulet care trece prin mai multe tuneluri. Se cunosc: numarul de tuneluri, numarul de portiuni de sina de tren si sensul de parcurgere intre doua tuneluri alaturate. Proprietarul parcului are la dispozitie nc culori si isi propune sa vopseasca tunelurile astfel incat oricare doua tuneluri alaturate sa fie colorate diferit. Afisati 3 solutii.

10. La un concurs de orientare juriul are o harta de repere intre repere fiind stabilite sensuri unice de parcurgere. Pentru a complica probele trebuie aleasa o harta care sa contina cel putin un circuit. Verificati daca harta contine circuite.

11. Sa se determine produsul numerelor de ordine al varfurilor unui graf prin parcugrgere in latime si adancime. Afisati valoare mai mare.

12. Problema celebritatii: o persoana cunoscuta de toata lumea si care nu cunoaste pe nimeni este considerata celebritate. Sa se determine daca un graf contine o celebritate.

13. Unui graf orientat prin eliminarea orientarii i se poate atasa un graf neorientat. Sa se determine daca graful neorientat atasat este conex si graful orientat tare conex.

14. Se numeste graf turneu un graf orientat cu proprietatea ca intre oricare doua varfuri distincte exista un arc si numai unul. Teorema: orice graf turneu contine un drum elementar care trece prin toate varfurile grafului. Sa se determine daca un graf dat este graf turneu. In caz afirmativ se va determina un drum elementar de la x la y.

15. Sunt n copii care au fost impreuna la biblioteca si au imprumutat m carti (m<n) .Copiii isi imprumuta unii altora carti (un copil poate imprumuta o singura carte la un moment dat altui copil).. Se cunoaste cine imprumuta, cui imprumuta si ce carte ii da. Sa se afle:

· Daca exista elevi care au citit toate cartile

· Daca exista elevi care nu au citit nici o carte

· Care este cartea citita de cei mai multi elevi?