Componentele de conectivitate forestieră sunt copacii
Un grafic G este un arbore dacă este conectat și numărul de margini este unul mai mic decât numărul de vârfuri.
Dacă G este un copac, atunci orice lanț va fi simplu.
Orice doi vârfuri ale unui copac pot fi unite printr-un lanț, mai mult decât unul simplu.
Fie G un copac. Dacă adăugăm o margine, obținem exact un ciclu simplu.
Conceptul de arbore are o valoare importantă în teoria nașului, deci acesta este un tip simplu de grafice și, prin urmare, este adesea întâi că întrebările teoretice prezentate pentru grafurile finite sunt studiate pe el. Pe de altă parte, conceptul de copac este folosit pentru a rezolva diferite probleme tehnice. Ie are un sens aplicat.
Considerăm o astfel de problemă. Pentru a face acest lucru, introducem o definiție suplimentară.
Scheletul (arborele de acoperire) al unui grafic este subgraful său, care este un arbore și conține toate vârfurile graficului.
Lăsați n orașele să fie conectate printr-o rețea de drumuri. Costul construcției fiecărui drum între cele două orașe este cunoscut. Vom construi un grafic în care vârfurile sunt orașe, coaste sunt drumuri. Fiecare margine are o greutate egală cu costul construcției unui drum. Definim greutatea scheletului ca sumă a greutăților componentelor sale.
Proiectarea unei rețele rutiere este redusă la construirea unei structuri de garaj care are o greutate minimă. Datorită conectivității copacului, condiția este de a conecta fiecare oraș cu fiecare drum.
Considerăm mai întâi problema construirii unui schelet fără a lua în considerare greutățile marginilor sale. Ideea algoritmului este aceea că marginile graficului sunt privite într-o ordine arbitrară și, conform regulii, se ia decizia de a include următoarea margine în schelet.
Această regulă constă în verificarea condiției în care marginea considerată formează un ciclu cu un subgraf construit. Dacă condiția este îndeplinită, marginea nu este inclusă în cadru și este colorată în roșu, dacă nu, atunci este inclusă în cadru și este vopsită verde.
Lucrarea algoritmului se termină după ce subgraful aciclic se dovedește a fi conectat și conține toate vârfurile graficului.
Algoritm pentru construirea unui schelet
Pasul 1. Selectați orice margine și colorați-o în verde. Formați subgraful G1 de la această margine. Etapa 2 completă.
Opțiunea a. Dați marginea verde și formați subgraful Gi + 1. adăugând la componentele subgrafului Gi o nouă componentă conectată - marginea luată în considerare. Etapa 2 completă.
Opțiunea b. Dați marginea verde și formează subgraful Gi + 1. combinând cele două componente de conectivitate într-una. Etapa 2 completă.
Opțiune în. Dați marginea verde și formează subgraful Gi + 1. adăugând la o componentă a subgrafului Gi marginea luată în considerare. Etapa 2 completă.
Varianta d. Pentru a colora marginea în roșu dacă formează un ciclu în subgraful construit.
Construim un schelet pentru graficul dat de diagramă fără a lua în considerare greutatea marginilor.
Vopsea marginea 1. v2> în culoarea verde.
Vopsește marginea 4. v5> în verde, deoarece există o variantă a.
Culoram marginea 4. v1> în verde, deoarece există opțiunea b.
Culoram marginea 2. v5> în roșu, deoarece există o variantă a lui g.
Vopsea marginea 4. v3> în verde, deoarece există o opțiune în.
Subgraful aciclic conține toate vârfurile graficului, de unde scheletul este construit:
5. Rangul ciclului unui grafic. Numărul ciclomatic
Dacă G (V, X) nu este un grafic aciclic, atunci se poate distinge un ciclu.
Ciclurile graficului G sunt numite independente dacă diferă cel puțin printr-o margine.
Setul tuturor ciclurilor simple independente care pot fi distinse într-un multigraf constituie o bază ciclică a graficului.
Numărul de cicluri simple într-o bază se numește numărul ciclomatic sau rangul ciclic al graficului G.
Denumim numărul ciclomatic în termeni de n (G).
Dacă G (V, X) este un grafic conectat, atunci m (G) este numărul de margini din grafic, n (G) este numărul de noduri în grafic, p (G) reprezintă numărul de componente conectate în grafic.
De exemplu, nu există o bază ciclică pentru un copac; în arborele m = n - 1, p = 1 (arborele este un grafic conectat). Apoi, numărul ciclomatic este egal cu n (G) = n - 1 - n + 1 = 0. În consecință, nu există ciclu în bază.
Luați în considerare un algoritm pentru găsirea bazei ciclice a unui multigraf conectat.
Dacă n (G) = 0, atunci graficul este aciclic, nu există o bază ciclică.
Fie n (G)> 0. În G, alegeți orice arbore T. Fie numărul de vârfuri din graficul G n și numărul de margini - m. x1. x2, ..., xn-1 sunt margini în T (arborele spanning conține toate vârfurile graficului, iar proprietatea arborelui numărul de margini cu 1 este mai mic decât numărul de vârfuri), xn. xn + 1, ..., xm sunt marginile rămase ale graficului G (notați că n ≥ 2, m ³ n). Numărul ultimelor margini m - (n - 1) = m - n + 1 și coincide cu numărul ciclomatic al graficului conectat. Adăugarea oricărei margini xi (i = n, ..., m). la arborele T, obținem un subgraf al lui G, din care derivăm un ciclu simplu mi- (n-1). trecând prin marginea xi. Acționând în acest fel, găsim un set de cicluri simple 1. mm-n + 1>. pentru că în fiecare dintre ciclurile acestui sistem există o margine care nu este cuprinsă în alte cicluri, atunci sistemul rezultat este independent, prin urmare este o bază ciclică a graficului G.
Folosind acest algoritm, definim baza ciclică a multigrafului prezentat în figură:
Să calculăm numărul ciclomatic: n = 4, m = 8, p = 1, prin urmare, n (G) = 8 - 4 + 1 = 5. Prin urmare, baza ciclică conține 5 cicluri independente. Construim un copac spanning:
Adăugăm o margine eliminată din grafic și vom obține astfel cicluri simple:
Am obținut cinci cicluri, care constituie baza ciclică a graficului.
Articole similare
Trimiteți-le prietenilor: