Элементы теории графов. Домнин Л.Н. - 78 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

v
2
v
9
,
v
8
v
6
.
v
7
v
7
.
v
5
,
v
4
l(v
3
)=4, l(v
7
)=6,
l(v
10
)=5. v
3
.
v
4
v
6
.
l(v
4
)=5, l(v
6
)=3 v
6
.
v
9
v
1
. v
5
v
7
v
1
, v
9
, v
6
, v
3
, v
4
.
ðèâàåì ïåðâóþ ñòðîêó ìàòðèöû. Çäåñü åäèíèöû ñîäåðæàòñÿ
âî âòîðîì, ïÿòîì è äåâÿòîì ñòîëáöàõ. Ïÿòàÿ âåðøèíà óæå
ïîìå÷åíà, ïîýòîìó ïîìå÷àåì òîëüêî v2 è v9 , çàïèñûâàÿ âî
âñïîìîãàòåëüíîé ñòðîêå äâîéêè â ñîîòâåòñòâóþùèõ ñòîëáöàõ.
Íà òðåòüåé èòåðàöèè àíàëèçèðóåì âòîðóþ è äåâÿòóþ ñòðîêè
ìàòðèöû.  ðåçóëüòàòå ïîìåòêó 3 ïîëó÷àþò v8 è v6 . Ïðî-
äîëæàÿ ïðîöåññ, â èòîãå ïîëó÷àåì ñîâîêóïíîñòü ïîìåòîê, êàê
íà ðèñ. 4.3,á. Ïîñêîëüêó v7 èìååò ïîìåòêó 6, äëèíà èñêîìî-
ãî êðàò÷àéøåãî ïóòè ðàâíà 6. Îñòàåòñÿ íàéòè ñàì ïóòü, ò. å.
ìíîæåñòâî ñîñòàâëÿþùèõ åãî äóã (ðåáåð), èëè ÷òî òîæå ñàìîå,
ïîñëåäîâàòåëüíîñòü ïðîõîäèìûõ âåðøèí.
    Ïîèñê íà÷èíàåì ñ v7 . Áóäåì ïåðåõîäèòü îò âåðøèíû ê âåð-
øèíå, òàê ÷òîáû ïîìåòêà êàæäûé ðàç óìåíüøàëàñü íà åäèíè-
öó, ïîêà íå äîñòèãíåì âåðøèíû v5 , ïðè÷åì îáðàáîòêó âûïîë-
íÿåì ïî ñòîëáöû ìàòðèöû. Â ñåäüìîì ñòîëáöå èìååòñÿ òîëü-
êî îäíà åäèíèöà â ÷åòâåðòîé ñòðîêå. Çíà÷èò, ïðåäïîñëåäíåé
âåðøèíîé ïóòè ÿâëÿåòñÿ v4 ñ ïîìåòêîé 5.  ÷åòâåðòîì ñòîëá-
öå åäèíèöû íàõîäÿòñÿ â òðåòüåé, ñåäüìîé è äåñÿòîé ñòðîêàõ.
Ñîîòâåòñòâóþùèå âåðøèíû èìåþò ïîìåòêè l(v3 )=4, l(v7 )=6,
l(v10 )=5. Èç íèõ ïîäõîäÿùåé ÿâëÿåòñÿ òîëüêî v3 . Ýòî è åñòü
òðåòüÿ îò êîíöà âåðøèíà ïóòè. Ñîäåðæèìîå òðåòüåãî ñòîëá-
öà óêàçûâàåò íà âåðøèíû v4 è v6 . Ïî çíà÷åíèþ ïîìåòêè
( l(v4 )=5, l(v6 )=3 ) ïîäõîäèò òîëüêî v6 . Äåéñòâóÿ àíàëîãè÷-
íûì îáðàçîì, íàõîäèì åùå äâå ïðîìåæóòî÷íûå âåðøèíû ïóòè
v9 è v1 . Îêîí÷àòåëüíî ïîëó÷àåì, ÷òî êðàò÷àéøèé ïóòü èç v5
â v7 ïðîõîäèò ÷åðåç âåðøèíû v1 , v9 , v6 , v3 , v4 .
    Àëãîðèòì Ëè.  êà÷åñòâå ïðèìåðà ïðèìåíåíèÿ ïîèñêà
â øèðèíó ðàññìîòðèì çàäà÷ó òðàññèðîâêè ïå÷àòíûõ ïëàò, ÿâ-
ëÿþùèõñÿ ñîñòàâíîé ÷àñòüþ ëþáîé ñîâðåìåííîé ýëåêòðîííîé
àïïàðàòóðû. Ïå÷àòíàÿ ïëàòà  ýòî òîíêàÿ (1,52ìì) æåñò-
êàÿ ïëàñòèíà èç ýëåêòðîèçîëÿöèîííîãî ìàòåðèàëà, íà êîòî-
ðîé óñòàíàâëèâàþòñÿ èíòåãðàëüíûå ñõåìû, òðàíçèñòîðû, äèî-
äû, êîíäåíñàòîðû è ò. ï. Ýëåêòðè÷åñêîå ñîåäèíåíèå âñåõ ýòèõ
ýëåìåíòîâ îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ïðîâîäíèêîâ, ïðåäñòàâ-
ëÿþùèõ ñîáîé òîí÷àéøèå óçêèå ìåòàëëè÷åñêèå ïîëîñêè, íà-
íåñåííûå ïî îïðåäåëåííîé òåõíîëîãèè íà ïîâåðõíîñòü ïëà-
òû. Ñðåäè ïðî÷èõ îïòèìèçàöèîííûõ çàäà÷ ïðè ïðîåêòèðîâà-
íèè ïå÷àòíûõ ïëàò âàæíîå ìåñòî çàíèìàåò çàäà÷à îòûñêàíèÿ


                             78

Страницы