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

   Åñëè (n, n−1)-ãðàô ÿâëÿåòñÿ äåðåâîì, òî ìîäóëü ëþáî-
ãî ìèíîðà n−1 ïîðÿäêà ìàòðèöû èíöèäåíòíîñòè ñîîòâåò-
ñòâóþùåãî îðãðàôà ðàâåí 1 è ðàâåí 0, åñëè ãðàô íå ÿâëÿåòñÿ
äåðåâîì.
   Ïîä ñîîòâåòñòâóþùèì îðãðàôîì äëÿ íåêîòîðîãî íåîðè-
åíòèðîâàííîãî ãðàôà áóäåì ïîíèìàòü îðãðàô, ïîëó÷åííûé ïó-
òåì ïðèäàíèÿ ïðîèçâîëüíîé îðèåíòàöèè ðåáðàì ýòîãî ãðàôà
(äîñòàòî÷íî â êàæäîì ñòîëáöå ìàòðèöû èíöèäåíòíîñòè îäíîé
èç åäèíèö ïðèïèñàòü çíàê ""). Ïåðâàÿ ÷àñòü ïðèâåäåííîãî
óòâåðæäåíèÿ, êàñàþùàÿñÿ äåðåâà, ôàêòè÷åñêè áûëà äîêàçàíà
â ðàçä. 3.2 (ñì. ñòð. 48.). Äîêàæåì âòîðóþ ÷àñòü.
    ¤ Ïóñòü (n, n−1)-ãðàô íå ÿâëÿåòñÿ äåðåâîì è, çíà÷èò,
íåñâÿçåí. Òîãäà åãî ìàòðèöà èíöèäåíòíîñòè ñîñòîèò èç íåñêîëü-
êèõ íåçàâèñèìûõ áëîêîâ, ïðåäñòàâëÿþùèõ ñîáîé ìàòðèöû èí-
öèäåíòíîñòè êîìïîíåíò ñâÿçíîñòè. Òî æå ñàìîå îòíîñèòñÿ è
ê ìàòðèöå èíöèäåíòíîñòè ñîîòâåòñòâóþùåãî îðãðàôà. Êðîìå
òîãî, ñòðîêè ýòîé ìàòðèöû ëèíåéíî çàâèñèìû, ïðè÷åì, ïî-
ñêîëüêó ãðàô íåñâÿçíûé, òàêàÿ çàâèñèìîñòü ñóùåñòâóåò â êàæ-
äîé ãðóïïå ñòðîê, îïèñûâàþùåé òó èëè èíóþ êîìïîíåíòó ñâÿç-
íîñòè. Óäàëèâ íåêîòîðóþ ñòðîêó ìàòðèöû, ïîëó÷èì êâàäðàò-
íóþ ïîäìàòðèöó ïîðÿäêà n−1, îïðåäåëèòåëü êîòîðîé ðàâåí 0.
Äåéñòâèòåëüíî, óäàëåíèå îäíîé ñòðîêè ìîæåò óñòðàíèòü ëè-
íåéíóþ çàâèñèìîñòü òîëüêî äëÿ ñòðîê, îòíîñÿùèõñÿ ëèøü ê
îäíîé êîìïîíåíòå ñâÿçíîñòè. Ñòðîêè, îïðåäåëÿþùèå îñòàëü-
íûå êîìïîíåíòû îcòàþòñÿ ïî-ïðåæíåìó ëèíåéíî çàâèñèìûìè.
Ïîýòîìó ëþáîé ìèíîð n−1 ïîðÿäêà â ðàññìàòðèâàåìîì ñëó-
÷àå ðàâåí 0, ÷òî è òðåáîâàëîñü äîêàçàòü. ¢
    ñîîòâåòñòâèè ñ èçëîæåííûì ïðîöåññ ïîëó÷åíèÿ (ïåðå-
÷èñëåíèÿ) âñåõ îñòîâîâ ãðàôà G(n, m), ïðåäñòàâëåííîãî ìàò-
ðèöåé èíöèäåíòíîñòè, ìîæíî îðãàíèçîâàòü ñëåäóþùèì îáðà-
çîì. Ïîñëåäîâàòåëüíî ôîðìèðóþòñÿ ñî÷åòàíèÿ èç m ïî n−1
ñòîëáöîâ çàäàííîé ìàòðèöû, êîòîðûå îáðàçóþò ìàòðèöû èí-
öèäåíòíîñòè (n−1)-ðåáåðíûõ îñòîâíûõ ïîäãðàôîâ ãðàôà G.
Äëÿ êàæäîé òàêîé ìàòðèöû ïîñëå îáðàáîòêè âñåõ åå ñòîëá-
öîâ (îäíîé èç äâóõ åäèíèö ñòîëáöà ïðèïèñûâàåòñÿ çíàê "")
ïîäñ÷èòûâàåòñÿ çíà÷åíèå ëþáîãî ìèíîðà n−1 ïîðÿäêà. Åñëè
ïîëó÷àåòñÿ +1 èëè 1, òî ñîîòâåòñòâóþùèé îñòîâíûé ïîäãðàô



                            51