Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. |
Розбиття графа на підграфи (англ. Graph partition) (іноді в літературі також вживається термін розрізання графа) — подання вихідного графа у вигляді множини підмножин вершин за певними правилами. Зазвичай за умовою задачі потрібно, щоб , тобто всі вершини вихідного графа повинні бути розподілені на підмножини, причому . , понад 15-20 отриманих оптимальних розбиттів як правило неможливо за прийнятний час (іноді для цього використовується метод гілок і меж), тому на практиці обмежуються субоптимальними розв'язками, отриманими з використанням евристичних алгоритмів.
Необхідність отримання розбиття виникає при вирішенні ряду завдань:
- Задача розфарбовування графа — кожна множина вершин складається з вершин одного кольору, причому вершини одного кольору не мають спільних інцидентних ребер. Зазвичай цікавить відшукання мінімальної розмальовки, що в загальному випадку є завданням класу NP (критерій оптимальності— ).
- Завдання визначення числа і складу компонента зв'язності графа.
- Під час проєктування топології локальної мережі її розбиття на широкомовні домени визначається вимогами продуктивності (критерій оптимальності — обсяг переданого міждоменного трафіку при використанні різних серверів і мережевих служб (доступ до файлових серверів, служб DHCP, WINS, DNS і т. Д.), Обмеження — число портів і пропускна здатність комутаторів, маршрутизаторів і каналів зв'язку, а також вартість).
- У задачі трасування з'єднань друкованих плат або мікросхем необхідно розбиття вихідної схеми на шари (кожен з яких є планарним графом). Критерії оптимальності — мінімальне число шарів і з'єднань (фактично, собівартість виробництва), обмеження — габаритні розміри і вимоги термічної і електромагнітної сумісності електронних компонентів.
- У задачі розбиття граф-схеми алгоритму на блоки з метою реалізації на багатопроцесорній системі або логічному мультиконтроллером. Критерії оптимальності — мінімальне число блоків, мінімальні ступені дублювання сигналів мікрооперацій і логічних умов, мінімальне число міжмодульних передач управління, мінімальний трафік міжмодульних передач управління і даних; обмеження диктуються використовуваною елементною базою.
- Подання графа у вигляді ярусно-паралельної форми або граф-схеми алгоритму у вигляді безлічі перетинів (безлічі вершин у складі перетинів можуть бути неортогональної).
- Розбиття графа алгоритму на непересічні підграфи з подальшим їх розміщенням в процесорних елементах або елементах в складі ПЛІС при реалізації конвеєрної обробки даних (балансування навантаження).
Методи розбиття графа
- Покоординатне розбиття
- Рекурсивний інерційний метод поділу навпіл
- Розподіл мережі з використанням кривих Пеано
- Розподіл з урахуванням зв'язності (по суті, пошук в ширину)
- [en]
Примітки
- Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985. 352 с.
- Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.
- Баранов С. И., Журавина Л. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81.
- Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с.
- Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управлени при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с.
- Ватутин Э.
- Каляев И. А., Левин И. И., Семерников Е. А., Шмойлов В. И. Реконфигурируемые мультиконвейерные вычислительные структуры: 2-е издание. Ростов н/Д: изд-во ЮНЦ РАН, 2009. 344 с.
- Каляев И. А., Левин И. И. Реконфигурируемые мультиконвейерные вычислительные системы для решения потоковых задач обработки информации и управления // Пленарные доклады 5-й международной конференции «Параллельные вычисления и задачи управления» (PACO'10). М.: ИПУ РАН, 2010 г. С. 23—37.
- INTUIT.ru: Курс: Теория и практика ..: Лекция № 10: Параллельные методы на графах[недоступне посилання з квітня 2019]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya mistit pravopisni leksichni gramatichni stilistichni abo inshi movni pomilki yaki treba vipraviti Vi mozhete dopomogti vdoskonaliti cyu stattyu pogodivshi yiyi iz chinnimi movnimi standartami Rozbittya grafa na pidgrafi angl Graph partition inodi v literaturi takozh vzhivayetsya termin rozrizannya grafa podannya vihidnogo grafa G A V displaystyle G left langle A V right rangle u viglyadi mnozhini pidmnozhin vershin Sep A A1 A2 An Ai V displaystyle mathrm Sep A left A 1 A 2 A n right A i subseteq V za pevnimi pravilami Zazvichaj za umovoyu zadachi potribno shob i 1nAi A displaystyle bigcup i 1 n A i A tobto vsi vershini vihidnogo grafa povinni buti rozpodileni na pidmnozhini prichomu Ai displaystyle A i neq varnothing i j Ai Aj displaystyle forall i neq j A i cap A j varnothing N A displaystyle N left A right ponad 15 20 otrimanih optimalnih rozbittiv yak pravilo nemozhlivo za prijnyatnij chas inodi dlya cogo vikoristovuyetsya metod gilok i mezh tomu na praktici obmezhuyutsya suboptimalnimi rozv yazkami otrimanimi z vikoristannyam evristichnih algoritmiv Neobhidnist otrimannya rozbittya vinikaye pri virishenni ryadu zavdan Zadacha rozfarbovuvannya grafa kozhna mnozhina vershin Vi displaystyle V i skladayetsya z vershin odnogo koloru prichomu vershini odnogo koloru ne mayut spilnih incidentnih reber Zazvichaj cikavit vidshukannya minimalnoyi rozmalovki sho v zagalnomu vipadku ye zavdannyam klasu NP kriterij optimalnosti n min displaystyle n rightarrow min Zavdannya viznachennya chisla i skladu komponenta zv yaznosti grafa Pid chas proyektuvannya topologiyi lokalnoyi merezhi yiyi rozbittya na shirokomovni domeni viznachayetsya vimogami produktivnosti kriterij optimalnosti obsyag peredanogo mizhdomennogo trafiku pri vikoristanni riznih serveriv i merezhevih sluzhb dostup do fajlovih serveriv sluzhb DHCP WINS DNS i t D Obmezhennya chislo portiv i propuskna zdatnist komutatoriv marshrutizatoriv i kanaliv zv yazku a takozh vartist U zadachi trasuvannya z yednan drukovanih plat abo mikroshem neobhidno rozbittya vihidnoyi shemi na shari kozhen z yakih ye planarnim grafom Kriteriyi optimalnosti minimalne chislo shariv i z yednan faktichno sobivartist virobnictva obmezhennya gabaritni rozmiri i vimogi termichnoyi i elektromagnitnoyi sumisnosti elektronnih komponentiv U zadachi rozbittya graf shemi algoritmu na bloki z metoyu realizaciyi na bagatoprocesornij sistemi abo logichnomu multikontrollerom Kriteriyi optimalnosti minimalne chislo blokiv minimalni stupeni dublyuvannya signaliv mikrooperacij i logichnih umov minimalne chislo mizhmodulnih peredach upravlinnya minimalnij trafik mizhmodulnih peredach upravlinnya i danih obmezhennya diktuyutsya vikoristovuvanoyu elementnoyu bazoyu Podannya grafa u viglyadi yarusno paralelnoyi formi abo graf shemi algoritmu u viglyadi bezlichi peretiniv bezlichi vershin u skladi peretiniv mozhut buti neortogonalnoyi Rozbittya grafa algoritmu na neperesichni pidgrafi z podalshim yih rozmishennyam v procesornih elementah abo elementah v skladi PLIS pri realizaciyi konveyernoyi obrobki danih balansuvannya navantazhennya Metodi rozbittya grafaPokoordinatne rozbittya Rekursivnij inercijnij metod podilu navpil Rozpodil merezhi z vikoristannyam krivih Peano Rozpodil z urahuvannyam zv yaznosti po suti poshuk v shirinu en PrimitkiEvstigneev V A Primenenie teorii grafov v programmirovanii M Nauka 1985 352 s Kurejchik V M Glushan V M Sherbakov L I Kombinatornye apparatnye modeli i algoritmy v SAPR M Radio i svyaz 1990 216 s Baranov S I Zhuravina L N Peschanskij V A Metod predstavleniya parallelnyh graf shem algoritmov sovokupnostyami posledovatelnyh graf shem Avtomatika i vychislitelnaya tehnika 1984 5 S 74 81 Zotov I V Titov V S Koloskov V A i dr Organizaciya i sintez mikroprogrammnyh multimikrokontrollerov Kursk izd vo Kursk 1999 368 s Vatutin E I Zotov I V Titov V S i dr Kombinatorno logicheskie zadachi sinteza razbienij parallelnyh algoritmov logicheskogo upravleni pri proektirovanii logicheskih multikontrollerov Kursk izd vo KurskGTU 2010 200 s Vatutin E Kalyaev I A Levin I I Semernikov E A Shmojlov V I Rekonfiguriruemye multikonvejernye vychislitelnye struktury 2 e izdanie Rostov n D izd vo YuNC RAN 2009 344 s Kalyaev I A Levin I I Rekonfiguriruemye multikonvejernye vychislitelnye sistemy dlya resheniya potokovyh zadach obrabotki informacii i upravleniya Plenarnye doklady 5 j mezhdunarodnoj konferencii Parallelnye vychisleniya i zadachi upravleniya PACO 10 M IPU RAN 2010 g S 23 37 INTUIT ru Kurs Teoriya i praktika Lekciya 10 Parallelnye metody na grafah nedostupne posilannya z kvitnya 2019