Oszd meg egy grafikont

A = \ bal \, A_. A_ \ right \>, A_ \ subseteq V> bizonyos szabályok szerint. Általában a probléma állapota miatt szükséges, hogy ⋃ i = 1 n A i = A ^ A_ = A>. azaz az eredeti gráf összes csúcsait fel kell osztani a részhalmazokra, és A i ≠ ∅ \ neq \ varnothing>. Rendszerint a partíció ortogonalitási állapotát is bevezetjük: ∀i ≠ j A i ∩ A j = ∅

A_ \ cap A _ = \ varnothing>. azaz ugyanaz a csúcs nem lehet a különböző alcsoportok részei. Néha a különféle rekeszeket kell választania, amelyik megfelel a megszorítások és az optimális (vagy szuboptimális) a meghatározott kritériumok, illetve annak bizonyítására, hogy a kívánt partíció nem létezik (korlátozások inkonzisztens). A gráf felosztásának problémája az NP-complete osztályhoz tartozik. A partíciók számának felső becslését a Bell szám határozza meg. Általában azonban nem minden lehetséges partíció helyes (nem sértik a korlátozásokat), vagyis a becslés túlbecsült. A gráf csúcsainak értékeihez N = | A | 15-20 megszerzése optimális partíciók általában lehetetlen ésszerű időn (néha használják ezt a módszert ágak és határok), így, a gyakorlatban, korlátozva szuboptimális megoldások alkalmazásával kapott heurisztikus algoritmusok.

A particionálás megszerzésének szükségessége számos probléma megoldásakor jelentkezik:

1. A grafikon színezésének problémája - minden csúcs V i> csúcsok azonos színű csúcsokból állnak, és az azonos színű csúcsok nem tartalmaznak gyakori incidens éleket. Általában a minimális színezésre való keresés érdekes, ami általában az NP osztály problémája (az optimális kritérium n → min).
2. A grafikon csatlakoztatott összetevőinek számát és összetételét meghatározó probléma.
3. Tervezésekor hálózati topológia, annak felosztását szórási tartományok által meghatározott teljesítmény követelmények (optimum kritérium - az összeg át inter-domain forgalom segítségével a különböző szerverek és hálózati szolgáltatásokat (iratbetekintési szerverek DHCP szolgáltatás WINS DNS, stb), a korlátozások -..... száma portok és átkapcsolók, routerek és kommunikációs csatornák, valamint a költségek).
4. A nyomtatott áramköri kártyák vagy mikroáramkörök összekapcsolásának lebonyolításakor az eredeti áramkört rétegekre kell osztani (amelyek mindegyike síkbeli grafikon). Az optimalitás kritériumai - a rétegek és összekapcsolások minimális száma (valójában a termelési költség), a korlátozások - az elektronikai alkatrészek hőméretének és elektromágneses összeférhetőségének általános méretei és követelményei. [2]
5. Az algoritmus grafikon-sémájának blokkolására többprocesszoros rendszeren vagy logikai multicontrolleren való végrehajtás céljából. Az optimális kritériumok - az egységek minimális száma, a mikroprocesszorok és a logikai feltételek minimális mértéke, az intermodális vezérlés minimális száma, az intermodulus vezérlés minimális forgalma és az adatátvitel; A korlátozásokat az alkalmazott elemalap határozza meg. [3] [4] [5] [6]
6. A grafikon ábrázolása párhuzamos formában vagy az algoritmus grafikon-sémája formájában szakaszok formájában (a szakaszok összetételében lévő csúcsok nem merőlegesek lehetnek).
7. A bomlás a gráf diszjunkt részgráfok algoritmust későbbi elhelyezését a processzor elem vagy elemek a készítményben, amikor a FPGA végrehajtására adatok továbbítására (terheléskiegyenlítés). [7] [8]

Grafikon partícionálásának módszerei [9]

• Egy koordinálatlan bomlás
• A felosztás rekurzív inerciális módszere
• A hálózat felosztása Peano görbék segítségével
• Divízió a csatlakoztathatóság tekintetében (valójában szélességű keresés)
• A Kernigan-Lina algoritmus

Kapcsolódó cikkek