Глобальная минимизация количества межслойных переходов
Раскрываются особенности эффективного (линейного по числу операций и требуемой памяти) алгоритма точного решения задачи расслоения совмещенной топологии проводящего рисунка с целью минимизации количества межслойных переходов для случая двух трассировочных слоев. Алгоритм используется в трассировщике...
Saved in:
| Published in: | Технология и конструирование в электронной аппаратуре |
|---|---|
| Date: | 2001 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
2001
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/70833 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Глобальная минимизация количества межслойных переходов / О.Б. Полубасов // Технология и конструирование в электронной аппаратуре. — 2001. — № 2. — С. 3-9. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860099771444756480 |
|---|---|
| author | Полубасов, О.Б. |
| author_facet | Полубасов, О.Б. |
| citation_txt | Глобальная минимизация количества межслойных переходов / О.Б. Полубасов // Технология и конструирование в электронной аппаратуре. — 2001. — № 2. — С. 3-9. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Технология и конструирование в электронной аппаратуре |
| description | Раскрываются особенности эффективного (линейного по числу операций и требуемой памяти) алгоритма точного решения задачи расслоения совмещенной топологии проводящего рисунка с целью минимизации количества межслойных переходов для случая двух трассировочных слоев. Алгоритм используется в трассировщике FreeStyleRoute.
|
| first_indexed | 2025-12-07T17:28:22Z |
| format | Article |
| fulltext |
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 2
3
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
ÃËÎÁÀËÜÍÀß ÌÈÍÈÌÈÇÀÖÈß
ÊÎËÈ×ÅÑÒÂÀ ÌÅÆÑËÎÉÍÛÕ ÏÅÐÅÕÎÄÎÂ
Î. Á. ÏÎËÓÁÀÑÎÂ
Ðîññèÿ, ã.Ñàíêò-Ïåòåðáóðã, ÃÓÏ «ÍÈÈ "Çâåçäà�»
E-mail: pbas@ spb.cityline.ru
Äàòà ïîñòóïëåíèÿ â ðåäàêöèþ
19.10 2000 ã.
Îïïîíåíò ê. ò. í. Â. Â. ÑÈÁÈÐßÊÎÂ
Èñïîëüçîâàíèå ïðåäëîæåííîé ïðîöåäó-
ðû â òîïîëîãè÷åñêîì òðàññèðîâùèêå
FreeStyleRoute ïîçâîëÿåò â 10-30 ðàç
óìåíüøèòü êîëè÷åñòâî ìåæñëîéíûõ
ïåðåõîäîâ.
Óâåëè÷åíèå êîëè÷åñòâà ýëåìåíòîâ íà ïå÷àòíîé
ïëàòå èëè êðèñòàëëå ÁÈÑ, óñëîæíåíèå ñàìèõ ýëå-
ìåíòîâ ïðèâîäÿò ê òîìó, ÷òî çàäà÷à òðàññèðîâêè
ñîåäèíåíèé ñòàíîâèòñÿ âñ¸ áîëåå òðóäíîé.
Äëÿ óâåëè÷åíèÿ ïëîòíîñòè êîìïîíîâêè ñîåäèíå-
íèé èñïîëüçóþòñÿ äâà îñíîâíûõ ñïîñîáà: óìåíüøå-
íèå øèðèíû ïðîâîäíèêîâ è çàçîðîâ ìåæäó íèìè è
óâåëè÷åíèå êîëè÷åñòâà òðàññèðîâî÷íûõ ñëîåâ. Îáà
ñïîñîáà âåäóò ê ñíèæåíèþ òåõíîëîãè÷íîñòè èçãî-
òîâëåíèÿ è ðåìîíòîïðèãîäíîñòè èçäåëèé, óâåëè÷å-
íèþ ïðîöåíòà áðàêà.
Îñîáóþ ñëîæíîñòü ïðåäñòàâëÿåò ïðîáëåìà ìè-
íèìèçàöèè êîëè÷åñòâà ìåæñëîéíûõ ïåðåõîäîâ. Íà
ïðàêòèêå îáû÷íî ïðîêëàäûâàþò ó÷àñòêè ïðîâîäíè-
êîâ ñòðîãî îðòîãîíàëüíî (âåðòèêàëüíî â îäíîì ñëîå
è ãîðèçîíòàëüíî â äðóãîì), à ëèøíèå ïåðåõîäû óäà-
ëÿþò òîëüêî ïîñëå çàâåðøåíèÿ òðàññèðîâêè. Äëÿ
ýòîãî ôðàãìåíò òðàññû ïåðåíîñÿò èç îäíîãî ñëîÿ â
äðóãîé. Âîçìîæíîñòè òàêîé ïðîöåäóðû âåñüìà îãðà-
íè÷åíû, ò. ê. ïîëó÷àåìîå êîëè÷åñòâî ïåðåõîäîâ â
äåñÿòêè ðàç áîëüøå íåîáõîäèìîãî.
Äëÿ ðåøåíèÿ óêàçàííîé çàäà÷è ïðåäëàãàëèñü ñëå-
äóþùèå ìåòîäû:
�Ìèíèìèçàöèÿ ÷èñëà ñëîåâ [1, c. 231] íà îñíîâå
ðàñêðàñêè ãðàôà ïåðåñå÷åíèé. Çàäà÷à NP-òðóäíà, êðî-
ìå òîãî, õðîìàòè÷åñêîå ÷èñëî ãðàôà ïåðåñå÷åíèé ìî-
æåò îêàçàòüñÿ áîëüøå çàäàííîãî ÷èñëà ñëîåâ.
�Ïîñëåäîâàòåëüíîå âûäåëåíèå â ãðàôå ïåðåñå-
÷åíèé ìàêñèìàëüíûõ ïëîñêèõ ñóãðàôîâ [2, ñ. 226].
Íåäîñòàòêè òå æå. Ïðè ýòîì âîçìîæíî âîçíèêíîâå-
íèå ïîãðåøíîñòè çà ñ÷åò èñïîëüçîâàíèÿ �æàäíîãî
àëãîðèòìà�. Ìîæíî îòìåòèòü, ÷òî íàõîæäåíèå ìàê-
ñèìàëüíîãî ïëîñêîãî ñóãðàôà � çàäà÷à íå ïðîùå
ïåðâîé.
�Íàõîæäåíèå êëèêîâîãî ïîêðûòèÿ ãðàôà ïåðå-
ñå÷åíèé, â êîòîðîì âåðøèíû, ñîîòâåòñòâóþùèå íåïå-
ðåñåêàþùèìñÿ îòðåçêàì, ñîåäèíåíû ðåáðîì [3, ñ. 64�
69]. Çàäà÷à î ïîêðûòèè NP-òðóäíà, ïðè ýòîì âõîä-
íàÿ öåïî÷êà � ÷èñëî êëèê ãðàôà (â õóäøåì ñëó÷àå
� 3n/3).
Ñëîæíîñòü ïðàêòè÷åñêîé ðåàëèçóåìîñòè óêàçàí-
íûõ ìåòîäîâ ñâèäåòåëüñòâóåò îá àêòóàëüíîñòè ðàç-
ðàáîòêè ýôôåêòèâíûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷è
ìèíèìèçàöèè êîëè÷åñòâà ìåæñëîéíûõ ïåðåõîäîâ.
Îäèí èç âîçìîæíûõ ïîäõîäîâ ðàññìîòðåí íèæå.
1. Çàäà÷à ðàññëîåíèÿ ñîâìåùåííîé òîïîëîãèè è
ãðàô äîìåíîâ
Ïðè ïðîåêòèðîâàíèè ìíîãîñëîéíûõ ïå÷àòíûõ ïëàò
ñî ñêâîçíûìè ìåòàëëèçèðîâàííûìè îòâåðñòèÿìè â
íåêîòîðûõ ìåòîäàõ òðàññèðîâêè ïðåäâàðèòåëüíî ïðî-
êëàäûâàþò òðàññû â îäíîé ïëîñêîñòè. Ïðè ýòîì ðàç-
ðåøåíî ïåðåñå÷åíèå òðàññ, íî íå áîëåå äâóõ â êàæ-
äîé òî÷êå ïåðåñå÷åíèÿ. Ïîëó÷åííûé ðåçóëüòàò íà-
çûâàåòñÿ ñîâìåùåííîé òîïîëîãèåé òðàññ. Çàòåì íå-
îáõîäèìî ðàñïðåäåëèòü ôðàãìåíòû òðàññ ïî èìåþ-
ùèìñÿ ñëîÿì òàêèì îáðàçîì, ÷òîáû òðàññû íà îäíîì
ñëîå íå ïåðåñåêàëèñü è êîëè÷åñòâî ïåðåõîäîâ ñî
ñëîÿ íà ñëîé áûëî ìèíèìàëüíûì.
Åñëè äëÿ òðàññèðîâêè äîñòóïíî òîëüêî äâà êîì-
ìóòàöèîííûõ ñëîÿ, çàäà÷à ìèíèìèçàöèè êîëè÷åñòâà
ïåðåõîäîâ ïðè ðàññëîåíèè ìîæåò áûòü òî÷íî ðåøå-
íà íåïåðåáîðíûì àëãîðèòìîì.
Îïðåäåëåíèå 1. Íàçîâåì òî÷êè ïåðåñå÷åíèÿ
òðàññ äîìåíàìè. Íàçâàíèå ñâÿçàíî ñ òåì, ÷òî â
êàæäîé òàêîé òî÷êå ïåðåñåêàþòñÿ ðîâíî äâå òðàññû,
ïðè÷åì âîçìîæíû òîëüêî äâà âàðèàíòà: ëèáî îäíà
òðàññà ïðîõîäèò ÷åðåç òî÷êó ïåðåñå÷åíèÿ â ïåðâîì
ñëîå, à äðóãàÿ � âî âòîðîì, ëèáî íàîáîðîò. Ýòè äâà
âàðèàíòà ìîæíî ñîîòíåñòè ñ äâóìÿ âîçìîæíûìè îðè-
åíòàöèÿìè äîìåíà.
Ïðîèçâîëüíî âûáðàâ îðèåíòàöèþ äëÿ êàæäîãî
äîìåíà, íàçîâåì åå èñõîäíîé.
Íà ðèñ. 1 ÷åðíûå êðóæêè èçîáðàæàþò êîíòàêò-
íûå ïëîùàäêè (äîñòóïíûå íà îáîèõ ñëîÿõ), òî÷êè
Ðèñ. 1. Ñîâìåùåííàÿ òîïîëîãèÿ ïðîâîäíèêîâ
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 2
4
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
ïåðåñå÷åíèÿ òðàññ � äîìåíû � îáâåäåíû ñêðóãëåí-
íûìè êâàäðàòàìè. Òàê êàê â ýòîì ïðèìåðå îòðåçêè
òðàññ ïðîëîæåíû ëèøü â äâóõ íàïðàâëåíèÿõ, ïðèìåì,
÷òî â èñõîäíîé îðèåíòàöèè âåðòèêàëüíûå îòðåçêè
ïðîõîäÿò ÷åðåç òî÷êè ïåðåñå÷åíèÿ â ïåðâîì ñëîå
(æèðíûå ëèíèè), à ãîðèçîíòàëüíûå � âî âòîðîì
(òîíêèå ïóíêòèðíûå ëèíèè).
Ðàññìîòðèì ó÷àñòîê òðàññû ìåæäó äâóìÿ ñîñåä-
íèìè òî÷êàìè ïåðåñå÷åíèÿ. Åñëè åãî êîíöû ïðèíàä-
ëåæàò ðàçíûì ñëîÿì, íà ó÷àñòêå íåîáõîäèì ïåðåõîä
ñ îäíîãî ñëîÿ íà äðóãîé (íà ðèñóíêå ïåðåõîäû èçîá-
ðàæåíû ìàëåíüêèìè ñâåòëûìè êðóæêàìè, èõ 10), èíà÷å
ïåðåõîä íà ó÷àñòêå íå íóæåí. Ñîåäèíèâ íà ãðàôå
äîìåíîâ (ðèñ. 2) ñîîòâåòñòâóþùèå äîìåíû ðåáðîì,
ïðèïèøåì ðåáðó âåñ +1, åñëè íà ó÷àñòêå íåò ïåðåõî-
äà, è �1, åñëè ïåðåõîä åñòü. Ïîëîæèòåëüíûå è îòðè-
öàòåëüíûå ðåáðà èçîáðàæåíû íà ðèñ. 2 òîíêèìè è
æèðíûìè ëèíèÿìè, ñîîòâåòñòâåííî.
Ïðè îïòèìàëüíîì ðàññëîåíèè îäíè äîìåíû ñîõðà-
íÿò èñõîäíóþ îðèåíòàöèþ, äðóãèå � èçìåíÿò åå íà
ïðîòèâîïîëîæíóþ. Ñëåäóåò îòìåòèòü, ÷òî ïðè èçìå-
íåíèè îðèåíòàöèè äîìåíà ìû äîëæíû òàêæå èçìåíèòü
çíàêè âåñîâ èíöèäåíòíûõ äîìåíó ðåáåð (ðèñ. 3).
Òàê êàê ïðè êàæäîì êîíêðåòíîì ðàññëîåíèè ñóì-
ìàðíûé âåñ îòðèöàòåëüíûõ ðåáåð ñîîòâåòñòâóåò (ïî
àáñîëþòíîé âåëè÷èíå) êîëè÷åñòâó ïåðåõîäîâ, òî îï-
ðåäåëåíèå îïòèìàëüíîãî ðàññëîåíèÿ ñâîäèòñÿ ê âû-
ÿâëåíèþ â ãðàôå äîìåíîâ íàèáîëåå îòðèöàòåëüíîãî
ðàçðåçà (â òåðìèíîëîãèè À. Çûêîâà � êâàëèðàçðå-
çà [4, ñ. 199]). Ïðè îïòèìàëüíîì ðàññëîåíèè äîìåíû,
íàõîäÿùèåñÿ ïî îäíó ñòîðîíó ðàçðåçà, ñîõðàíÿò ñâîþ
îðèåíòàöèþ, à ïî äðóãóþ � èçìåíÿò åå, ïðè ýòîì
êîëè÷åñòâî ïåðåõîäîâ èçìåíèòñÿ íà âåëè÷èíó ðàç-
ðåçà. Èíòåðåñóþùèé íàñ ðàçðåç ïîêàçàí íà ðèñ. 2
âîëíèñòîé ëèíèåé. Åãî âåëè÷èíà ðàâíà +3�8 = �5,
ò. ê. îí ñîñòîèò èç òðåõ ïîëîæèòåëüíûõ è âîñüìè
îòðèöàòåëüíûõ ðåáåð.
Êàê èçâåñòíî, äëÿ ãðàôîâ îáùåãî âèäà çàäà÷à
ïîèñêà íàèáîëåå îòðèöàòåëüíîãî ðàçðåçà NP-ñëîæíà,
íî äëÿ ïëàíàðíûõ ãðàôîâ ðàçðåøèìà çà ïîëèíîìè-
àëüíîå âðåìÿ. Ëåãêî âèäåòü, ÷òî ãðàô äîìåíîâ âñå-
ãäà ïëàíàðåí. Îäèí èç ýôôåêòèâíûõ àëãîðèòìîâ
[5] ðåøàåò ýòó çàäà÷ó çà O(PNlogN+P3logP) ïðè
òðåáóåìîé ïàìÿòè O(PN), ãäå N � ÷èñëî âåðøèí
ãðàôà äîìåíîâ, P � ÷èñëî ãðàíåé, îãðàíè÷åííûõ
íå÷åòíûì ÷èñëîì ðåáåð îòðèöàòåëüíîãî âåñà.
2. Ðåäóêöèÿ ãðàôà äîìåíîâ
Ïåðåñå÷åíèÿ òðàññ íà ðèñóíêå ñîâìåùåííîé òî-
ïîëîãèè òèïè÷íîé ñîâðåìåííîé ñõåìû èñ÷èñëÿþòñÿ
äåñÿòêàìè òûñÿ÷,÷òî âåäåò ê áîëüøîé ðàçìåðíîñòè
ãðàôà äîìåíîâ. Ïðè ýòèõ óñëîâèÿõ ïîòðåáíîñòè âî
âðåìåíè è ïàìÿòè äàæå ïîëèíîìèàëüíîãî àëãîðèòìà
ïîèñêà íàèáîëåå îòðèöàòåëüíîãî ðàçðåçà îêàçûâà-
þòñÿ ÷ðåçìåðíî áîëüøèìè. Äëÿ ïðàêòè÷åñêîãî ïðè-
ìåíåíèÿ ìîæíî äîïóñòèòü àëãîðèòìû òîëüêî ñ ëè-
íåéíûìè òðåáîâàíèÿìè ê ïàìÿòè è òîëüêî ñ ëèíåé-
íûìè òðåáîâàíèÿìè ê ÷èñëó îïåðàöèé.
Ïåðå÷èñëåííûå íèæå ïðåîáðàçîâàíèÿ ðåäóêöèè
ãðàôà äîìåíîâ çà ëèíåéíîå ÷èñëî îïåðàöèé óìåíü-
øàþò åãî ðàçìåð áåç ïîòåðè îïòèìàëüíîãî ðåøå-
íèÿ. Ïîñëå îïðåäåëåíèÿ îïòèìàëüíîé îðèåíòàöèè
äîìåíîâ ðåäóöèðîâàííîãî ãðàôà ëåãêî âîññòàíîâèòü
îïòèìàëüíóþ îðèåíòàöèþ è äëÿ èñõîäíîãî ãðàôà.
 îáùåì ñëó÷àå ãðàô äîìåíîâ ÿâëÿåòñÿ ìóëüòè-
ãðàôîì, ïîñêîëüêó îí ìîæåò èìåòü ïåòëè è êðàòíûå
ðåáðà. Îäíàêî ïåòëè íå âõîäÿò íè â îäèí ðàçðåç,
ïîýòîìó èõ ìîæíî óäàëèòü. Ïðè ýòîì òàê êàê ïåòëè
îòðèöàòåëüíîãî âåñà ñîîòâåòñòâóþò îáÿçàòåëüíûì
ïåðåõîäàì, òî óäàëÿÿ îòðèöàòåëüíûå ïåòëè, çàïîì-
íèì èõ ñóììàðíûé âåñ (ñî çíàêîì "ïëþñ"). Íàçî-
âåì ýòó âåëè÷èíó íàêîïëåííûì êîëè÷åñòâîì ïåðå-
õîäîâ (ÍÊÏ).
Ïðåîáðàçîâàíèå 1 (ðèñ. 4). Ïóñòü äîìåíû
A è B ñîåäèíåíû ñðàçó íåñêîëüêèìè ðåáðàìè. Òàê
êàê ýòè ðåáðà âõîäÿò â ëþáîé ðàçðåç òîëüêî âñå
âìåñòå, òî çàìåíèì èõ íà îäíî ðåáðî ñóììàðíîãî
âåñà. Ïðè ýòîì åñëè âåñà ðåáåð èìåëè ðàçíûå çíàêè,
òî íåêîòîðîå êîëè÷åñòâî ïåðåõîäîâ ïîïàäåò â ðàç-
ðÿä îáÿçàòåëüíûõ. Äîáàâèì ýòó âåëè÷èíó ê íàêîï-
ëåííîìó êîëè÷åñòâó ïåðåõîäîâ. Âåñ ðåçóëüòèðóþ-
ùåãî ðåáðà ìîæåò îêàçàòüñÿ è ðàâíûì íóëþ, òàêîå
ðåáðî ïðîñòî èñ÷åçàåò.
Ðèñ. 2. Ñîîòâåòñòâóþùèé ãðàô äîìåíîâ è åãî íàèáîëåå
îòðèöàòåëüíûé ðàçðåç
6 7 17 16 27 26 28
1
8 18 19
9 2
3
4
10
11
20 21 29 30
31 32
12 22 33
13
14
5 15
23 37 36 35 34
39 38
24
25
Ðèñ. 3. Èçìåíåíèå îðèåíòàöèè äîìåíà
-x2
-xi
-xN
-x1
–
x2
xi
xN
x1
+
Ðèñ. 4. Ãðàôè÷åñêàÿ èëëþñòðàöèÿ ê ïðåîáðàçîâàíèþ 1
y
x x + y
A B A B
+ ( |x| + |y| – |x + y| ) / 2
îáÿçàòåëüíûõ ïåðåõîäîâ
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 2
5
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
Ïðåîáðàçîâàíèå 2 (ðèñ. 5). Ïóñòü âåñ ðåáðà
AB ïîëîæèòåëåí è íàñòîëüêî âåëèê, ÷òî ñóììà àáñî-
ëþòíûõ âåëè÷èí âåñîâ îñòàëüíûõ ðåáåð, èíöèäåíò-
íûõ äîìåíó A, íå ïðåâûøàåò åãî. Òîãäà ñðåäè íàè-
áîëåå îòðèöàòåëüíûõ ðàçðåçîâ ñóùåñòâóåò ðàçðåç,
íå ñîäåðæàùèé ðåáðà AB.
Äåéñòâèòåëüíî, ïðåäïîëîæèì, ÷òî ðåáðî AB âõî-
äèò â íàèáîëåå îòðèöàòåëüíûé ðàçðåç. Òîãäà, çàìå-
íèâ â ýòîì ðàçðåçå ðåáðî AB íà ñîâîêóïíîñòü îñ-
òàëüíûõ ðåáåð, èíöèäåíòíûõ äîìåíó A, ìû ïîëó÷èì
ðàçðåç íå ìåíåå îòðèöàòåëüíûé.
Ñòÿíåì ðåáðî AB, îáúåäèíèâ âåðøèíû A è B â
îäíó. ( ÷àñòíîñòè, âñåãäà ìîæíî ñòÿíóòü îäíî èç
ðåáåð, èíöèäåíòíûõ äîìåíó ñòåïåíè 2 èëè 1.)
Ïðåîáðàçîâàíèå 3. Èçîëèðîâàííîìó äîìåíó
ïðèïèøåì ïðîèçâîëüíóþ îðèåíòàöèþ è óäàëèì åãî
èç äàëüíåéøåãî ðàññìîòðåíèÿ.
Ïðåîáðàçîâàíèå 4. Íà ðèñ. 6 ñëåâà ïîêàçàíà
òðåóãîëüíàÿ ãðàíü ABC, âåñà âñåõ åå ðåáåð ïîëîæè-
òåëüíû. Ýêâèâàëåíòíûé ïîäãðàô ïîêàçàí íà òîì æå
ðèñóíêå ñïðàâà. Ïðåîáðàçîâàíèå êîððåêòíî, ïîñêîëü-
êó ðåáðà òðåóãîëüíîé ãðàíè âõîäÿò â ëþáîé ðàçðåç
òîëüêî ïîïàðíî.
 ÷åì æå ñîñòîèò âûãîäà äàííîãî ïðåîáðàçîâà-
íèÿ? Âåäü ÷èñëî ðåáåð îñòàëîñü ïðåæíèì, à ÷èñëî
âåðøèí äàæå óâåëè÷èëîñü.
Äåëî â òîì, ÷òî íîâûå ðåáðà èìåþò áîëüøèé âåñ
è îáû÷íî ñðàçó æå áûâàþò ñòÿíóòû ïðåîáðàçîâàíè-
åì 2. Óñëîâèìñÿ ïðèìåíÿòü ïðåîáðàçîâàíèå 4 òîëü-
êî â òîì ñëó÷àå, åñëè õîòÿ áû îäíî èç íîâûõ ðåáåð
áóäåò ñòÿíóòî. Òîãäà ÷èñëî âåðøèí íå óâåëè÷èòñÿ, à
÷èñëî ðåáåð óìåíüøèòñÿ (ðèñ. 7).
Åùå íåñêîëüêî ÷óòü áîëåå ñëîæíûõ ïðåîáðàçî-
âàíèé áóäåò ïðèâåäåíî â ðàçäåëå 4.
Òåîðåìà 1.
×èñëî îïåðàöèé, òðåáóþùååñÿ äëÿ ðåäóêöèè ãðà-
ôà äîìåíîâ, ëèíåéíî çàâèñèò îò ñóììû ÷èñëà âåð-
øèí è ÷èñëà ðåáåð ãðàôà.
Äåéñòâèòåëüíî, êàæäîå ïðåîáðàçîâàíèå âûïîëíÿ-
åòñÿ çà êîíñòàíòíîå ÷èñëî îïåðàöèé, à ò. ê. ïîñëå
êàæäîãî ïðåîáðàçîâàíèÿ óìåíüøàåòñÿ èëè ÷èñëî ðå-
áåð, èëè ÷èñëî âåðøèí, òî îáùåå ÷èñëî îïåðàöèé íå
ïðåâûøàåò Î(N+M), ãäå N � ÷èñëî âåðøèí, M �
ðåáåð.
Ïîñëå ïðèìåíåíèÿ îïèñàííûõ ïðåîáðàçîâàíèé ðàç-
ìåð ãðàôà äîìåíîâ óìåíüøàåòñÿ. Ïîñêîëüêó ýòè ïðå-
îáðàçîâàíèÿ íå íàðóøàþò ïëàíàðíîñòè ãðàôà, ê ðå-
äóöèðîâàííîìó ãðàôó ìîæåò áûòü ïðèìåíåí àëãî-
ðèòì ïîèñêà íàèáîëåå îòðèöàòåëüíîãî ðàçðåçà [5].
Âîïðîñ, íàìíîãî ëè ðåçóëüòèðóþùèé ãðàô ìåíüøå
èñõîäíîãî, îñòàåòñÿ îòêðûòûì. Ìîæíî óêàçàòü, ÷òî
çà 10 ëåò ïðàêòè÷åñêîãî ïðèìåíåíèÿ áûëè îïðîáî-
âàíû ìíîãèå òûñÿ÷è ðåàëüíûõ òîïîëîãèé. Äëÿ êàæ-
äîé èç íèõ ðàçìåð ãðàôà äîìåíîâ â ðåçóëüòàòå ðå-
äóêöèè óìåíüøàëñÿ äî íóëÿ.
3. Ïðèìåð ðåäóêöèè ãðàôà äîìåíîâ
Ïîñìîòðèì åùå ðàç íà ðèñ. 2. Çàìåòèì, ÷òî äî-
ìåí 25 èìååò ëèøü îäíó ñâÿçü � ñ äîìåíîì 24. Âåñ
ýòîãî ðåáðà ïîëîæèòåëåí, ñëåäîâàòåëüíî, äëÿ îòñóò-
ñòâèÿ íà íåì ïåðåõîäà íåîá-
õîäèìî, ÷òîáû äîìåíû 25 è 24
áûëè îðèåíòèðîâàíû îäèíà-
êîâî. Ñòÿíóâ ðåáðî, îáúåäè-
íèì äîìåíû 25 è 24 â îäèí.
Îñòàâèì çà íèì íîìåð 24, çà-
ïîìíèâ, ÷òî äîìåí 25 èìååò
òàêóþ æå îðèåíòàöèþ. Â äàëü-
íåéøåì èçëîæåíèè áóäåì èñ-
ïîëüçîâàòü êðàòêóþ çàïèñü
îáúåäèíåíèÿ âåðøèí:
1. 25�> 24.
Îáðàòèì âíèìàíèå íà äî-
ìåí 5. Åãî ñòåïåíü ðàâíà äâóì,
ñëåäîâàòåëüíî, ìû îïÿòü âïðà-
âå ïðèìåíèòü ïðåîáðàçîâàíèå
2. Ïðè ýòîì, ò. ê. âåñà îáîèõ
ðåáåð ñîâïàäàþò ïî àáñîëþò-
íîìó çíà÷åíèþ (õîòÿ èìåþò
Ðèñ. 5. Ïðåîáðàçîâàíèå 2
yN
yi
y1
x
A B
∑
=
≥
N
i
iyx
1
||
yN
yi
y1
A=B
Ðèñ. 6. Ïðåîáðàçîâàíèå 4
y
z
x
x + y
C
A B
x, y, z > 0
y + z x + z
C
A B
D
Ðèñ. 7. Âûãîäà ïðåîáðàçîâàíèÿ 4
wN
wi
w1
wN
wi
w1
y + z
x + y
x + z
C
A B
x, y, z > 0
∑
=
≥+
N
i
iwyx
1
||
y + z x + z
C
A B
D
wN
wi
w1
z
y x
A B
C
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 2
6
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
ðàçíûå çíàêè), ðàâíîïðàâíû äâà âàðèàíòà åãî ïðè-
ìåíåíèÿ: ëèáî îáúåäèíèòü äîìåíû 5 è 15, ñ÷èòàÿ, ÷òî
èõ îðèåíòàöèÿ îäèíàêîâà, ëèáî îáúåäèíèòü äîìåíû
5 è 14, ñ÷èòàÿ, ÷òî èõ îðèåíòàöèÿ ðàçëè÷íà. Âûáåðåì
ïåðâûé âàðèàíò: 2. 5�> 15.
Òåïåðü îêàçàëîñü, ÷òî íîâûé äîìåí (çà êîòîðûì
ìû îñòàâèëè íîìåð 15) è äîìåí 14 ñîåäèíåíû ñðàçó
äâóìÿ ðåáðàìè: ðåáðîì ñ âåñîì +1 è ðåáðîì ñ âåñîì
�1 (ðèñ. 8, à). Â çàâèñèìîñòè îò òîãî, îäèíàêîâóþ
èëè ðàçíóþ îðèåíòàöèþ ïîëó÷àò â îêîí÷àòåëüíîì
ðàññëîåíèè äîìåíû 14 è 15, íà òîì èëè äðóãîì ðåáðå
ïîòðåáóåòñÿ ïåðåõîä. Çàïîìíèì ýòîò ôàêò, äîáàâèâ
îäèí ïåðåõîä ê íàêîïëåííîìó êîëè÷åñòâó ïåðåõî-
äîâ (ÍÊÏ), ïåðâîíà÷àëüíî íóëåâîìó: ÍÊÏ=1.
Ïðèìåíåíèå ïðåîáðàçîâàíèÿ 1 ïðèâåëî ê òîìó,
÷òî äîìåíû 14 è 15 áîëüøå íå ñîåäèíåíû ðåáðîì
(ðèñ. 8,á). Îáîçíà÷àÿ âåñ ðåáðà ìåæäó äîìåíàìè a
è b ÷åðåç W(a,b), çàïèøåì: W(14,15) = 0.
Òåïåðü ñòåïåíü äîìåíà 15 ñòàëà ðàâíîé åäèíèöå, è
åãî ìîæíî îáúåäèíèòü ñ äîìåíîì 24: 3. 15 �> 24.
Âòîðóþ ñòåïåíü èìåþò äîìåíû 1, 4, 6, 9, 12, 13, 14,
21, 22, 24, 28, 30, 33, 37 è 38. Ñëåäîâàòåëüíî: 4. 14�
> 23, 5. 1�> 2, 6. 4�> 11, 7. 6�> 7, 8. 9�> 10,
9. 12�> 11, 10. 13�> 12, 11. 21�> 20, 12. 22�
> 23, 13. 24�> 23, 14. 28�> 27, 15. 30�> 39,
16. 33�> 37, 17. 37�> 36, 18. 38�> 39.
Òåïåðü, ïîñëå øàãà 18, ñòåïåíè âñåõ âåðøèí ãðà-
ôà áîëüøå ÷åì 2 (ðèñ. 9), è ïðåîáðàçîâàíèå 2 ê åãî
ýëåìåíòàì íåïðèìåíèìî. Ïðèìåíèì ê òðåóãîëüíîé
ãðàíè, îáðàçîâàííîé äîìåíàìè 18, 19 è 20, ïðåîáðàçî-
âàíèå 4.
Íà ðèñ. 10, à âèäíî, ÷òî íîâûé äîìåí (îáîçíà-
÷åííûé çâåçäî÷êîé) ñâÿçàí ñ äîìåíàìè 18, 19 è 20
ðåáðàìè âåñà +2. Ïîñêîëüêó âñå òðè ðåáðà ìîæíî
ñòÿíóòü ñ ïîìîùüþ ïðåîáðàçîâàíèÿ 2, òî äîìåíû 18,
19, 20, à òàêæå íîâûé äîìåí áóäóò îáúåäèíåíû â
îäèí (ðèñ. 10, á). Îñòàâèì çà íèì íîìåð 20, çàïîì-
íèâ, ÷òî äîìåíû 18 è 19 èìåþò òàêóþ æå îðèåíòà-
öèþ: 19. 18, 19�> 20.
Àíàëîãè÷íî: 20. 29, 32�> 31, W(31, 36)=0,
ÍÊÏ=2; 21. 3, 11�> 10.
Òåêóùåå ñîñòîÿíèå ãðàôà ïîêàçàíî íà ðèñ. 11.
22. 36�> 35; 23. 31�> 27; 24. 17, 26�> 20,
W(20, 27)=0, ÍÊÏ=3; 25. 2, 10�> 8, W(8, 7)=0,
ÍÊÏ=4.
Äàëåå ðåäóêöèÿ ïðîòåêàåò ëàâèíîîáðàçíî (ðèñ.
12). Äîìåí 27 ñîåäèíåí ëèøü ñ äîìåíîì 35, íî âåñ
ñîåäèíÿþùåãî ðåáðà îòðèöàòåëåí (�1). Ñòÿíóâ ðåá-
ðî, îòìåòèì, ÷òî äîìåí 27 èìååò îðèåíòàöèþ, ïðîòè-
âîïîëîæíóþ îðèåíòàöèè äîìåíà 35: 26. 27 �>�35;
à á
Ðèñ. 8. Âçàèìîóíè÷òîæåíèå ïàðû ðåáåð
13
14
15
23
24
13
14
15
23
24
Ðèñ. 9. Ãðàô ïîñëå øàãà 18
7 17 16 27 26
8 18 19
2
3 10
11
20 29
31 32
23 36 35 34
39
Ðèñ. 12.
Ãðàô ïîñëå øàãà 25
7 16 27
8
20
23 35 34
39
Ðèñ. 11.
Ãðàô ïîñëå øàãà 21
7 17 16 27 26
8
2
10
20
31
23 36 35 34
39
à á
18 19
*
20 20
Ðèñ. 10. Øàã 19
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 2
7
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
Ðèñ. 13. Ãðàô ïîëíîñòüþ ðàçîáðàí
16
4. Äîïîëíèòåëüíûé íàáîð ïðåîáðàçîâàíèé ãðàôà
äîìåíîâ
Ïðåîáðàçîâàíèå 5 (ðèñ. 16) îáðàòíî ïðåîáðà-
çîâàíèþ 4. Âîçíèêàþùèå ïðè ýòîì ïðåîáðàçîâàíèè
äðîáíûå âåñà ðåáåð íå äîëæíû íèêîãî ñìóùàòü, ïî-
ñêîëüêó ìàíèïóëÿöèè ñ ãðàôîì ÷èñòî ôîðìàëüíûå.
Êàêóþ îðèåíòàöèþ ñëåäóåò ïðèïèñàòü óäàëÿå-
ìîé âåðøèíå D âî âðåìÿ îáðàòíîãî õîäà àëãîðèò-
ìà? Ëåãêî ïîíÿòü, ÷òî äîìåí D äîëæåí ïîëó÷èòü òó
îðèåíòàöèþ, êàêîé îáëàäàåò áîëüøèíñòâî èç ñìåæ-
íûõ ñ íèì äîìåíîâ A, B è C. Çàïèøåì ýòî ñèìâîëè-
÷åñêè: D�> (A, B, C).
Òåïåðü çàìåòèì, ÷òî ïðè ëþáûõ èçìåíåíèÿõ
îðèåíòàöèè äîìåíîâ ÷åòíîñòü ÷èñëà ðåáåð îòðèöà-
òåëüíîãî âåñà â ëþáîì öèêëå ñîõðàíÿåòñÿ. Òàêèì
îáðàçîì, ñóùåñòâóþò òîëüêî äâà ïðèíöèïèàëüíî ðàç-
ëè÷íûõ òèïà òðåóãîëüíûõ ãðàíåé: âñå ðåáðà ïîëî-
æèòåëüíîãî âåñà èëè îäíî èç ðåáåð èìååò îòðèöà-
òåëüíûé âåñ. Ïðåîáðàçîâàíèå 4 (ðèñ. 6) ðàáîòàåò
ëèøü ñ òðåóãîëüíèêàìè ïåðâîãî òèïà.
Ïðåîáðàçîâàíèå 6 (ðèñ. 17, a). Ðàññìîòðèì
òðåóãîëüíóþ ãðàíü ABC, îäíî èç ðåáåð êîòîðîé AB
èìååò îòðèöàòåëüíûé âåñ �z.
Îáîçíà÷èì S wi
i
N
=
=
∑
1
. È ïóñòü x + y � 2z≥S.
Äîáàâèì âðåìåííî ê ãðàôó ðåáðî CD âåñà x+y�2z
(ðèñ. 17, á). Çàìåòèì, ÷òî ïîñêîëüêó âåñ íîâîãî
ðåáðà íå ìåíüøåS, òî âåëè÷èíà íàèáîëåå îòðèöàòåëü-
íîãî ðàçðåçà íå èçìåíèòñÿ. Ïîîáåùàåì íå ðàçðåçàòü
ðåáðî CD.
Ïðèìåíèì ê âðåìåííî äîáàâëåííîé âåðøèíå D
ïðåîáðàçîâàíèå 5. Òåïåðü âåðøèíû A è B ñîåäèíå-
íû ñðàçó äâóìÿ ðåáðàìè ñ âåñàìè z è �z, êîòîðûå
âçàèìíî óíè÷òîæàþòñÿ, à z ïåðåõîäîâ ïîïàäàåò â
ðàçðÿä îáÿçàòåëüíûõ (ðèñ. 17, â).
Âî âðåìÿ îáðàòíîãî õîäà àëãîðèòìà âñïîìíèì î
ñâîåì îáåùàíèè íå ðàçðåçàòü ðåáðî CD. Åñëè îíî
âñå æå îêàçàëîñü ðàçðåçàííûì (ýòî ìîæåò ïðîèçîé-
òè, åñëè x+y�2z=S), òî èçìåíèì îðèåíòàöèþ äîìåíà
C, ïåðåíåñÿ òåì ñàìûì ðàçðåç ñ ðåáðà CD íà îñ-
òàëüíûå èíöèäåíòíûå äîìåíó C ðåáðà. Äðóãèìè ñëî-
âàìè, åñëè ïðè îáðàòíîì õîäå îáíàðóæèòñÿ, ÷òî îðè-
åíòàöèÿ îáîèõ äîìåíîâ A è B îòëè÷àåòñÿ îò îðèåíòà-
öèè äîìåíà C, òî îðèåíòàöèþ äîìåíà C íàäî èçìå-
íèòü. Çàïèøåì ýòî ñèìâîëè÷åñêè: C�> (A, B, C).
27. 35�> 34, W(34, 39)=0, ÍÊÏ=5; 28. 34�> 23;
29. 39�> �23; 30. 7�> 16; 31. 23�> 8, W(8,
20)=�2; 32. 20�> 16, W(8, 16)=�3; 33. 8�> �16.
Îñòàëñÿ åäèíñòâåííûé äîìåí 16 (ðèñ. 13), è ïîðà
ïðèìåíèòü ïðåîáðàçîâàíèå 3.
Ïóñòü äîìåí 16 ñîõðàíèò èñõîäíóþ îðèåíòàöèþ.
Îáðàòíûì õîäîì àëãîðèòìà âîññòàíîâèì âñå äîìå-
íû èñõîäíîãî ãðàôà è óçíàåì èõ îïòèìàëüíóþ îðè-
åíòàöèþ:
33. Äîìåí 8 îðèåíòèðîâàí ïðîòèâîïîëîæíî äîìåíó 16.
32. Äîìåí 20 îðèåíòèðîâàí òàê æå, êàê è äîìåí 16.
31. Äîìåí 23 îðèåíòèðîâàí òàê æå, êàê è äîìåí 8.
30. Äîìåí 7 îðèåíòèðîâàí òàê æå, êàê è äîìåí 16.
29. Äîìåí 39 îðèåíòèðîâàí ïðîòèâîïîëîæíî äîìå-
íó 23.
...................................................
2. Äîìåí 5 îðèåíòèðîâàí òàê æå, êàê è äîìåí 15.
1. Äîìåí 25 îðèåíòèðîâàí òàê æå, êàê è äîìåí 24.
Íàêîïëåííîå êîëè÷åñòâî ïåðåõîäîâ îêàçàëîñü
ðàâíûì 5. Íà ðèñ. 14 ïîêàçàí íàéäåííûé ðàçðåç, à
íà ðèñ. 15 � ñîîòâåòñòâóþùåå ðàññëîåíèå. Ïîòðå-
áîâàëîñü, äåéñòâèòåëüíî, 5 ïåðåõîäîâ.
Ðèñ. 15. Îïòèìàëüíîå ðàññëîåíèå
6 7 17 16 27 26 28
1
8 18 19
9 2
3
4
10
11
20 21 29 30
31 32
12 22 33
13
14
5 15
23 37 36 35 34
39 38
24
25
Ðèñ. 14. Îïòèìàëüíàÿ îðèåíòàöèÿ äîìåíîâ
Ðèñ. 16. Ïðåîáðàçîâàíèå 5
(y + z – x) /2
(x + y – z) /2
(x + z – y) / 2
z
C
A B
x, y, z > 0
x < y + z
y < x + z
z < x + y
y x
C
A B
D
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 2
8
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
w
x, y, z, w > 0
∑
=
=
N
i
ia aS
1
||
∑
=
=
M
i
ib bS
1
||
aN ai
a1 y
z `x
A
C D
bN
bi
b1
B
aN ai
a1 y + w
z `x + w
A
C D
b1
B
x + y ≥ Sa
y + z ≥ Sb
x + z ≥ Sa + Sb
Ðèñ. 19. Ïðåîáðàçîâàíèå 7
�(z � d)
wN
wi
w1
wN
wi
w1
�z
y � d
S
x � d
C
A B
x, y, z > 0
∑
=
=
N
i
iwS
1
||
x + y > S
x + y � 2z < S
y x
C
A B
D
wN
wi
w1
�z
y x
A B
C
+ d îáÿçàòåëüíûõ
ïåðåõîäîâ
d = (x + y � S) / 2
Ðèñ. 18. ×àñòè÷íîå ïðåîáðàçîâàíèå 6
à á â
à á â
wN
wi
w1
wN
wi
w1
-z
y - z
x + y - 2z
x - z
C
A B
x, y, z > 0
∑
=
≥−+
N
i
iwzyx
1
||2
y x
C
A B
D
wN
wi
w1
-z
y x
A B
C
+ z îáÿçàòåëüíûõ
ïåðåõîäîâ
Ðèñ. 17. Ïðåîáðàçîâàíèå 6
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 2
9
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
Ëþáîïûòíî ñðàâíèòü ðèñóíêè 7 è 17.
À ÷òî, åñëè x+y>S, íî x+y�2z< S? Òîãäà ðåáðî
AB ñîâñåì óáðàòü íåëüçÿ, íî ìîæíî óìåíüøèòü åãî
àáñîëþòíóþ âåëè÷èíó íà (x+y�S)/2. Íàñòîëüêî æå
óìåíüøàòñÿ è âåñà ðåáåð AC è BC (ðèñ. 18).
Íå áóäåì ââîäèòü äëÿ ýòîãî ïðåîáðàçîâàíèÿ îò-
äåëüíîãî íîìåðà, ïîñêîëüêó îíî àíàëîãè÷íî ïðåîá-
ðàçîâàíèþ 6, çà èñêëþ÷åíèåì òîãî, ÷òî ÷èñëî ðåáåð
íå óìåíüøàåòñÿ. Òåì íå ìåíåå íàêîïëåííîå êîëè÷å-
ñòâî ïåðåõîäîâ óâåëè÷èâàåòñÿ, ïîýòîìó çàöèêëèâà-
íèå íåâîçìîæíî.
Ïðåîáðàçîâàíèå 7 (ðèñ. 19). Ðàññìîòðèì ÷å-
òûðåõóãîëüíóþ ãðàíü ABCD. Îáîçíà÷èì
S aa i
i
N
=
=
∑
1
, S bb i
i
M
=
=
∑
1
,
è ïóñòü x+y≥≥≥≥≥Sa, y+z≥≥≥≥≥Sb, x+z≥≥≥≥≥Sa+Sb.
Èç ïåðâîãî íåðàâåíñòâà ñëåäóåò, ÷òî ñðåäè íàè-
áîëåå îòðèöàòåëüíûõ ðàçðåçîâ ñóùåñòâóåò ðàçðåç,
íå ñîäåðæàùèé ñîâìåñòíî ðåáåð AB è AD.
Äåéñòâèòåëüíî, ïðåäïîëîæèì, ÷òî â íàèáîëåå îò-
ðèöàòåëüíûé ðàçðåç âõîäÿò ðåáðà AB è AD. Òîãäà,
çàìåíèâ â ýòîì ðàçðåçå ðåáðà AB è AD íà ñîâîêóï-
íîñòü îñòàëüíûõ ðåáåð, èíöèäåíòíûõ äîìåíó A, ìû
ïîëó÷èì ðàçðåç íå ìåíåå îòðèöàòåëüíûé.
Èç äâóõ äðóãèõ íåðàâåíñòâ òî÷íî òàê æå ñëåäó-
åò, ÷òî ñðåäè íàèáîëåå îòðèöàòåëüíûõ ðàçðåçîâ ñó-
ùåñòâóåò ðàçðåç, íå ñîäåðæàùèé ñîâìåñòíî ðåáåð
AB è BC è ñîâìåñòíî ðåáåð BC è CD.
Òàêèì îáðàçîì, ñðåäè âñåõ âîçìîæíûõ ðàçðåçîâ
÷åòûðåõóãîëüíèêà ABCD îñòàëèñü òîëüêî ðàçðåçû
CD+AD, CD+AB è CD+BC. Èõ âåëè÷èíû ñîîòâåò-
ñòâåííî ðàâíû x+w, y+w è z+w. Èç ðèñ. 19 âèäíî,
÷òî ïðåîáðàçîâàíèå íå íàðóøàåò âåëè÷èí ýòèõ ðàç-
ðåçîâ.
Ïåðå÷åíü ïðåîáðàçîâàíèé ìîæíî ïðîäîëæèòü (íà-
ïðèìåð, ïðîâåñòè ïðåîáðàçîâàíèå ïÿòèóãîëüíîé ãðà-
íè), íî äëÿ ïðàêòè÷åñêèõ íóæä âïîëíå äîñòàòî÷íî
ïðèâåäåííîãî íàáîðà.
Ïðàêòèêà òàêæå ïîêàçûâàåò, ÷òî ïðåîáðàçîâàíèå
5 (ïðåâðàùåíèå òðîéíèêà â òðåóãîëüíèê) î÷åíü âàæíî,
îäíàêî ïðèìåíÿòü åãî ñëåäóåò â ïîñëåäíþþ î÷åðåäü,
êîãäà äðóãèå ïðåîáðàçîâàíèÿ íåïðèìåíèìû. Ýòî,
êñòàòè, åäèíñòâåííîå ïðåîáðàçîâàíèå, êîòîðîå íå
óìåíüøàåò ÷èñëà ðåáåð ãðàôà, óìåíüøàåò òîëüêî ÷èñ-
ëî âåðøèí.
5. Òî÷êè ðàçâåòâëåíèÿ òðàññ è ïëàíàðíûå
êîíòàêòíûå ïëîùàäêè
Êðîìå ñêâîçíûõ êîíòàêòíûõ ïëîùàäîê, íà ðå-
àëüíûõ ïëàòàõ âñòðå÷àþòñÿ è òàêèå ýëåìåíòû ïå÷àò-
íîãî ìîíòàæà, êàê òî÷êè ðàçâåòâëåíèÿ òðàññ è ïëà-
íàðíûå êîíòàêòíûå ïëîùàäêè (ïëîùàäêè, äîñòóï-
íûå òîëüêî íà îäíîì ñëîå).
Îáðàòèì âíèìàíèå âíà÷àëå íà òî÷êè âåòâëåíèÿ
ñòåïåíè òðè � òðîéíèêè. Çàìåòèì, ÷òî èç òðåõ òðàññ,
ïîäõîäÿùèõ ê òðîéíèêó, õîòÿ áû äâå ïîäõîäÿò â
îäíîì ñëîå. Åñëè â òî÷êå âåòâëåíèÿ åñòü ìåæñëîé-
íûé ïåðåõîä, ïåðåíåñåì åãî íà îñòàâøóþñÿ òðàññó.
Òåïåðü òðîéíèê öåëèêîì íàõîäèòñÿ íà îäíîì ñëîå,
íà ãðàôå åìó ñîîòâåòñòâóåò äîìåí, ïðè÷åì èçìåíå-
íèå îðèåíòàöèè äîìåíà îçíà÷àåò ïåðåìåùåíèå òðîé-
íèêà íà äðóãîé ñëîé.
Ê ñîæàëåíèþ, ñ òî÷êàìè âåòâëåíèÿ áîëüøèõ ñòå-
ïåíåé ïîäîáíûì îáðàçîì ïîñòóïèòü íåëüçÿ. Íå ñó-
ùåñòâóåò àäåêâàòíîãî ïðåäñòàâëåíèÿ òî÷åê âåòâëå-
íèÿ ñòåïåíè áîëüøå òðåõ. Íî ïîñêîëüêó òàêèõ òî-
÷åê íå áûâàåò ìíîãî, ïðåäëàãàåòñÿ, æåðòâóÿ òî÷íîñ-
òüþ ðåøåíèÿ, ðàññìàòðèâàòü èõ êàê êîíòàêòíûå ïëî-
ùàäêè, äîñòóïíûå íà îáîèõ ñëîÿõ. Òàêèå ïëîùàäêè,
ïî îïðåäåëåíèþ, äîìåíàìè íå ÿâëÿþòñÿ è íà ãðàôå
äîìåíîâ íèêàê íå ôèãóðèðóþò.
Îñîáî ñëåäóåò ñêàçàòü î ïëàíàðíûõ êîíòàêòíûõ
ïëîùàäêàõ, ò. å. ïëîùàäêàõ, äîñòóïíûõ íà îäíîì, ôèê-
ñèðîâàííîì ñëîå. Òàê êàê èçìåíèòü íîìåð äîñòóï-
íîãî ñëîÿ ìû íå ìîæåì, òàêèì ïëîùàäêàì ñîîòâåò-
ñòâóþò äîìåíû ôèêñèðîâàííîé îðèåíòàöèè. Ïðè ýòîì
âñå ýòè äîìåíû ìîæíî ñðàçó æå îáúåäèíèòü â îäèí.
Ýòîò äîïîëíèòåëüíûé äîìåí èìååò ñâÿçè ñ áîëüøèì
êîëè÷åñòâîì äîìåíîâ, è ãðàô ïåðåñòàåò áûòü ïëà-
íàðíûì. À ýòî çíà÷èò, ÷òî çàäà÷à ïîèñêà íàèáîëåå
îòðèöàòåëüíîãî ðàçðåçà ñòàíîâèòñÿ NP-ñëîæíîé.
Íî âåäü ïðè îïèñàíèè ïðåîáðàçîâàíèé ãðàôà ìû
íèãäå íå òðåáîâàëè åãî ïëàíàðíîñòè. Ýêñïåðèìåíòû
ïîêàçàëè, ÷òî è ïðè íàëè÷èè ïëàíàðíûõ êîíòàêòíûõ
ïëîùàäîê ðåäóêöèÿ íå òîëüêî âîçìîæíà, íî äàæå
îñóùåñòâëÿåòñÿ ñ áîëüøåé ñêîðîñòüþ.
Íàêîíåö, ïðåäïîëîæèì, ÷òî ñòîèìîñòè ïåðåõîäîâ
íà ðàçëè÷íûõ ó÷àñòêàõ òðàññ ðàçëè÷íû, è íåîáõîäè-
ìî ìèíèìèçèðîâàòü ñóììàðíóþ ñòîèìîñòü ïåðåõî-
äîâ. Ýòîãî ìîæíî äîñòè÷ü, íàçíà÷èâ ðåáðàì ñîîò-
âåòñòâóþùèå âåñà (çíàêè âåñîâ ïî-ïðåæíåìó îïðå-
äåëÿþò íàëè÷èå èëè îòñóòñòâèå ïåðåõîäîâ). Çàäà÷à
ðåøàåòñÿ àíàëîãè÷íî.
6. Çàêëþ÷åíèå
Îïèñàíà ýôôåêòèâíàÿ ïðîöåäóðà ìèíèìèçàöèè
êîëè÷åñòâà ìåæñëîéíûõ ïåðåõîäîâ íà îñíîâå ðå-
äóêöèè ãðàôà äîìåíîâ. Äëÿ ïðîâåäåíèÿ ðåäóêöèè
ðàçðàáîòàí íàáîð ëîêàëüíûõ ïðåîáðàçîâàíèé. Ïî-
êàçàíî, ÷òî ïðåäëîæåííûå ëîêàëüíûå ïðåîáðàçîâà-
íèÿ íå ïðèâîäÿò ê ïîòåðå îïòèìàëüíîãî ðåøåíèÿ.
Ïîêàçàíî òàêæå, ÷òî ñëîæíîñòü àëãîðèòìà ëèíåé-
íî çàâèñèò îò êîëè÷åñòâà ïåðåñå÷åíèé ïðîâîäíèêîâ.
Ïðåäëîæåííàÿ â ñòàòüå ïðîöåäóðà ãëîáàëüíîé ìè-
íèìèçàöèè ÷èñëà ïåðåõîäîâ ïðèìåíÿåòñÿ â òîïîëî-
ãè÷åñêîì òðàññèðîâùèêå FreeStyleRoute.  ðåçóëü-
òàòå îáû÷íî äîñòèãàåòñÿ êîëè÷åñòâî ìåæñëîéíûõ
ïåðåõîäîâ ïðèìåðíî â 10�30 ðàç ìåíüøåå, ÷åì ó
òðàññèðîâùèêîâ, íå èñïîëüçóþùèõ ýòó ïðîöåäóðó.
ÈÑÏÎËÜÇÎÂÀÍÍÛÅ ÈÑÒÎ×ÍÈÊÈ
1. Ñåëþòèí Â. À. Ìàøèííîå êîíñòðóèðîâàíèå ýëåê-
òðîííûõ óñòðîéñòâ.� Ì.: Ñîâ. ðàäèî, 1977.
2. Ìåëèõîâ À. Ì., Áåðøòåéí Ë. Ñ., Êóðåé÷èê Â. Ì.
Ïðèìåíåíèå ãðàôîâ äëÿ ïðîåêòèðîâàíèÿ äèñêðåòíûõ
óñòðîéñòâ.� Ì.: Íàóêà, 1974.
3.Áàçèëåâè÷ Ð. Ï. Äåêîìïîçèöèîííûå è òîïîëîãè÷åñ-
êèå ìåòîäû àâòîìàòèçèðîâàííîãî ìåòîäà êîíñòðóèðîâà-
íèÿ ýëåêòðîííûõ óñòðîéñòâ.� Ëüâîâ.: Âèùà øêîëà, 1981.
4.Çûêîâ À. À. Îñíîâû òåîðèè ãðàôîâ.� Ì.: Íàóêà,
1987.
5. Êàðçàíîâ À. Â. Àëãîðèòì ìàêñèìàëüíîé óïàêîâ-
êè íå÷åòíîïîëþñíûõ ðàçðåçîâ è åãî ïðèëîæåíèÿ // Â
êí.: Èññëåäîâàíèÿ ïî ïðèêëàäíîé òåîðèè ãðàôîâ.�
Íîâîñèáèðñê: Íàóêà, 1986.� Ñ. 126�140.
|
| id | nasplib_isofts_kiev_ua-123456789-70833 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2225-5818 |
| language | Russian |
| last_indexed | 2025-12-07T17:28:22Z |
| publishDate | 2001 |
| publisher | Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України |
| record_format | dspace |
| spelling | Полубасов, О.Б. 2014-11-15T10:38:43Z 2014-11-15T10:38:43Z 2001 Глобальная минимизация количества межслойных переходов / О.Б. Полубасов // Технология и конструирование в электронной аппаратуре. — 2001. — № 2. — С. 3-9. — Бібліогр.: 5 назв. — рос. 2225-5818 https://nasplib.isofts.kiev.ua/handle/123456789/70833 681.14 Раскрываются особенности эффективного (линейного по числу операций и требуемой памяти) алгоритма точного решения задачи расслоения совмещенной топологии проводящего рисунка с целью минимизации количества межслойных переходов для случая двух трассировочных слоев. Алгоритм используется в трассировщике FreeStyleRoute. ru Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України Технология и конструирование в электронной аппаратуре Проектирование. Конструирование Глобальная минимизация количества межслойных переходов Article published earlier |
| spellingShingle | Глобальная минимизация количества межслойных переходов Полубасов, О.Б. Проектирование. Конструирование |
| title | Глобальная минимизация количества межслойных переходов |
| title_full | Глобальная минимизация количества межслойных переходов |
| title_fullStr | Глобальная минимизация количества межслойных переходов |
| title_full_unstemmed | Глобальная минимизация количества межслойных переходов |
| title_short | Глобальная минимизация количества межслойных переходов |
| title_sort | глобальная минимизация количества межслойных переходов |
| topic | Проектирование. Конструирование |
| topic_facet | Проектирование. Конструирование |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/70833 |
| work_keys_str_mv | AT polubasovob globalʹnaâminimizaciâkoličestvamežsloinyhperehodov |