Opdeling af en graf

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. marts 2017; checks kræver 3 redigeringer .

At opdele en graf i undergrafer ( eng. Graph partition ) (nogle gange bruges udtrykket cutting of a graph også i litteraturen [1] ) er en repræsentation af den originale graf som et sæt af undergrupper af toppunkter i henhold til visse regler. Normalt kræves det i henhold til problemets tilstand, at , det vil sige, at alle hjørner af den originale graf skal fordeles mellem delmængder, og . Normalt er kravet om partitionsortogonalitet også introduceret : , det vil sige, at det samme toppunkt ikke kan være en del af forskellige delmængder . Nogle gange, fra sættet af mulige partitioner, er det nødvendigt at vælge en, der opfylder begrænsningerne og er optimal (eller suboptimal) i henhold til det angivne kriterium, eller at bevise, at den påkrævede partition ikke eksisterer (begrænsningerne er inkonsekvente). Opgaven med at partitionere en graf tilhører klassen af NP-complete , det øverste estimat af antallet af partitioner bestemmes af Bell-nummeret , men normalt er ikke alle mulige partitioner korrekte (overtræder ikke begrænsninger), dvs. skøn er overvurderet. Når antallet af grafens hjørnepunkter er mere end 15-20, er det normalt umuligt at opnå optimale partitioner inden for en acceptabel tid (nogle gange bruges gren- og bundmetoden til dette ), og derfor er de i praksis begrænset til suboptimale løsninger opnået ved brug af heuristisk algoritmer . $G=\venstre\langle A,V\højre\range$ $\mathrm {sep} ~A=\left\{A_{1},A_{2},...,A_{n}\right\},A_{i}\subseteq A$ $\bigcup _{i=1}^{n}A_{i}=A$ $A_{i}\neq \varnothing$ $\forall i\neq j~A_{i}\cap A_{j}=\varnothing$ $N=\left|A\right|$

Behovet for at få en partition opstår, når du løser en række problemer:

Graffarveproblem — hvert sæt af hjørner består af hjørner af samme farve , og hjørner af samme farve har ikke fælles indfaldende kanter. Normalt er man interesseret i at finde minimumsfarvningen, som i det generelle tilfælde er et NP -klasseproblem (optimitetskriteriet er ). $V_i$ $n\rightarrow \min$
Problemet med at bestemme antallet og sammensætningen af de forbundne komponenter i en graf .
Når topologien af et lokalt netværk designes, bestemmes dets opdeling i broadcast-domæner af ydeevnekrav (optimitetskriteriet er mængden af interdomænetrafik, der transmitteres ved brug af forskellige servere og netværkstjenester (adgang til filservere , DHCP , WINS , DNS osv. .), restriktioner - antallet af porte og båndbredde for switches , routere og kommunikationskanaler samt omkostninger).
I problemet med at spore sammenkoblingerne af trykte kredsløb eller mikrokredsløb er det nødvendigt at opdele det originale kredsløb i lag (som hver er en plan graf ). Optimalitetskriterier - minimumsantallet af lag og sammenkoblinger (faktisk produktionsomkostninger), begrænsninger - overordnede dimensioner og krav til termisk og elektromagnetisk kompatibilitet af elektroniske komponenter. [2]
I opgaven med at opdele grafdiagrammet for en algoritme i blokke med henblik på implementering på et multiprocessorsystem eller en logisk multicontroller . Optimalitetskriterier er minimumsantallet af blokke, minimumsgraden af duplikering af mikrooperationssignaler og logiske forhold, minimumsantallet af inter-modul kontroloverførsler, minimum trafik af inter-modul kontrol og dataoverførsler; restriktioner er dikteret af den anvendte elementbase. [3] [4] [5] [6]
Repræsentation af en graf i form af en tiered-parallel form eller et grafskema af en algoritme i form af et sæt sektioner (sæt af hjørner i sektionerne kan være ikke-ortogonale).
Opdeling af algoritmegrafen i ikke-skærende undergrafer med deres efterfølgende placering i processorelementer eller elementer i FPGA'en ved implementering af datapipelinebehandling (belastningsbalancering). [7] [8]

Grafpartitioneringsmetoder [9]

Koordiner opdeling
Rekursiv inertihalveringsmetode
Netværksopdeling ved hjælp af Peano-kurver
Opdeling med hensyn til tilslutning (i det væsentlige, bredde-først søgning )
Kernigans

Se også

Gerasim@Home

Noter

↑ Evstigneev V. A. Anvendelse af grafteori i programmering. M.: Nauka, 1985. 352 s.
↑ Kureichik V. M., Glushan V. M., Shcherbakov L. I. Kombinatoriske hardwaremodeller og algoritmer i CAD. Moskva: Radio og kommunikation, 1990. 216 s.
↑ Baranov S. I., Zhuravina L. N., Peschansky V. A. En metode til at repræsentere parallelle grafskemaer af algoritmer ved hjælp af sæt af sekventielle grafskemaer // Automation and Computer Science. 1984. nr. 5. S. 74-81.
↑ Zotov I. V., Titov V. S., Koloskov V. A. [et al.] Organisering og syntese af mikroprogram multimikrocontrollere. Kursk: forlaget "Kursk", 1999. 368 s. ISBN 5-7277-0253-4
↑ Vatutin E. I., Zotov I. V., Titov V. S. [et al.] Kombinatorisk-logiske problemer med at syntetisere partitioner af parallelle logiske kontrolalgoritmer i designet af logiske multicontrollere. Kursk, forlag af Kursk State Technical University, 2010. 200 s. ISBN 978-5-7681-0523-5
↑ Vatutin E.I. Design af logiske multicontrollere. Syntese af partitioner af parallelle grafskemaer af algoritmer. Saarbrucken : Lambert Academic Publishing , 2011. 292 pp. ISBN 978-3-8433-1728-3
↑ Kalyaev I. A., Levin I. I., Semernikov E. A., Shmoylov V. I. Rekonfigurerbare multi-pipeline computing-strukturer: 2. udgave. Rostov n/a: YuNTs RAN, 2009. 344 s. ISBN 978-5-902982-61-6
↑ Kalyaev I. A., Levin I. I. Rekonfigurerbare multi-pipeline computersystemer til løsning af flowproblemer med informationsbehandling og kontrol // Plenarrapporter fra den 5. internationale konference "Parallel Computing and Control Problemer" (PACO'10). M.: IPU RAN, 2010, s. 23-37.
↑ INTUIT.ru: Kursus: Teori og praksis ..: Forelæsning nr. 10: Parallelle metoder på grafer (utilgængeligt link)