Fisa de lucru 1

1. Enunt

În ţara lui Byte Împărat sunt un număr de n ape curgătoare şi mări. Ştiind că într-un izvor nu se varsă nici o apă, iar mările nu se varsă în alte ape stabiliţi:

a) Care din cele n ape sunt mari si câte sunt

b) Care sunt izvoare si câte sunt.

c) Care din cele n ape sunt râuri.

d) pentru un râu k, stabiliţi numărul afluenţilor şi precizaţi care sunt.

Datele de intrare se citesc din fişierul text BYTE.TXT de forma:

n – Numărul total de izvoare, râuri şi mări

i j mai multe linii de forma i j cu semnificaţia că “ i ” se varsă în “ j ”

Indicaţii:Vom considera apele ca fiind nodurile unui graf, iar faptul că apa i se varsă în apa j va reprezenta muchia (i, j ) a grafului. Se poate observa cu uşurinţă că se va obţine un graf orientat (apa curge într-un singur sens). Se va determina pentru fiecare nod din graf semigradul interior şi semigradul exterior.

Vor fi considerate mări acele noduri care au semigradul exterior egal cu zero şi semigradul interior diferit de zero.

Vor fi considerate izvoare acele noduri care au semigradul interior egal cu zero şi semigradul exterior diferit de zero. Vor fi considerate râuri acele noduri pentru care semigradul exterior şi semigradul interior sunt diferite de zero.

Algoritm in pseudocod:

mări := Ø {mulţimea mărilor}

izvor:= Ø {mulţimea izvoarelor}

râu:= Ø {mulţimea râurilor}

pentru fiecare apă i:=1 până la n execută

| sgi := interior(i) {determină semigradul interior pentru nodul i}

| sge := exterior(i) {determină semigradul exterior pentru nodul i}

| dacă sgi = 0 şi sge<>0 atunci

| | izvor := izvor + [nodul i]

| |_▄

| dacă sge = 0 şi sgi<>0 atunci

| | mări := mări + [nodul i]

| |_▄

| dacă sgi <> 0 şi sge<>0 atunci

| | râu := râu + [nodul i]

| |_▄

|_▄

dacă mari + izvor +râu = [1..n] atunci

| scrie elementele mulţimii mări

| scrie elementele mulţimii izvor

| scrie elementele mulţimii râu

| citeşte apă

| dacă apă aparţine mulţimii râu atunci

| | sgi := interior(i)

| | scrie 'numărul afluenţilor este', sgi

| | scrie afluenţii

| |_▄

| altfel

| scrie date eronate

|_▄

2. Enunt

Se consideră o reţea de străzi ale unui cartier dintr-un oraş oarecare. Restricţiile de circulaţie în acest cartier sunt date în figura următoare:

Se cere:

a) Să se construiască graful G corespunzător acestei reţele, considerând că vârfurile grafului sânt intersecţiile străzilor, iar muchia (i, j) există în graf dacă şi numai dacă un mijloc de circulaţie poate să ajungă de la intersecţia i la intersecţia j, fără a mai trece prin altă intersecţie şi bineînţeles să nu fie considerat contravenient;

b) Scrieţi matricea de adiacenţă a grafului astfel format;

c) Scrieţi care sunt nodurile adiacente cu vârful 1;

d) Folosind matricea de adiacenţă determinaţi care sunt acele vârfuri cu grad exterior de valoare maximă.

EXERCITII DIN VARIANTE DA BACALAUREAT

3. Se consideră graful orientat cu 5 noduri numerotate de la 1 la 5 şi cu arcele: (1,2),(2,1),(2,5),(3,2),(4,3),(5,1),(5,2),(5,4). Determinaţi gradul intern al nodului cu gradul extern maxim.

4. Suma gradelor interne ale tuturor vârfurilor unui graf orientat este totdeauna egală cu:

• numărul valorilor de 1 aflate sub diagonala principală în matricea de adiacenţă

• suma tuturor valorilor aflate deasupra diagonalei principale în matricea de adiacenţă

• produsul gradelor externe ale tuturor vârfurilor grafului

• suma gradelor externe ale tuturor vârfurilor grafului

5.

Un graf orientat este reprezentat prin matricea de adiacenţă dată alăturat. Precizaţi care sunt nodurile pentru care gradul interior este mai mare decât gradul exterior.

0 1 1 0 0 0

0 0 1 1 0 1

1 1 0 1 0 0

0 0 0 0 1 0

0 1 0 0 0 0

0 1 0 0 1 0

6.Gradul intern pentru nodul cu eticheta i dintr-un graf orientat la care se cunoaşte matricea de adiacenţă este egal cu numărul de cifre egale cu 1 aflate pe:

• linia i

• diagonala principală

• diagonala secundara

• coloana i

7.Fie G un graf orientat cu 6 vârfuri dat prin matricea de adiacenţă alăturată. Precizaţi câte dintre vârfurile grafului au gradul intern egal cu gradul extern?

0 0 0 0 1 0

1 0 0 1 0 1

0 0 0 0 0 0

1 0 0 0 1 0

0 1 0 0 0 0

0 0 0 0 1 0

8.Graful orientat G=(X,U) are 20 de vârfuri numerotate de la 1 la 20 şi arce între vârfurile numerotate i şi j care îndeplinesc condiţiile: i este număr de o singură cifră iar j este un număr de două cifre ce are în scrierea sa cifra i. Numărul valorilor de 1 din matricea de adiacenţă asociată grafului G este:

9.Fie graful orientat G=(V,E) unde mulţimea nodurilor este V={1,2,3,4,5,6,7}, iar mulţimea arcelor este E={[1,2],[1,6],[2,5], [2,6],[3,4],[4,3],[6,2], [6,5],[3,7],[4,7]}. Numărul nodurilor grafului G care au gradul exterior egal cu 0 este: