Algoritm gamma

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 19 ianuarie 2020; verificările necesită 2 modificări .

Algoritmul gamma  este un algoritm pentru așezarea unui grafic plat și verificarea planarității acestuia pe parcurs .

Definiții

Algoritm

Așezați pe plan orice ciclu H al graficului G fără repetări de vârfuri.

  1. Construiți toate segmentele S 1 ,..,S k ale graficului G din H .
  2. Dacă există un segment S i cu o singură față admisibilă  , selectați-l.
  3. Dacă toate segmentele au mai multe fețe suplimentare, selectați oricare.
  4. Selectați un lanț gamma arbitrar al segmentului și potriviți-l într-o față admisibilă.
  5. Treceți la pasul (2) adăugând un lanț gamma la graficul H.

Proprietăți ale graficelor pentru funcționarea corectă a algoritmului

  1. Graficul trebuie să fie conectat .
  2. Graficul trebuie să aibă cel puțin un ciclu .
  3. Graficul nu trebuie să aibă punți , adică margini, după eliminarea cărora, graficul se împarte în două componente conectate .

Dacă proprietatea (1) este încălcată, atunci graficul trebuie să fie stivuit separat în funcție de componentele conectate. Dacă proprietatea (2) este încălcată, atunci graficul este un arbore și este trivial să desenați aplatizarea acestuia.

Cazul de încălcare a proprietății (3) va fi analizat mai detaliat. Dacă există punți în grafic, atunci acestea trebuie tăiate, fiecare componentă conectată trebuie aplatizată separat și apoi conectată prin punți. O dificultate poate apărea aici: în timpul procesului de așezare, vârfurile de capăt ale podului pot fi în interiorul unui graf plan. Să desenăm o componentă conectată și să adăugăm altele la ea secvenţial. Fiecare componentă nouă conectată va fi desenată în fața care conține vârful de capăt al podului corespunzător. Deoarece graficul conectivității prin punți de componente conectate este un arbore, vom putea obține o ambalare plată.

Teorema

Graficul Г este plan dacă și numai dacă algoritmul gamma îl plasează pe plan.

Dovada

În sens invers, dovada este evidentă.

Să dovedim clar. Dacă graficul Γ este plan, atunci subgraful H așezat pe plan poate fi completat până la așezarea graficului Γ . În special, pentru ultimul pas, aceasta înseamnă că graficul Γ este complet așezat pe plan.

Fie graficul Γ plan. Atunci orice ciclu al graficului Γ este reprezentat ca un poligon atunci când este stivuit. Acest poligon este inclus în așezarea graficului Γ pe plan.

Fie afirmația să fie adevărată până la a n-a iterație a algoritmului.

Opțiuni:

  1. S se încadrează în singura față a graficului H , graficul H este completat până la pliul graficului G , iar în această pliu segmentul S se află în singura față. În consecință, încorporarea oricărui traseu gamma C al segmentului S în această față conduce la unirea graficului H cu C , care poate fi extinsă la placarea Г.
  2. Fiecare segment are mai multe fețe valide.

Fie S  un segment cu fețele admisibile F 1 și F 2 . Subgraful H se completează până la așezarea graficului Г prin ipoteza inductivă. În acest caz, segmentul S se încadrează într-una dintre fețele admisibile. Fără pierderea generalității, să fie această față F 1 . Să demonstrăm că există o prelungire a lui H până la așezarea graficului Г în care segmentul S se află în fața F 2 . Deoarece F 1 și F 2  sunt fețe suplimentare, ambele conțin toate vârfurile de contact ale segmentului S . Prin urmare, toate vârfurile de contact ale segmentului S se află în mulțimea vârfurilor comune F 1 și F 2 . Fie S 1 ,..,S k  toate segmentele cuprinse în F 1 . Fie S ' 1 ,.., S ' m  toate segmentele din F 2 care conţin unul dintre vârfuri. Fie segmentul S ' i să aibă un vârf de contact şi un alt vârf de contact care nu aparţine lui F 1 . Atunci feţele admisibile S ' i este faţa F 2 , iar aceasta este ipoteza punctului (2). Din contradicție rezultă că toate vârfurile de contact S ' i (în mod asemănător cu Si ) se află în mulțimea de vârfuri ale segmentelor S ' 1 ,..,S ' m .

Prin urmare, în așezarea graficului G , este posibil să se deplaseze segmentele S 1 ,.., Sk la F 2 și S ' 1 ,..,S ' m la F 1 , aceasta va duce la așezarea a graficului Г în care segmentul S se află în faţa F 2 .

Prin urmare, algoritmul va potrivi orice grafic plan pe plan. Ceea ce s-a cerut.

Vezi și

Literatură