Astfel, matricea incidenței pentru graficul de sarcini orientat are forma:
Ordonarea vârfurilor de graf. Algoritmul lui Falkerson
Renumerotarea noduri și arce, exact ca configurațiile lor, nu schimbă esența fenomenelor naturale și a proceselor care descriu graficele. În această lucrare - procesul de producție a produselor lactate. Această proprietate a grafurilor se numește izomorfism. Soluția problemelor care implică grafice este simplificată dacă vârfurile și arcele grafurilor sunt aranjate într-o anumită ordine.
Se crede că o pereche de vârfuri digraph vertex i este precedente, iar nodurile j - urmate, dacă există o cale de la i la j, iar calea de la i la j nu există.
Prin ordonarea vârfurilor unui digraph se înțelege numerotarea vârfurilor sale, sub care:
vârfurile primului grup nu au precedente, iar nodurile ultimului grup sunt cele succesive;
vârfurile oricărui alt grup nu au precedente, iar nodurile ultimului grup sunt ulterioare;
vârfurile acelorași grupuri nu sunt alăturate de arce.
După ordonarea nodurilor, obținem un graf izomorf al graficului inițial.
Ordonarea cifrelor digraph poate fi efectuată în urma algoritmului Falkerson, care include următoarele etape:
1. Gasiti nodurile graficei in care nu intri arce. Acesta este primul nivel al nodurilor. După numerotare, aceștia, împreună cu arcurile care le aparțin, sunt îndepărtate din punct de vedere mental din grafic.
2. În graficul rămas, ca și în graficul inițial, se găsesc vârfuri în care nu intră arce. Aceste noduri într-o ordine arbitrară sunt numerotate de numere naturale după numerele nodurilor primului nivel. Acestea sunt vârfurile celui de-al doilea nivel.
Selectarea nivelurilor și numerotarea continuă până la ultimul vârf.
Ordonăm numerotarea vârfurilor graficului urmând acest algoritm:
Figura 4.6 - Graficul izomorf
Într-un nod de referință al graficului (fig. 4.2) nu include arc audio și arc localizat (1,3), (1,4). Se atribuie nodului 1 numărul 1, reprezentăm acest nod din Fig. 4.6 împreună cu arcurile care ies din el și elimină mental acest vârf din graficul original.
Printre nodurile rămase ale graficului, nodul 2 nu include acum niciun arc. Atribuiți, respectiv, numărul nodului 2 și prezentați-o în Figura 4.6. Ștergeți din punct de vedere minuțios acest vârf împreună cu arcurile care se întâmplă în acest grafic.
Acum, nodul 3 nu include nici un arc. Am atribuit acest număr 3 acestui vertex și îl transferăm în Fig. 4.6 și ștergeți mental din grafic.
Apoi vedem că nodul 4 nu include nici un arc. Alocați-i numărul 4 și transferați-l într-un desen nou, îndepărtându-l mental din graficul original.
După operație, nodul 5 a rămas fără arce. Alocați-i numărul 5 și transferați-l într-un desen nou, îndepărtându-l mental din graficul original.
Printre nodurile rămase ale graficului, nodul 6 nu include acum niciun arc. Atribuiți numărul nodului 6, respectiv, și prezentați-o în Figura 4.6. Ștergeți din punct de vedere minuțios acest vârf împreună cu arcurile care se întâmplă în acest grafic.
Acum, nodul 7 nu include nici un arc. Atribuiți acest număr la vârful numărului 7. Transferăm-o în Fig. 4.6 și ștergeți mental din grafic.
Nu era decât un singur nod 8, fără intrarea și ieșirea arcurilor. Atribuiți acest număr de nod 8 și este reprezentat în Fig. 4.6.
Astfel, vom obține un nou grafic comandat (fig. 4.6) este izomorf graficul inițial (fig. 4.2).
Putere maximă.
Algoritmul pentru determinarea debitului maxim:
1. Debitul inițial este construit
Se găsesc subseturile A ale vârfurilor care pot fi obținute de la sursa I de-a lungul marginilor nesaturate. Dacă, în acest caz, chiuveta S nu intră în subsetul A, atunci fluxul construit este maxim și problema este rezolvată. Dacă, totuși, chiuveta S intră în subsetul A, treceți la următoarea etapă a algoritmului.
Articole similare
Trimiteți-le prietenilor: