Dela en graf

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 mars 2017; kontroller kräver 3 redigeringar .

Att dela upp en graf i subgrafer ( eng. Graph partition ) (ibland används termen cutting of a graph också i litteraturen [1] ) är en representation av den ursprungliga grafen som en uppsättning delmängder av hörn enligt vissa regler. Vanligtvis, beroende på problemets tillstånd, krävs det att , det vill säga alla hörn i den ursprungliga grafen måste fördelas mellan delmängder och . Vanligtvis introduceras dessutom kravet på partitionsortogonalitet : $G=\vänster\langle A,V\höger\rangle$ $\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$ , det vill säga samma vertex kan inte vara en del av olika delmängder. Ibland, från uppsättningen av möjliga partitioner, krävs det att man väljer en som uppfyller begränsningarna och är optimal (eller suboptimal) enligt det angivna kriteriet, eller att bevisa att den nödvändiga partitionen inte existerar (restriktionerna är inkonsekventa). Uppgiften att partitionera en graf tillhör klassen NP-complete , den övre uppskattningen av antalet partitioner bestäms av Bell-numret , men vanligtvis är inte alla möjliga partitioner korrekta (bryt inte mot begränsningar), det vill säga uppskattningen är överskattad. När antalet grafhörn är mer än 15–20 är det vanligtvis omöjligt att få optimala partitioner inom en acceptabel tid (ibland används gren- och bunden-metoden för detta ), därför är de i praktiken begränsade till suboptimala lösningar som erhålls med hjälp av heuristiska algoritmer . $N=\left|A\right|$

Behovet av att skaffa en partition uppstår när man löser ett antal problem:

Graffärgningsproblem — varje uppsättning hörn består av hörn av samma färg , och hörn av samma färg har inte gemensamma infallande kanter. Vanligtvis är man intresserad av att hitta den lägsta färgen, som i det allmänna fallet är ett NP -klassproblem (optimitetskriteriet är ). $V_i$ $n\rightarrow \min$
Problemet med att bestämma antalet och sammansättningen av de sammankopplade komponenterna i en graf .
Vid design av topologin för ett lokalt nätverk bestäms dess uppdelning i sändningsdomäner av prestandakrav (optimalitetskriteriet är mängden interdomäntrafik som överförs vid användning av olika servrar och nätverkstjänster (åtkomst till filservrar , DHCP , WINS , DNS , etc.) .), restriktioner - antalet portar och bandbredd för switchar , routrar och kommunikationskanaler, samt kostnad).
I problemet med att spåra sammankopplingarna av tryckta kretskort eller mikrokretsar är det nödvändigt att dela upp den ursprungliga kretsen i lager (som vart och ett är en plan graf ). Optimalitetskriterier - det minsta antalet lager och sammankopplingar (i själva verket produktionskostnaden), begränsningar - övergripande dimensioner och krav på termisk och elektromagnetisk kompatibilitet för elektroniska komponenter. [2]
I uppgiften att dela upp grafdiagrammet för en algoritm i block för implementering på ett multiprocessorsystem eller en logisk multicontroller . Optimalitetskriterier är det minsta antalet block, den minsta graden av duplicering av mikrooperationssignaler och logiska förhållanden, det minsta antalet styröverföringar mellan moduler, minsta trafik för styrning mellan moduler och dataöverföringar; begränsningar dikteras av elementbasen som används. [3] [4] [5] [6]
Representation av en graf i form av en tiered-parallell form eller ett grafschema för en algoritm i form av en uppsättning sektioner (uppsättningar av hörn i sektionerna kan vara icke-ortogonala).
Dela upp algoritmgrafen i icke-korsande subgrafer med deras efterföljande placering i processorelement eller element i FPGA vid implementering av datapipelinebearbetning (lastbalansering). [7] [8]

Grafpartitioneringsmetoder [9]

Koordinera partitionering
Rekursiv tröghetsbisektionsmetod
Nätverksuppdelning med Peano-kurvor
Uppdelning med avseende på anslutning (i huvudsak, bredd-först sökning )
Kernigans

Se även

Gerasim@Home

Anteckningar

↑ Evstigneev V. A. Tillämpning av grafteori i programmering. M.: Nauka, 1985. 352 sid.
↑ Kureichik V. M., Glushan V. M., Shcherbakov L. I. Kombinatoriska hårdvarumodeller och algoritmer i CAD. Moskva: Radio och kommunikation, 1990. 216 sid.
↑ Baranov S. I., Zhuravina L. N., Peschansky V. A. En metod för att representera parallella grafscheman av algoritmer genom uppsättningar av sekventiella grafscheman // Automation and Computer Science. 1984. Nr 5. S. 74-81.
↑ Zotov I. V., Titov V. S., Koloskov V. A. [et al.] Organisation och syntes av mikroprograms multimikrokontroller. Kursk: förlag "Kursk", 1999. 368 s. ISBN 5-7277-0253-4
↑ Vatutin E. I., Zotov I. V., Titov V. S. [et al.] Kombinatoriskt-logiska problem med att syntetisera partitioner av parallella logiska styralgoritmer i designen av logiska multikontroller. Kursk, förlag vid Kursk State Technical University, 2010. 200 sid. ISBN 978-5-7681-0523-5
↑ Vatutin E.I. Design av logiska multicontrollers. Syntes av partitioner av parallella grafscheman av algoritmer. Saarbrucken : Lambert Academic Publishing , 2011. 292 s. ISBN 978-3-8433-1728-3
↑ Kalyaev I. A., Levin I. I., Semernikov E. A., Shmoylov V. I. Reconfigurable multi-pipeline computing structures: 2nd edition. Rostov n/a: YuNTs RAN, 2009. 344 sid. ISBN 978-5-902982-61-6
↑ Kalyaev I. A., Levin I. I. Omkonfigurerbara multi-pipeline beräkningssystem för att lösa flödesproblem av informationsbehandling och kontroll // Plenarrapporter från den 5:e internationella konferensen "Parallel Computing and Control Problems" (PACO'10). M.: IPU RAN, 2010, s. 23-37.
↑ INTUIT.ru: Kurs: Teori och praktik ..: Föreläsning nr 10: Parallella metoder på grafer (otillgänglig länk)