OK-metodichka-2010-part2 (С.А. Ложкин - Лекции по основам кибернетики (2009)), страница 2

Çàìåòèì, ÷òî îòíîøåíèå äîñòèæèìîñòèâåðøèí ãðàôà G ÿâëÿåòñÿ ðåôëåêñèâíûì è òðàíçèòèâíûì,à åñëè G íåîðèåíòèðîâàííûé ãðàô, òî è ñèììåòðè÷íûì.Ñëåäîâàòåëüíî, ìíîæåñòâî âåðøèí ãðàôà G ðàñïàäàåòñÿ íàêëàññû ýêâèâàëåíòíîñòè ïî îòíîøåíèþ èõ äîñòèæèìîñòè âb , êîòîðûé ïîëó÷àåòñÿ èç ãðàôà G çàìåíîé êàæäîéãðàôå Gb,äóãè íà ñîîòâåòñòâóþùåå íåîðèåíòèðîâàííîå ðåáðî (G = Gåñëè G íåîðèåíòèðîâàííûé ãðàô). Ïðè ýòîì ïîäãðàô ãðàôà G, íàòÿíóòûé íà êàæäûé òàêîé êëàññ âåðøèí, íàçûâà-ðåáðàóäàëåíèÿóäàëåíèÿ âåðøèíû-ïóòåìíà÷àëüíîéìèäëèíîéêîíå÷íîéâíóòðåííè-öåïüþïðîñòîé öåïüþçàìêíóòûì ïóòåìöèêëîìïðîñòûì öèêëîìâåðøèíà äîñòèæèìà èç âåðøèíû â ãðàôå10Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìñâÿçíîé êîìïîíåíòîéñâÿçíûìåòñÿãðàôà G, à ìíîæåñòâî âñåõ åãîñâÿçíûõ êîìïîíåíò îáîçíà÷àåòñÿ ÷åðåç c (G).

Ãðàô G íàçûâàåòñÿ, åñëè |c (G)| = 1.Íàïîìíèì, ÷òî|E (G)| − |V (G)| + |c (G)| > 0(1.2)è ÷òî ëåâàÿ ÷àñòü (1.2) íàçûâàåòñÿ öèêëîìàòè÷åñêèì ÷èñëîì ãðàôà G. Íàïîìíèì òàêæå, ÷òî ýòî ÷èñëî ðàâíî ìàêñè-ìàëüíîìó ÷èñëó ëèíåéíî íåçàâèñèìûõ îòíîñèòåëüíî îïåðàöèè ñèììåòðè÷åñêîé ðàçíîñòè1 îñòîâíûõ ïîäãðàôîâ ãðàôàG, ñîñòîÿùèõ èç îäíîãî ïðîñòîãî öèêëà è èçîëèðîâàííûõâåðøèí.Ìíîæåñòâî S , êîòîðîå ñîñòîèò èç ðåáåð ãðàôà G = (V, E)è îáëàäàåò òåì ñâîéñòâîì, ÷òî âåðøèíà u, u ∈ V , äîñòèæèìà èç âåðøèíû v, v ∈ V , â ãðàôå G, íî íå äîñòèæèìà èçíåå â ãðàôå (V, E \ S), íàçûâàåòñÿ (u|v)ãðàôà G.Ëåãêî âèäåòü, ÷òî ëþáàÿ (u − v)-öåïü ãðàôà G èìååò õîòÿáû îäíî îáùåå ðåáðî ñ ëþáûì (u|v)-ñå÷åíèåì ýòîãî ãðàôà.Ñå÷åíèå, êîòîðîå íå èìååò ñîáñòâåííûõ ïîäìíîæåñòâ, ÿâëÿþùèõñÿ ñå÷åíèåì, íàçûâàåòñÿ.Íåîðèåíòèðîâàííûé (îðèåíòèðîâàííûé) ãðàô, íå èìåþùèé öèêëîâ (ñîîòâåòñòâåííî îðèåíòèðîâàííûõ öèêëîâ), íàçûâàåòñÿ.

Çàìåòèì, ÷òî â îðèåíòèðîâàííîìàöèêëè÷åñêîì ãðàôå G âñåãäà åñòü êàê ñòîêè, òàê è èñòîêè. Ïðè ýòîì äëÿ êàæäîé åãî âåðøèíû v ìîæíî îïðåäåëèòüåå(ñîîòâåòñòâåííî), êàê ìàêñèìàëüíóþ äëèíó (u − v)- (ñîîòâåòñòâåííî (v − u)-) ïóòåé ãðàôà G, ãäå u îäèí èç èñòîêîâ (ñîîòâåòñòâåííî ñòîêîâ) G.-ñå÷åíèåìòóïèêîâûìàöèêëè÷åñêèìãëóáèíóèñõîäÿùóþ ãëóáèíó1Ïîä ñèììåòðè÷åñêîé ðàçíîñòüþ ãðàôîâ G1 è G2 ïîíèìàåòñÿ ãðàôG, äëÿ êîòîðîãîV (G) = V (G1 ) ∪ V (G2 ) ,E (G) = (E (G1 ) ∪ E (G2 )) \ (E (G1 ) ∩ E (G2 )) .Ÿ1.Îñíîâíûå ïîíÿòèÿ èç òåîðèè ãðàôîâ, ñåòåé, ñõåì.11Ëåãêî âèäåòü, ÷òî îòíîøåíèå äîñòèæèìîñòè ÿâëÿåòñÿ îòíîøåíèåì ÷àñòè÷íîãî ïîðÿäêà íà ìíîæåñòâå âåðøèí îðèåíòèðîâàííîãî àöèêëè÷åñêîãî ãðàôà è îáðàòíî.Íåîðèåíòèðîâàííûé ñâÿçíûé àöèêëè÷åñêèé ãðàô íàçûâàåòñÿ.

Äëÿ äåðåâà G, êàê èçâåñòíî, èìååò ìåñòîðàâåíñòâî|E (G)| = |V (G)| − 1.(1.3)äåðåâîìêîðíåìëèñòüÿìèêîð-Äåðåâî ñ âûäåëåííîé âåðøèíîé () íàçûâàåòñÿ, à âñå îòëè÷íûå îò êîðíÿ âåðøèíû ñòåïåíè 1 ýòîãî äåðåâà ñ÷èòàþòñÿ åãî. Îðèåíòèðîâàííûé ãðàô, êîòîðûé ïîëó÷àåòñÿ èç êîðíåâîãî äåðåâà çàìåíîé êàæäîãî åãî íåîðèåíòèðîâàííîãî ðåáðà íà ñîîòâåòñòâóþùóþ äóãó, ¾íàïðàâëåííóþ¿ ê êîðíþ, íàçûâàåòñÿ.Äåðåâî (îðèåíòèðîâàííîå äåðåâî) D, ÿâëÿþùååñÿ îñòîâíûì ïîäãðàôîì ãðàôà G, íàçûâàåòñÿ åãî, à äåðåâî D0 , êîòîðîå ïîëó÷àåòñÿ èç D â ðåçóëüòàòå¾ïîäñîåäèíåíèÿ¿ âñåõ íå âîøåäøèõ â íåãî ðåáåð G ê ñâîèì¾íà÷àëüíûì¿ âåðøèíàì, ãðàôà G.Î÷åâèäíî, ÷òî ïðè ýòîì ãðàô G ìîæåò áûòü ïîëó÷åí èç äåðåâà D0 â ðåçóëüòàòå ïðèñîåäèíåíèÿ íåêîòîðûõ âåðøèí ñòåïåíè 1 (ëèñòüåâ) ê äðóãèì åãî âåðøèíàì. Çàìåòèì, ÷òî ëþáîé íåîðèåíòèðîâàííûé ñâÿçíûé ãðàô, à òàêæå ëþáîé îðèåíòèðîâàííûé àöèêëè÷åñêèé ãðàô ñ 1 ñòîêîì âñåãäà èìåþòîñòîâíûå ïîääåðåâüÿ è íàääåðåâüÿ ñîîòâåòñòâóþùåãî òèïà.Ãðàô, âåðøèíàì è (èëè) ðåáðàì êîòîðîãî ñîïîñòàâëåíû îïðåäåëåííûå ñèìâîëû (ïîìåòêè), ñ÷èòàåòñÿ.

Ïðèìåðîì òàêîãî ãðàôà ÿâëÿåòñÿ, â ÷àñòíîñòè, êîðíåâîå äåðåâî. Äðóãèì ïðèìåðîì ïîìå÷åííîãî ãðàôà ÿâëÿåòñÿ àöèêëè÷åñêèé ãðàô ñ, êîãäà äëÿ ëþáîé äóãè íîìåð âåðøèíû, èç êîòîðîéîíà èñõîäèò, áîëüøå íîìåðà âåðøèíû, â êîòîðóþ ýòà äóãàâõîäèò. Îðèåíòèðîâàííûé ãðàô G íàçûâàåòñÿíåâûì äåðåâîìîðèåíòè-ðîâàííûì äåðåâîìðåâîìîñòîâíûì ïîääå-îñòîâíûì íàääåðåâîìíûì ãðàôîìâåðøèíïîìå÷åí-ìîíîòîííîé íóìåðàöèåéóïîðÿäî÷åí-12Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìíûì, åñëè äëÿ ëþáîé åãî âåðøèíû v,v ∈ V (G), âñå ðåáðà, âõîäÿùèå â v , óïîðÿäî÷åíû è ïðîíóìåðîâàíû ÷èñëàìè1, 2, .

. . , d+G (v).Áóäåì ñ÷èòàòü, ÷òî ðåáðà è âåðøèíû îñòîâíîãî ïîääåðåâà, à òàêæå ðåáðà ñâÿçàííîãî ñ íèì îñòîâíîãî íàääåðåâàïîìå÷åííîãî ãðàôà èìåþò òå æå ñàìûå ïîìåòêè, êîòîðûåîíè èìåëè â èñõîäíîì ãðàôå. Ýòî îçíà÷àåò, â ÷àñòíîñòè, ÷òîîñòîâíîå íàääåðåâî îðèåíòèðîâàííîãî àöèêëè÷åñêîãî óïîðÿäî÷åííîãî ãðàôà ÿâëÿåòñÿ óïîðÿäî÷åííûì.Ãðàôû G0 = (V 0 , E 0 ) è G00 = (V 00 , E 00 ) íàçûâàþòñÿ, åñëè ñóùåñòâóþò òàêèå âçàèìíîîäíîçíà÷íûå îòîáðàæåíèÿ ϕ : V 0 → V 00 è ψ : E 0 → E 00 , ïðè êîòîðûõ âåðøèíûè íåîðèåíòèðîâàííûå ðåáðà (äóãè) G0 ïåðåõîäÿò â âåðøèíû è íåîðèåíòèðîâàííûå ðåáðà (ñîîòâåòñòâåííî äóãè) G00 ññîõðàíåíèåì îòíîøåíèÿ èíöèäåíòíîñòè (ñîîòâåòñòâåííî èñõîäà, çàõîäà) âåðøèí è ðåáåð, à òàêæå âñåõ ïîìåòîê.

Äëÿ(êîíå÷íîãî) ìíîæåñòâà ãðàôîâ G ÷åðåç |G| áóäåì îáîçíà÷àòü÷èñëî ïîïàðíî íåèçîìîðôíûõ ãðàôîâ â G. Èçâåñòíî, ÷òîèçî-ìîðôíûìè|D (q)| 6 4q ,(1.4)ãäå D (q) ìíîæåñòâî óïîðÿäî÷åííûõ îðèåíòèðîâàííûõ êîðíåâûõ äåðåâüåâ ñ íå áîëåå, ÷åì q ðåáðàìè.Ââåäåì òåïåðü îáùèå îïðåäåëåíèÿ è îáîçíà÷åíèÿ, ñâÿçàííûå ñ ñåòÿìè è ¾àáñòðàêòíûìè¿ ñõåìàìè, ñ ðåàëèçàöèåéèìè ôóíêöèé, à òàêæå ñ íåêîòîðûìè ñòðóêòóðíûìè ïðåäñòàâëåíèÿìè ñõåì.Íàáîð âèäà G = (G; V 0 ; V 00 ), ãäå G ãðàô, à V 0 è V 00 âûáîðêè èç ìíîæåñòâà V (G) äëèíû p è q ñîîòâåòñòâåííî,ïðè÷åì âûáîðêà V 0 ÿâëÿåòñÿ âûáîðêîé áåç ïîâòîðåíèé, íàçûâàåòñÿ (p, q).

Ïðè ýòîì âûáîðêà V 0 (âûáîðêà V 00 )ñ÷èòàåòñÿ(ñîîòâåòñòâåííî), à ååi-ÿ âåðøèíà íàçûâàåòñÿ i(ñîîòâåòñòâåííî)èëè, èíà÷å, i(ñîîòâåòñòâåííî-ñåòüþâõîäíîéâûõîäíîé âûáîðêîé-ì âõîäíûìâûõîäíûì ïîëþñîì-ì âõîäîìâûõî-Ÿ1.Îñíîâíûå ïîíÿòèÿ èç òåîðèè ãðàôîâ, ñåòåé, ñõåì.13äîì ) ñåòè G.

Âåðøèíû, íå ó÷àñòâóþùèå âî âõîäíîé è âûõîäíîé âûáîðêàõ ñåòè, ñ÷èòàþòñÿ åå âíóòðåííèìè âåðøèíàìè.Äëÿ òîãî ÷òîáû âûäåëèòü âõîäíóþ è âûõîäíóþ âûáîðêè ñåòè G = (G; V 0 , V 00 ), áóäåì çàïèñûâàòü åå â âèäå G =G(V 0 ; V 00 ) èëè G = G(V 0 ; V 00 ). Ñåòü, â êîòîðîé âõîäíàÿ èâûõîäíàÿ âûáîðêè ñîâïàäàþò (íå ñîâïàäàþò), íàçûâàåòñÿ(ñîîòâåòñòâåííî). Ïðè ýòîì â ñëó÷àå íåðàçäåëåííûõ ïîëþñîâ ñåòüG = (G; V ; V ) = G(V ; V ) áóäåì çàïèñûâàòü â âèäå G =(G; V ) = G(V ). Êàê ïðàâèëî, âõîäû è âûõîäû (ïîëþñà) ñåòèèìåþò ñïåöèàëüíûå ïîìåòêè, êîòîðûå îòëè÷àþò ýòè âåðøèíû îò äðóãèõ âåðøèí ñåòè è óêàçûâàþòñÿ âìåñòî íèõ â ñîîòâåòñòâóþùèõ âûáîðêàõ.

Òàêèì îáðàçîì, ñåòè ìîæíî ñ÷èòàòüñïåöèàëüíûì ÷àñòíûì ñëó÷àåì ïîìå÷åííûõ ãðàôîâ.Ïðèìåðîì ñåòè ÿâëÿåòñÿ êîðíåâîå äåðåâî, âõîäàìè êîòîðîãî ñ÷èòàþòñÿ åãî ëèñòüÿ, à âûõîäîì êîðåíü. Ïðè ýòîìïîðÿäîê ëèñòüåâ âî âõîäíîé âûáîðêå îðèåíòèðîâàííîãî óïîðÿäî÷åííîãî êîðíåâîãî äåðåâà D çàäàåòñÿ ¾åñòåñòâåííîé¿íóìåðàöèåé τ , îòîáðàæàþùåé ìíîæåñòâî âåðøèí äåðåâà Dâ N òàê, ÷òî τ (v 0 ) < τ (v 00 ) òîãäà è òîëüêî òîãäà, êîãäà ëèáîv 00 äîñòèæèìà èç v 0 , ëèáî k 0 < k 00 , ãäå k 0 è k 00 íîìåðà äóã,ïî êîòîðûì öåïè, ñîåäèíÿþùèå âåðøèíû v 0 è v 00 ñîîòâåòñòâåííî ñ êîðíåì D, âõîäÿò â ñâîþ ïåðâóþ îáùóþ âåðøèíó.Äëÿ ïðîèçâîëüíûõâûáîðîê V 0 = v10 , .

. . , vp0 è V 00 == v100 , . . . , vq00 èç ìíîæåñòâà V (G) ãðàôà G îïðåäåëèìV0V 00 êàê ìàòðèp,qöó M, M ∈ B , äëÿ êîòîðîé(1, åñëè vj00 äîñòèæèìà èç vi0 ,M hi, ji =0, â îñòàëüíûõ ñëó÷àÿõ.ñåòüþ ñ íåðàçäåëåííûìèïîëþñàìèðèöó äîñòèæèìîñòè âûáîðêèñ ðàçäåëåííûìèèç âûáîðêèìàò-Çàìåòèì, ÷òî â ñëó÷àå V 0 = V 00 ìàòðèöà M ÿâëÿåòñÿ ðåôëåêñèâíîé è òðàíçèòèâíîé1 , à åñëè, êðîìå òîãî, G íåîðè1Ìàòðèöà M, M ∈ B m,m , ñ÷èòàåòñÿ ðåôëåêñèâíîé (òðàíçèòèâíîé)14Ãëàâà 2.Îñíîâíûå êëàññû óïðàâëÿþùèõ ñèñòåìåíòèðîâàííûé ãðàô, òî è ñèììåòðè÷íîé ìàòðèöåé. Çàìåòèì òàêæå, ÷òî òðàíçèòèâíîñòü ðåôëåêñèâíîé ìàòðèöû M ,M ∈ B m,m , èìååò ìåñòî òîãäà è òîëüêî òîãäà, êîãäà2M 2 = M.(1.5)c = M 2 , ïîëó÷èìÄåéñòâèòåëüíî, ïîëàãàÿ Mc hi, ji =Mm_M hi, ti · M ht, ji(1.6)t=1c = M íåðàâåíñòâà òðàíçèòèâè, ñëåäîâàòåëüíî, â ñëó÷àå Míîñòèc hi, ji = M hi, ji > M hi, ti · M ht, jiMáóäóò âûïîëíåíû ïðè ëþáûõ i, j, t èç îòðåçêà [1, m].

Ñ äðóãîéñòîðîíû, èç òðàíçèòèâíîñòè ðåôëåêñèâíîé ìàòðèöû M , âñèëó (1.6), ñëåäóåò, ÷òî _c hi, ji = M hi, ji ∨  = M hi, ji .MMhi,ji·Mht,ji16t6mt6=i,jÌàòðèöà äîñòèæèìîñòè âûõîäíîé âûáîðêè ñåòè èç åå âõîäíîé âûáîðêè íàçûâàåòñÿýòîé ñåòè.Ïîä ¾àáñòðàêòíîé¿ ñõåìîé ïîíèìàåòñÿ ñåòü, ÷àñòü ïîìåòîê êîòîðîé ñîñòàâëÿþò âõîäíûå ïåðåìåííûå è â êàæäîéìàòðèöåé äîñòèæèìîñòèòîãäà è òîëüêî òîãäà, êîãäà îíà çàäàåò ðåôëåêñèâíîå (ñîîòâåòñòâåííîòðàíçèòèâíîå) îòíîøåíèå íà ìíîæåñòâå [1, m], òî åñòüM hi, ii = 1(ñîîòâåòñòâåííî M hi, ti · M ht, ji > M hi, ji)äëÿ ëþáîãî i (ñîîòâåòñòâåííî ëþáûõ i, j è t) èç îòðåçêà [1, m].2Ñ÷èòàåì, ÷òî ïðè óìíîæåíèè ìàòðèö èç 0 è 1 âìåñòî îïåðàöèèñëîæåíèÿ èñïîëüçóåòñÿ îïåðàöèÿ äèçúþíêöèè.Ÿ1.15Îñíîâíûå ïîíÿòèÿ èç òåîðèè ãðàôîâ, ñåòåé, ñõåì.âåðøèíå êîòîðîé ðåàëèçóåòñÿ ôóíêöèÿ (ñòîëáåö èç ôóíêöèé) îò ýòèõ ïåðåìåííûõ.

Ïðè ýòîì ñ÷èòàåòñÿ, ÷òî ñàìàñõåìà ðåàëèçóåò ñèñòåìó (ìàòðèöó), ñîñòîÿùóþ èç ôóíêöèé (ñîîòâåòñòâåííî ñòîëáöîâ ôóíêöèé), ðåàëèçîâàííûõ íàåå âûõîäàõ.  êà÷åñòâå âûõîäíûõ ïîìåòîê ñõåìû èñïîëüçóþòñÿ, êàê ïðàâèëî, ñïåöèàëüíûå âûõîäíûå ïåðåìåííûå,à ñõåìà Σ ñ âõîäíûìè ïåðåìåííûìè (âõîäàìè) x1 , . . . , xnè âûõîäíûìè ïåðåìåííûìè z1 , . . . , zm çàïèñûâàåòñÿ â âèäåΣ = Σ(x1 , . . . , xn ; z1 , . .