A apărut o eroare în acest obiect gadget

joi, 4 mai 2017

Grile grafuri neorientate...orientate...arbori


































GRAFURI NEORIENTATE



 NOŢIUNI INTRODUCTIVE. Subgraf. Graf parţial


1. Se dă un graf neorientat cu n noduri prin matricea de adiacenţă citită din fişierul GRAF1.TXT. Să se formeze vectorul de muchii corespunzător grafului şi să se afişeze în fişierul MUCHII.TXT
2. Din fişierul GRAF2.TXT se citeşte matricea de adiacenţă a unui graf neorintat cu n noduri. Să se formeze reprezentarea grafului prin listele de vecini şi să se afişeze.

3. Fişierul  GRAF3.IN conţine pe prima linie numărul de noduri şi numărul de muchii ale unui graf neorientat, iar pe urmatoarele m linii extremităţile muchiilor separate printr-un spaţiu. Să se formeze matricea de adiacenţă şi să se afişeze.
4. Fişierul GRAF4.IN conţine pe prima linie numărul de noduri şi numărul de muchii ale unui graf neorientat, iar pe următoarele m linii extremităţile muchiilor separate printr-un spatiu, respectiv costul muchiei. Rezolvaţi următoarele cerinţe:
     a)    Să se determine media costurilor.
  b)    Să se afişeze graful parţial obţinut prin eliminarea muchiilor de cost egal cu o valoare citită c.
     c)  Să se afişeze graful parţial obţinut prin eliminarea muchiilor de cost maxim, dintre costurile tuturor muchiilor.
5. Se dă un graf neorientat prin matricea de adiacenţă citită dintr-un fişier text care conţine pe prima linie numărul de noduri, iar pe următoarele linii matricea de adiacenţă. Să se verifice dacă o matrice patratică de dimensiune n´n poate fi sau nu matricea de adiacenţă a unui graf parţial.
6. Din fişierul GRAF6.TXT se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se afişeze subgraful obţinut prin eliminarea nodurilor impare.
7. Să se genereze toate grafurile neorientate cu n noduri.
8. Din fişierul GRAF8.TXT se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se genereze toate grafurile parţiale ale grafului iniţial.
9. Din fişierul GRAF9.IN se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se genereze toate subgrafurile grafului iniţial.
10. Din fişierul GRAF.IN se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se genereze subgraful cu număr maxim de noduri, dar cu proprietatea că fiecare nod din subgraf are gradul cel puţin egal cu o valoare dată v.

 PARCURGERI ALE GRAFURILOR


1. Se dă un graf neorientat prin matricea de adiacenţă citită dintr-un fişier text care conţine pe prima linie numărul de noduri, iar pe următoarele linii matricea de adiacenţă. Să se afişeze parcurgerea grafului în laţime.
2. Se dă un graf neorientat prin matricea de adiacenţă citită dintr-un fişier text care conţine pe prima linie numărul de noduri, iar pe următoarele linii matricea de adiacenţă. Să se afişeze parcurgerea grafului în adâncime.
3. Se dă un graf neorientat prin matricea de adiacenţă citită dintr-un fişier text care conţine pe prima linie numărul de noduri, iar pe următoarele linii matricea de adiacenţă. Să se determine lungimea lanţului minim dintre două noduri x şi y citite de la tastatură.
4. Se dă un graf neorientat prin matricea de adiacenţă citită dintr-un fişier text care conţine pe prima linie numărul de noduri, iar pe următoarele linii matricea de adiacenţă. Cunoscând nodul x, citit de la tastatură, să se determine lungimile lanţurilor minime de la x la restul nodurilor, dacă există, iar dacă nu există se va afişa –1.
5. Se dă un graf neorientat prin matricea de adiacenţă citită dintr-un fişier text care conţine pe prima linie numărul de noduri, iar pe următoarele linii matricea de adiacenţă. Utilizând parcurgerea în lăţime să se verifice dacă graful conţine sau nu cicluri.

 GRADUL UNUI NOD. CONEXITATE


1. Se dă un graf neorientat prin matricea de adiacenţă citită dintr-un fişier text care conţine pe prima linie numărul de noduri, iar pe următoarele linii matricea de adiacenţă. Rezolvaţi următoarele cerinţe:
   a) Să se afişeze pentru fiecare nod gradul.
   b) Să se afişeze nodurile care au gradul maxim.
   c) Să se afişeze nodurile izolate.
   d) Să se afişeze nodurile terminale.
2. Din fişierul GRAF2.IN se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se determine subgraful obţinut prin elimi­narea nodurilor care au gradul egal cu o valoare dată k.
3. Să se verifice dacă un graf neorientat dat prin matricea de adiacenţă, citită dintr-un fişier text, este sau nu conex.
4. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se verifice dacă între două noduri x şi y, citite de la tastatură, există sau nu lanţ.
5. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se scrie în fişierul COMP.OUT, pe câte o linie, componentele conexe din care este format graful neorientat.
6. Din fişierul GRAF6.TXT se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se adauge un număr minim de muchii astfel încât graful să devină conex. Muchiile adăugate se vor scrie în fişierul MUCHII.OUT, câte una pe linie.
7. Din fişierul GRAF7.TXT se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se afişeze pe ecran componentele conexe care sunt formate din k noduri, unde k este o valoare citită de la tastatură.

8. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text şi un şir x cu p elemente. Să se verifice dacă elementele şirului pot fi nodurile unui lanţ, iar în caz afirmativ să se specifice natura lanţului.
9. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text şi un şir x cu p elemente. Să se verifice dacă elementele şirului pot fi nodurile unui ciclu, iar în caz afirmativ să se specifice natura ciclului.
10. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se genereze toate lanţurile elementare care încep cu un nod dat y.

11. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se genereze toate lanţurile elementare au ca extremităţi nodurile x1 şi y1.
12. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se genereze toate lanţurile elementare care au lungimea L.
13. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se genereze toate ciclurile elementare care trec numai prin noduri pare.
14. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se genereze toate ciclurile care au lungimea L.
15. Se dă un şir d cu n noduri. Fiecare componentă fiind un număr natural. Să se verifice dacă valorile din şir pot fi gradele nodurilor unui graf neorientat, iar în caz afirmativ să se afişeze unul din grafurile corespunzătoare.
16. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se asocieze fiecărui nod câte o culoare astfel încât să nu existe două noduri adiacente cu aceeaşi culoare. Numărul de culori utilizate trebuie să fie minim.
17. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se asocieze fiecărei muchii o culoare astfel încât să nu existe două muchii incidente cu aceeaşi culoare. Numărul de culori utilizate trebuie să fie minim.

 CLASE  SPECIALE  DE  GRAFURI


1. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se verifice dacă graful este complet.
2. Să se genereze toate grafurile de tip bipatit complet cu n noduri.
3. Să se genereze toate grafurile de tip bipatit complet cu n noduri
ştiind că cele două mulţimi au p, respectiv n-p elemente.

ARBORI


1. Din fişierul GRAF1.TXT se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se verifice dacă graful poate fi arbore.
2. Se dă un arbore cu n noduri prin matricea de adiacenţă şi prin rădăcina r. Datele se vor citi dintr-un fişier. Să se determine numărul de nivele ale arborelui, cunoscând că rădăcina se găseşte pe nivelul 1.
3. Dându-se un arbore cu n noduri prin matricea de adiacenţă şi prin rădăcina r, să se afişeze nodurile de pe nivelul k, unde k se citeşte de la tastatură.
4. Se dă un arbore cu n noduri prin matricea de adiacenţă. Să se determine rădăcina arborelui astfel încât numărul de nivele să fie minim.
5. Se dă un graf neorientat prin vectorul de muchii. Fiecare muchie este caracterizată prin cele două extremităţi, respectiv prin cost. Să se determine arborele parţial de cost minim conform algoritmului lui Kruskal.
6. Se dă un graf neorientat prin vectorul de muchii. Fiecare muchie este caracterizată prin cele două extremităţi, respectiv prin cost. Să se determine arborele parţial de cost minim conform algoritmului lui Prim.

ARBORI BINARI


1. De pe prima linie a fişierul text ARB.TXT se citesc două valori, prima reprezentând numărul de noduri ale unui arbore, iar a doua reprezentând rădăcina arborelui. Să se verifice dacă arborele este binar.
2. Să se scrie un program care realizează următoarele cerinţe. Opţiu­nile se vor include într-un meniu din care utilizatorul va avea posibili­tatea să aleagă operaţia dorită.
            0. Ieşirea din aplicaţie.
            1. Crearea arborelui binar.
            2. Parcurgerea în preordine.
            3. Parcurgerea în inordine.
            4. Parcurgerea în postordine.
            5. Afişarea frunzelor.
            6. Afişarea nodurilor cu un singur descendent.
            7. Afişarea nodurilor cu doi descendenţi.
            8. Verificarea dacă arborele este complet.
            9. Determinarea numărului de nivele.
           10.  Afişarea nodurilor de pe nivelul k.
           11.  Afişarea arborelui pe nivele.
           12. Verificarea dacă frunzele sunt pe ultimul nivel.
           13.  Verificarea dacă arborele este echilibrat.
           14.  Adăugarea unui număr minim de noduri astfel încât arborele să devină complet.
           15.  Afişarea vectorilor tată şi descendent.

3. Să se afişeze nodurile terminale ale unui arbore binar pentru care se citeşte vectorul tată din fişierul text ARB3.TXT.
4. De pe prima linie a fişierului text ARB4.TXT se citesc: numărul de noduri pentru un arbore binar (n), rădăcina acestuia (r) şi două valori (x şi y) corespunzătoare a două noduri. Să se determine lungimea lanţului minim dintre nodurile citite.

 PROBLEME PROPUSE


1. Se dă un graf neorientat prin matricea de adiacenţă citită dintr-un fişier text care conţine pe prima linie numărul de noduri, iar pe următoarele linii matricea de adiacenţă. Să se determine un nod al grafului cu proprietatea că suma distanţelor minime de la el la restul nodurilor grafului este şi ea minimă.

2. Din fişierul GRAF.IN se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se afişeze subgraful obţinut prin eliminarea nodurilor prime.

3. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se verifice dacă trei noduri x, y, z se găsesc sau nu în aceeaşi componentă conexă.

4. Din fişierul GRAF.IN se citeşte matricea de adiacenţă a unui graf neorientat cu n noduri. Să se afişeze pe ecran componentele conexe care sunt formate dintr-un număr maxim de noduri.

5. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se genereze toate lanţurile care au lungimea L.

6. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se genereze toate ciclurile elementare care au lungimea L.

7. Dându-se un arbore cu n noduri prin matricea de adiacenţă si prin rădăcina r, să se afişeze nodurile arborelui pe nivele.

8. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se genereze toate modalităţile de a colora fiecare nod astfel încât numărul de culori să fie maxim 5, şi să nu existe două noduri adiacente cu aceeaşi culoare.


9. Se dă un graf neorientat prin matricea de adiacenţă, citită dintr-un fişier text. Să se genereze toate modalităţile de a colora fiecare muchie astfel încât numărul de culori să fie maxim 5, şi să nu existe două muchii incidente cu aceeaşi culoare.

GRAFURI ORIENTATE



1. NOŢIUNI INTRODUCTIVE. Graf paţial. Subgraf

1. Se dă un graf orientat în fişierul GRAF1.IN prin numărul n de noduri şi perechi de numere asociate arcelor (câte un arc pe fiecare linie). Vârfurile grafului sunt numerotate prin numerele 1,2,…,n. Să se afişeze în fişierul SUCC.OUT succesorii fiecărui nod, iar în fişierul PRED.OUT predecesorii fiecărui nod.
2. De pe prima linie a fişierului GRAF2.IN se citeşte o valoare întreagă n reprezentând numărul de noduri ale unui graf orientat. De pe următoarele n linii se citesc componentele matricei de adiacenţă asociate grafului. Să se afişeze în fişierul PARTIAL.OUT matricea de adiacenţă a grafului parţial obţinut prin eliminarea arcelor cu ambele extremităţi pare.
3. De pe prima linie a fişierului GRAF3.IN se citesc valorile n şi m reprezentând numărul de noduri, respectiv arce ale unui graf orientat. De pe fiecare dintre următoarele m linii se citesc câte 3 valori întregi reprezentând extremităţile şi costul unui arc. Să se determine costul mediu al grafului şi să se afişeze în fişierul GRUPE.OUT arcele pe grupe, o grupa fiind formată din toate arcele cu acelaşi cost.
4. Se citesc de la tastatură două valori întregi n şi m reprezentând numărul de vârfuri, respectiv arce ale unui graf orientat. Să se afişeze în fişierul V_ARC.OUT matricea vârfuri-arce ataşată grafului.
5. De pe prima linie a fişierului GRAF5.IN se citeşte o valoare întreagă n reprezentând numărul de vârfuri ale unui graf orientat, iar de pe următoarele linii se citesc perechi de numere corespunzătoare extremitaţilor arcelor grafului. Din fişierul GRAF_P.IN se citeşte matricea de adiacenţă a unui graf. Să se verifice dacă această matrice poate fi reprezentarea unui graf parţial al grafului din GRAF5.IN.
6. Se consideră un graf orientat G cu n vârfuri a cărui matrice de adiacenţă se citeşte din fişierul GRAF6.IN. În mulţimea m_sub de numere întregi se găsesc vârfurile unui graf orientat G1 pentru care se citesc extremitaţile muchiilor de la tastatură şi se construieşte vectorul de muchii. Să se verifice dacă G1 este subgraf al lui G.

2. GRADELE NODURILOR. MULŢIMI ATAŞATE


1. Se citeşte matricea de adiacenţă ataşată unui graf orientat cu n noduri din fişierul text GRAF1.IN. De la tastatură se citeşte o valoare întreagă x (). Să se realizeze un meniu pentru determi­narea:
-          gradului exterior al lui x;
-          gradului interior al lui x;
-          mulţimii
-          mulţimii
-          mulţimii
-          mulţimii
2. De pe prima linie a fişierului text GRAF2.IN se citesc două valori întregi n, m, reprezentând numărul de noduri, respectiv arce ale unui graf orientat, iar de pe următoarele n linii  se citesc componentele matricei vârfuri-arce. Să se afişeze nodurile pentru care gradul interior este egal cu cel exterior.
3. Se defineşte un graf orientat prin vectorul de arce citit din fişierul GRAF3.IN (pe prima linie a fişierului numărul n de noduri, respectiv numărul m de arce, iar pe următoarele m linii extremităţile arcelor despărţite prin spaţiu). Să se verifice dacă graful conţine noduri izolate, urmând a fi afişate aceste noduri în cazul în care există.
4. Se dă un grup format din n persoane şi m perechi numere întregi (x,y) cu semnificaţia persoana x cunoaşte persoana y. Relaţia de cunoştinţă nu este neapărat reciprocă. Numim celebritate o persoană care este cunoscută de toţi membri grupului, dar nu cunoaşte pe niciunul dintre aceştia. Să se verifice dacă în grup avem o astfel de celebritate.

3. REPREZENTĂRI ALE GRAFURILOR ORIENTATE


1. Se consideră un graf orientat cu n vârfuri, definit prin intermediul vectorului de muchii. Valorile lui n, respectiv valorile corespunzătoare extremităţilor se citesc din fişierul GRAF1.IN. Să se genereze în fişierul MAT_D.OUT, matricea drumurilor, obţinută conform algorit­mului lui Roy-Warshall.
2. În fişierul GRAF2.IN se găseşte matricea de adiacenţă a unui graf orientat şi pe ultima linie a fişierului o valoare întreagă asociată unui vârf. Să se determine numărul drumurilor care pleacă din vârful respectiv, precum şi numărul drumurilor care intră în acesta.

3. Să se determine toate drumurile elementare într-un graf orientat care au ca extremităţi două noduri x şi y date. Datele se citesc din fişierul GRAF3.IN după cum urmează: pe prima linie numărul de noduri n şi valorilor corespunzătoare lui x şi y, iar pe următoarele n linii elementele matricei de adiacenţă. Afişarea în DRUMURI.OUT.
4. Pentru un graf orientat a cărui matrice de adiacenţă se citeşte din fişierul GRAF4.IN, să se verifice dacă există un drum elementar care să treacă prin toate nodurile acestuia.
5. Să se determine circuitele de lungime L dintr-un graf orientat pentru care se citesc datele din fişierul GRAF5.IN, după cum urmează: pe prima linie numărul n de vârfuri şi lungimea L, iar pe următoarele n linii componentele matricei de adiacenţă a grafului. Afişarea se va face în fişierul text CIRCUITE.OUT.
6. Se defineşte un graf orientat prin vectorul de arce. Să se verifice dacă există un circuit elementar care să treacă prin toate nodurile impare ale grafului.
7. Din fişierul GRAF6.IN se citeşte matricea de adiacenţă a unui graf orientat. De pe fiecare linie a fişierului SECVENTE.IN se citesc valori întregi corespunzătoare unei secvenţe (nu se cunoaşte numărul liniilor din fişier şi nici numărul valorilor de pe fiecare linie). Pentru fiecare secvenţă să se verifice dacă reprezintă drum şi în caz afirmativ să se specifice natura acestuia, datele urmând a fi afişate în fişierul REZULTAT.OUT.

8. Se citesc k valori de la tastatură. Să se verifice dacă cele k valori pot constitui un circuit în graful orientat pentru care se citesc extremităţile arcelor şi numărul de vârfuri din fişierul GRAF8.IN şi în caz afirmativ să se specifice natura acestuia.

4.4. CONEXITATE ŞI TARE CONEXITATE


1. Se defineşte un graf orientat prin vectorul de muchii citit din fişierul GRAF1.IN (numărul de noduri pe prima linie, pe următoarele linii extremităţile muchiilor). Să se verifice dacă graful este sau nu conex.
2. Se citeşte matricea de adiacenţă a unui graf orientat din fişierul GRAF2.IN. Să se determine componentele conexe cu număr maxim de elemente şi să se afişeze aceste componente în fişierul COMP.OUT.
3. Din fişierul GRAF3.IN se citeşte matricea de adiacenţă a unui graf orientat. Să se afişeze în fişierul T_CON.OUT componentele tare conexe ale grafului.

1. Se consideră un un graf orientat cu n vârfuri în care fiecare arc are asociat câte un cost. Să se afişeze folosind algoritmul Roy-Floyd, pentru fiecare pereche de noduri (x,y) costul drumului minim de la x la y.
2. Se consideră un graf orientat cu n vârfuri în care fiecărui arc îi este asociat un cost. Pentru un vârf dat (start) se cere să se determine drumurile minime şi costurile acestora de la vârful dat la celelalte vârfuri ale grafului, conform algoritmului lui Dijkstra.

4.6. PROBLEME PROPUSE


1. De pe fiecare linie a fişierului text GRAF1.IN se citesc câte 3 valori corespunzătoare extremităţilor, respectiv costului unui graf orientat cu n vârfuri. Să se realizeze un subprogram care determină pentru două noduri oarecare x şi y introduse ca parametri, costul drumului maxim de la x la y.

2. Din fişierul text GRAF2.IN se citeşte matricea de adiacenţă a unui graf orientat cu n noduri. Să se afişeze în fişierul text COMP.OUT componentele conexe ale grafului, formate din p vârfuri (p citit de la tastatură).

3. Să se genereze folosind metoda backtraking drumurile de lungime pară care ajung într-un vârf x dat al unui graf orientat cu n vârfuri.

4. Ştiind că pentru fiecare vârf al unui graf orientat cu n vârfuri avem definită câte o culoare nu neapărat distincte, să se verifice dacă există un drum elementar care să treacă prin toate vârfurile colorate diferit.

5. Să se genereze folosind metoda backtraking circuitele elementare şi neelementare ale unui graf orientat cu n vârfuri pentru care se citeşte din fişierul GRAF5.IN matricea vârfuri-arce.

6. Pentru 3 valori corespunzătoare vârfurilor a, b, c ale unui graf orientat a cărui matrice de adiacenţă se citeşte din fişierul GRAF6.IN să se verifice dacă aceste fac parte din aceeaşi componentă tare conexă.

7. Din fişierul GRAF7.IN se citeşte matricea de adiacenţă a unui graf orientat. De pe fiecare linie a fişierului SECVENTE.IN se citesc valori întregi corespunzătoare unei secvenţe (nu se cunoaşte numărul liniilor din fişier şi nici numărul valorilor de pe fiecare linie). Pentru fiecare secvenţă să se verifice dacă reprezintă circuit şi în caz afirmativ să se specifice natura acestuia, datele urmând a fi afişate în fişierul OUT.TXT.