1. Formulați definiția unui grafic.
2. Listați tipurile de grafice.
3. Afișează modalitățile de specificare a negrafului.
4. Explicați conceptele: incidența și contiguitatea.
5. Ce se numește componenta conectată a unui non-grafic?
6. Care este gradul vârfului? Formulează o teoremă cu privire la suma gradelor de vârfuri.
7. Formulați definiția rutei în grafic.
8. Care este ruta minimă?
9. Listați tipurile de rute.
SUBIECT: OBIECTIVELE GRAFELOR NEGOCIABILE
1. Căutați o rută cu un număr minim de margini
2. Caracteristicile metrice ale unui grafic nedirecționat
3. Trasee minime în graficele încărcate
4. Sarcini pe copaci
5. Rangul ciclului unui grafic. Numărul ciclomatic
Atunci când rezolvăm unele probleme aplicate, este adesea nevoie să găsim un traseu care să lege vârfurile date în graficul G (V, X). Și ruta ar trebui să fie cea mai scurtă.
O rută în graficul G (V, X) de la vârful v până la vârful w, unde v ¹ w este numită minimă dacă are lungimea minimă între toate rutele de la v la w.
Rețineți că lungimea rutei este numărul de margini din ea.
Traseu minimal: Orice traseu minim este un circuit simplu.
Luați în considerare sarcina de a găsi ruta minimă. Introducem o notație: G (V, X) să fie un grafic, v Î V, V1 Í V; vom denumi cu G (v) = Î X> este imaginea v; G (V1) = - imaginea setului de vârfuri V1; G -1 (v) =
Fie G (V, X) un grafic cu n ≥ 2 noduri și v și w nodurile date din graficul dat. Mai mult decât atât, v¹ w. Descriim algoritmul pentru găsirea rutei minime în graficul G (algoritmul frontal al undelor).
Step1. Marcați vârful v de indexul 0. Apoi etichetați vârfurile care aparțin imaginii vertexului v. index 1. Se desemnează setul de vârfuri cu indexul 1 de către FW1 (v). Am setat k = 1.
Pasul 2. Dacă FWk (v) = Æ sau avem k = n -1, wÏ FWk (v), atunci vertexul w nu este accesibil din v, iar operarea algoritmului se termină aici. În caz contrar, treceți la pasul 3.
Pasul 3. Dacă wÏ FWk (v), apoi treceți la pasul 4. În caz contrar, există o rută de la v la w a lungimii k, iar această cale este minimă. Secvența de vârfuri vw1 w2 ... wk-1 w. unde
și este calea minimă necesară de la v la w.
Pasul 4. Marcați toate vârfurile neexploatate de indexul k + 1, care aparțin imaginii setului de vârfuri cu index k. Noi denotăm setul de vârfuri cu indexul k + 1 de FWk + 1 (v). Atribuiți k: = k + 1 și treceți la pasul 2.
Setul FWk (v) se numește frontul de undă al nivelului k.
Observație: Vârfurile w1. w2, ... wk-1 poate fi diferențiat ambiguu, în cazul în care există mai multe rute minime de la v la w.
1. Folosind algoritmul descris, găsiți ruta minimă de la v1 la v10 în graficul specificat de diagramă:
Atribuiți indexul 0 la vertexul v1 și stabiliți secvențial
Prin urmare, există o rută de la v1 la v10 cu lungimea l = 3. și este minim.
Să găsim secvența de vârfuri din acest traseu:
Avem ruta minimă: v1 v6 v7 v10. Această problemă are mai multe soluții.
2. Construiește un traseu minim de la v1 la v6 în graficul dat de matricea de adjuvant:
La vertexul v1 atribuim indexul 0 și determinăm secvențial seturile prin căutarea liniilor:
Traseul există și este egal cu l = 3. Gasim secvența de noduri din acest traseu, care caută prin coloane:
Avem ruta minimă v1 v2 v3 v6. Problema are o soluție unică.
Articole similare
Trimiteți-le prietenilor: