Sarcini, platforma de conținut

№9 digraph matrice dat adiacență. trebuie:
a) pentru a desena graficul;
b) să aloce componente puternic conectate;
c) înlocuirea tuturor arcelor în coaste și graficul neorientat rezultat pentru a găsi circuitul Euler (sau bucla).

a) să elaboreze un grafic.

Grafic Matrix adiacenta (digraph) - este o matrice pătratică de dimensiuni astfel încât pentru orice element din coloana lea rând și jth este 1 dacă nodurile și -lea -lea conectate de marginea (arc începând de la partea de sus), și este 0 altfel caz.

-- 1, în cazul în care partea de sus și - legate (de digraph arc merge de la c), 0 altfel.

Conform acestui construct un grafic direcționat.

b) Selectați componentele de conectivitate puternice.

Componentele conectate puternic digraph - este conectat maximale subgrafurilor sale. Conceptul de conectivitate puternică înțeles după cum urmează: de la fiecare vârf al subgraful este calea către restul vârfurile subgrafic și vice-versa, celelalte vârfuri ale subgraful este modul în partea de sus a acestei subgrafic. Acest subgrafic se numește o componentă digraph puternic conectată.

Pentru a izola componentul puternic conectat ca un algoritm de bază digraph folosind o metodă de căutare în profunzime. intrare de căutare în profunzime în exemplul de curs. Pentru a simplifica notatia, vom nota în partea de sus a figurii.

Pornim de la partea de sus 1.

De la un nod de by-pass este finalizată.

Pentru a începe cu 2 noduri.

2 vârfuri de by-pass este finalizată.

Vom începe cu 6 vârfuri.

Ca rezultat, o secvență de noduri: 1,4,2,5,3,6.

Din recordul de căutare adancime arată care poate fi atins de la 1 4 (), și de la 4 realizabile 1 (). De asemenea, se observă că 2 realizabil 3 și 5 () 2 din 3 și 5 sunt realizabile () și 2 din 5 este realizabil (). Astfel, au identificat două componente puternic conectate (1,4) și (1,3,5). Sau scrie alt mod: Cele două componente ale conectivității puternice și. arc de gros prezintă componentele de conectivitate puternice.

c) Înlocuiți toate muchiile și coaste în graful neorientat rezultat pentru a găsi circuitul Euler (sau bucla).

Pentru a găsi circuitul Euler într-un grafic conectat, care are vârfuri numai chiar și putere, folosiți algoritmul Fleury:

1) Mișcarea pornește de la un nod arbitrar; Suntem pe margini, inclusiv marginile din lanțul Euler și eliminarea lor din grafic.

2) Odată ce partea de sus a calea aleasă de istmul numai în cazul în care nu există nici o cale prin ciclul.

3) Dacă graficul sunt coaste, care nu pot fi utilizate pentru continuarea căii existente, ar trebui să înceapă să construiască o buclă simplă închisă a finalizat deja incidentul de sus și marginile acestuia, în cazul în care acesta din urmă nu a mai fost utilizată anterior.

Construcție poate începe de la orice margine a graficului. Din moment ce obținem ciclu:

În acest caz, odată ce am primit circuitul Euler. Marginea este un istm (bridge).

№10 grafic cu matrice specificate lungimi de arc ponderate. Desenați un grafic. Găsiți: a) minimum de greutate se întinde copac;
b) o distanță scurtă de la vertexul la alte vârfuri v3 grafic utilizând algoritmul lui Dijkstra.

Desenați un grafic folosind regula:

Aceasta este, la intersecția rândurilor și coloanelor conține lungimea arcului sau infinit dacă nu arce (margini) între nodurile respective.

a) Găsiți arborele de acoperire greutate minimă.

Pentru a găsi algoritmul spanning tree Kruskal isplzuem greutate minimă.

Construcția miezului va începe la margine cu greutate minimă.

Cum să se alăture coaste la miezul:

În partea de sus, selectați din care nu este asociat cu nervură marginile mai puțin în greutate și atașați-l la miezul.

În partea de sus a celor trei coaste nu sunt conectate cu aceleași două cea mai mică greutate, pentru a alege margine și atașați-l la miezul. Îmbinarea coaste nu formează o buclă.

Captatorul de sus a marginilor care nu au legătură cu nervura cu cea mai mică greutate și atașați-l la miezul. Îmbinarea coaste nu formează o buclă.

Primele două nu sunt conectate la stânga margini. Alegerea nervura cu cea mai mică greutate atunci când aderarea la miezul, bucla nu se formează.

Prin adăugarea oricare din ciclul Contururile vor rămase.

Toate muchiile sunt luate în considerare, algoritmul este terminat.

Scheletul a subliniat marginile ingrosate.

b) Găsiți cea mai mică distanță de la vârf pentru a graficului celelalte vârfuri v3 folosind algoritmul lui Dijkstra.

Tops furniza note, iar graficul va fi prezent etichetă nu este găsit încă drumul.

Nodurile care vor deveni permanente, selectați semnul.

Vertex A a devenit constantă, și cu ea B adiacentă, C și F distanța găsită pentru ei (este de 1, 5 și 3) este deplasată pe etichetă (1 A), (5, A) și (3, A)

Distanțele minime de la un vârf al V (1, A) devine constantă.

Se calculează distanța de la ea la C aliat, D și F. distanța C să fie 1 + 1 = 2 este mai mic decât curentul (5) vertexul eticheta C este modificată la (2, B).

Distanța a fi F 1 + 2 = 3 egal cu curent (3) noduri etichetă F nu se schimba si constanta acestuia.

Distanța până la vertex D este mai puțin nodurile etichetă este modificată la (4, B).

Dintre toate etichetele actuale C (2, B) distanțe de sus face permanent.

C Distanța de la vertexul la adiacent vertex E este mai mică decât eticheta vertex se înlocuiește cu (4, C).

De la nodurile de timp din vârful superior C D (4, B) devine constantă.

Distanța de la momentul în care vârful E prin partea de sus a C 5 + 4 = 9, în partea superioară a D 3 + 4 + 1 = 8, în partea superioară a F 1 + 3 = 4, distanța minimă va fi în partea superioară F 1 + 3 = 4 marchează vârfuri E modificări (1, F) și devine constantă.

Cea mai mică distanță de sus, sunt margini îngroșate marcate.

Cea mai mică distanță din partea de sus:

1 = 1 la calea superioară;

2. sus = 2, o cale;

3 = 3 la calea de sus;

= 4 la top 5, calea;

5. sus = 4, calea.