graf 11 A
2
Un exemplu de graf orientat este: reţeaua de străzi a unui oraş. Străzile sunt arcele în graf, iar intersecţiile reprezintă vârfurile grafului . Întrucât mergând pe jos ne putem deplasa pe orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui oraş” este neorientat. Cu totul altfel stau lucrurile în ceea ce priveşte conducătorii auto, pentru că în orice oraş există străzi cu sens unic. Pentru un şofer străzile trebuie să primească în graf o anumită orientare . Desigur că acele străzi pe care se poate circula în ambele sensuri vor primi orientare dublă . Desenează harta schematica a Centrului din orasul Pecica cu cele mai importante cladiri, şi directia străzilor marchează prin sageti . Fiecare elev va reprezenta o clădire. Numele clădirii se scrie pe foaie Într-un grup sunt n elevi, băieţi şi fete, pe care-i numerotăm 1, 2, ..., n. Fiecare elev cunoaşte o parte din ceilalţi elevi. Relaţia de cunoştinţă nu este neaparat reciprocă (dacă x îl cunoaşte pe z, nu înseamnă că şi y trebuie să-l cunoască pe x). Unul dintre elevi are un CD foarte valoros, cu multe jocuri demonstrative, pe care toţi membrii grupului vor să-l aibe fie şi pentru scurt timp, pentru a şi-l copia pe calculatorul propriu. CD-ul circulă printre membrii grupului în felul următor: fiecare elev după ce l-a primit de la altcineva îl dă mai departe, dar numai unui elev pe care îl cunoaşte, pentru că nu doreşte să ajungă în mâna unor persoane în care nu poate avea încredere. Determinaţi o modalitate (dacă există) prin care CD-ul să circule pe la fiecare elev o singură dată, transmiterea lui făcându-se numai către o cunoştinţă, iar în final CD-ul să ajungă din nou la proprietarul său. Indicaţie: Pentru a rezolva cerinţa trebuie să construiţi un circuit elementar care să cuprindă toţi elevii grupului, pornind de la elevul care are CD-ul valoros.
-
Upload
berindea-petra -
Category
Documents
-
view
221 -
download
6
description
test
Transcript of graf 11 A
Un exemplu degraf orientateste: reeaua de strzi a unui ora. Strzile suntarcelen graf, iar interseciile reprezintvrfurile grafului. ntruct mergnd pe jos ne putem deplasa pe orice strad n ambele sensuri, vom spune c din punctul de vedere al pietonilor, graful unui ora este neorientat.
Cu totul altfel stau lucrurile n ceea ce privete conductorii auto, pentru c n orice ora exist strzi cu sens unic. Pentru un ofer strzile trebuie s primeascn grafo anumitorientare. Desigur c acele strzi pe care se poate circula n ambele sensuri vor primiorientare dubl.
Deseneaz harta schematica a Centrului din orasul Pecica cu cele mai importante cladiri, i directia strzilor marcheaz prin sageti .Fiecare elev va reprezenta o cldire. Numele cldirii se scrie pe foaie
ntr-un grup sunt n elevi, biei i fete, pe care-i numerotm 1, 2, ..., n. Fiecare elev cunoate o parte din ceilali elevi. Relaia de cunotin nu este neaparat reciproc (dac x l cunoate pe z, nu nseamn c i y trebuie s-l cunoasc pe x).Unul dintre elevi are un CD foarte valoros, cu multe jocuri demonstrative, pe care toi membrii grupului vor s-l aibe fie i pentru scurt timp, pentru a i-l copia pe calculatorul propriu. CD-ul circul printre membrii grupului n felul urmtor: fiecare elev dup ce l-a primit de la altcineva l d mai departe, dar numai unui elev pe care l cunoate, pentru c nu dorete s ajung n mna unor persoane n care nu poate avea ncredere.
Determinai o modalitate (dac exist) prin care CD-ul s circule pe la fiecare elev o singur dat, transmiterea lui fcndu-se numai ctre o cunotin, iar n final CD-ul s ajung din nou la proprietarul su.
Indicaie:Pentru a rezolva cerina trebuie s construii un circuit elementar care s cuprind toi elevii grupului, pornind de la elevul care are CD-ul valoros.
rosie ambele sensuri negru doar o directie
