В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 48
Текст из файла (страница 48)
вылелсннме пунктнрпымн лянпямп столбам матрнпм С(6) нэ примера 4.32). Этот очевидный факт является следствием тога, что каждый простой цикл !ч имеет ребро, ве входяшее в лр)тве цяклм, а следовательно, сшлветствуюшнй етому ребру столбец в матрице С(6) солержит отлнчный от нуля элемент в <-й познцнп [т. е либо 1, лнбо — 1], а все остальные элементы этого столбца равнм О.
4.3.7. Ураввенв» Кнрхгобж длв нэпряженнй Пусть кмеегся некоторая электрическая цепь 3, представлявшая собой набоР двУхполюсных элементов аь ..., о (напРимеР, сопротязлеияй, конденсаторов. индукпшносгей, нсточннков ЭДС и зю т. д.), соедннекнмх проводниками. 1!оставим в соответствие электрической непн 5 мульт«граф 6 = 0(5). Для этого кажаому Вму узлу соеднненнй элементов цепи поставим в саотаетствне вершину аь а «аждому элементу ас — ребра кь соединяющее саетветствуюшпе вершина. Вссде аронзес ыо орннпюшю яс робряя ну,атнтрзфа О. В резул тсш ю пул нгр фа о еолучн«аркентн]анап«ма ну юнгрзф О дуга *',, ., з дда «емдою о прс 1 1, ..., ю сбозпэчнь щмп 1, зплнч у ток», ерз д ш то срез эща«шт ас, с щрез О, пм рпксн«с пп«ду по юса н ш ппе аь Пспеюьку к рязленне тока зарсеш прелсксзать е с да зш.
мак«о, а зседпшую щмепсшл ю ез рсбрск мульт щзп]п О фшм рзсс ст. резать нзк услосн«е на раююн«н тако Тагла после пределення 1, спек э ое зелнч ам ложтппш на ястннеое спрас вше тою ло з е«ппу а, (где сш(1,..., Ц. й слшачю з«ая «елнчн и и тзю е ауле оеределзться ембренюй ар«анан«ей нл ребр яь е «плю: «ад Рс будем понимать ш. л чнну. получз «у зтз «з шел и« астстяуюшсто Ичыг луг» з'. сом«несла поппи, саоташстщюше о иену О 1 гшВ,..., ш]).
Цр, М 1 (гь....г ], О (Р,,..., П ) матчам такое н напр«нюс й а злш у«четкой ксп 3. Дзм зюб«к еекюр» А (Аь „А ], В (Вь ..., В ) нэ Н яшде Г е (А, й] - 2 АВ, — ар и ек пщ А. В. Ес р — пронззс ьнпй пнкл ультпср фе О, «з юглз ю 3 кону Юююо фа лля ереме«не п ем (С(а), П] а. Но « да УС гпа (С. 6) =6.
(4.36) г У напевна (4.36) относительно 6 нааыванпся рраапспиямн яр«лафа для напряжений. Прн атом систему уравненнй С(0) 6 6 (4.37) булем назмвать балис«ой системой уравнепнй Кнрхгофа йля напряжений. Поскольку ранг матрицы С(6) равен колнчесгву уравнений в (4.37) (см. занечанне 442), то онн ли«аппо паюансомм (т. е нв одно яз уравнений спстеше (4.37) яе яалпегся линейной «омбннацней других уравненнй этой система).
С другой стороны, по определению С(6) любое урввяенкс из (4.36) являетсн линейной комб«нацией уравнений базисной системы (4.37). Из указанных свойств базисной системы уравнений слсауег, что для расчета электрнческой цепи удобнее не«го пользоваться банковой снстемой уравневнй Кнрхгофа для аапряженнй. Пример 433. Определим базнсную систему уравяеннй Кирхгофа длн нвпряженнй для элелтрыческой цепи 8, скема которой представлена на ряс.
4.33,а. Электрической цени 5 саотвегствуег граф 6, иэображепнмй аа рнс. 433,б, где ребро х, соответствует сопротивлению г, арн з 1, 2, 3, 4, б, в ребро х, — нсточнаку ЭДС. Введем орнсята. цню на ребрах графа 6. В резуньтатс получим, например, ор. граф Р, показаннмй на рвс. 4.33,е. Выделим останков перона 1 графа 6 (см.
юображенне 1 на ряс. 4.33,г). Используя алга. рнтм 4.3, апределнм цккновой базис графа 6. Прн вмделенян ас. тонного дерева 1 нз графа 6 было удалено всего трн ребра! пь ха хс, поскольку т(0) 3 (онц покаэанм пунктнрнммя линя. ЖА р. и) 43 Ю г) ями на рис. 433,»). х»збавляя поочередно к Т каждое из геречисленнмт ребер и вьшеляя из получаемого таким образом графа простой цикл, имеем циклы !И = О»Х П»Х»О»Х»ОП И О»Х»о»Х»о»Х»О»; а» = о»х»о»хчп х»о», составляющие циююаой базис графа и. Выпнше»» соответствующие им вектор-циклы; С(!и) (1. !.
О, О, О, 1): С(!ы) (О, О, — 1, 1, О, 1); Сол ) (1, О, 1. О, — 1, О). Тогда о о о: С(и]= О О; — 1 1 О! 1 О,!Π— 1::О) н при »том базисная система уравнений Кирдгсфа лля напряжений С[С)и=О имеет вид и,+и,+и,-о; — и.+и,+и,=о,' и,+й» вЂ” и,=о. Заиегим, что столбцы иикломатической матрицы С(б), соответствующие ребрам хь х». х», не вошелшим в Т (они выделены пунктирными линиями), образуют диагональную квадратную матрицу порядка ч(6), зле»»опты главной диагонали которой принадлежат множеству ( — 1, 1) (см. замечание 4.43), а следователыю, переменные и», и», и», соответствующие ребрам х», х».
х». летно выражаются через остальные переменные: и — и» вЂ” и; и. = и.-иы (4.33) и.= и»+и..' Переменные В» (3», ()я в снстеме уравнений (4.33) называются базис»мм», а (гь Вя, Вя — слобод»жми. Заме»плие 4.44. В ряде случаев прн расчете электряческвх цепей, нспользу» выражен»е базисных переменных через свобод° мс, мы можем существенна сократ»ть общее число нензвсст° ых.
Такая возможность »местов, например, в случае, когда элементами электрической пыта являются лвшь источники ЭДС н со»разве»синя (см, зэлачу 3.30). 4.3.3. Уравнения Кнрхгейю для токов Для рвсяета электрической ценя олнят уравнений Кмрхгсфа дл» напряжений недостаточно. Рассмст)им уравнения Кирхеофл дзя мгка. Пусть, как я ранее, э.|ектркчсснсй цен» В поставлен в соотвсгстьне нули»граф 6, которому в свою очередь после ввс»енэ» арнентацнн на ребрак соответствует некоторый орнентнрованный мультпграф Л. Уравнен»я Кврхгофа для тонов составляют относительно каждой вершины арнентнроеанного нуль.
тнграфа В. Эт» уравнении математмческн выражают тот факт, что прк установншпемся процессе в электрнческой цецн 5 сумма входящих в некоторый узел этой цепи токов ранна сумме тоюж, выходящих нз него. Но тогла с учетом условных направлен»й токов, определяемых ор»ентнроавнмым мульт»графом В, система всех уравнений Кнрхгофа для токов в цепи 8 имеет внд В(В)1 = О, гле В(В) — матриц»»нцндентности ориентированного мульти- графа О. Пример 4.34.
Определены совокупносш уравненнй Кнрхгофа лля тонов в юяектрвческой цепв, приведенной» примере 423 (сн. рпс. 4.33,п). В ссотвегствнв с выбором орграфа В, опнсаняым в примере 4.33 (см. рпс. 4.33, э), получаем — О ! О О ! — 1 О О 1 О В(В)-~ О 3 О 3 Π— 1~. ΠΠ†! — 3 †! О Тогда с»степа уравнений Кнрхгсфа для гоков В(В)1 О имеет анд — 1я+1 +1 О; 1 — !я+6 О; 1+1 — 1 О; — 1з — 1я-Д- О. Нз определения матрицы В(О) слслует, что лля произволь. наго ориентированного мультиграфа О сумма всех строк магри.
цы В(О) дает нулевую строку, а следооательво, любая строка матрицы В (О) является линейной комбинацией остальных строк Таким образам, нз системы уравнений Кирхгсфе В(О)1=0 можно исключить любое уравяенис и пОлучить ари этом систему, равносильную исходной, поскольку исключенное уравнение является лвиейгюй комбинацией оставшихся. Возникает зопрссг будет ли после исключсии» алного уравнения ш В(О)1 0 остаошаяся система уравнений линейно независимой? Нилы будет показано, что если О О(5) — связный мультиграф, та исключение олпою уравнения нз системы В(О)1 = 0 уравнений Кирхгафа для токае в электрической цепи 5 дает линейно независимую систему уравнений. Цля доказательства этого факта иам потребуются следующие утверждения. Утверждение 4 47.11усть Т=(У, Х) †дере, гдг У= (оь ...
..., о ), Х (хг, ..., к -г), имй Тогда персиумероцией ребер и гспшии е Т всегда молов дсбитьсл тово, пабы падмитпиаа матрицы В(т), ягляюившг» рсзугшогом игхгючгиил из В(т) переса строки, бала «годратнод могпицей порядки л — 1 гргугольиого вида с нулями гюд глегпол дипгаиагью и г единицами иа главной дьагаиали. Унажем правила сереиумерация вершин и ребер в Тг 1(' = 1 разбиваем множество вершин У на иепустыс поднвожества г[о~)=(оеаУ(д(о, ог)=г), 1=0, 1, ..., Л, юе й — последний помер токай, что 0'ь(ог)чьи; 2) нумеруем вершины из У: начинаем с вершины из йг,(ш), затеи перехолим к вершинам из 00(о,) и т. л, п закан пгваем вершинами из йуг(о,); 3] ставим е соответствие «ажлой вершине о„м, где )ш[1, ..., я — 1), ребро х! (относительно новой нумерации ребер) по следующему правилу.
Пусть ц — простая цепь в Т, соелоияюшая с, с ог+ь ог — вершина, непосредственно прелшествуюшея вершине о!+с в этой цепи. В силу правила 2 имеем 1(у+1. Обозначим х; = (оь ог+,). Действуя такич образом, зэнумеруем л — 1 ребро дерева Т, т. е. все его ребра (очевидно, по мы пе можем алка в ю же ребро пронумеровать более одного раза).
В результаю перенумерации верюин и ребер дерева Т получаем иовое дерева Т; изоморфное Т, такое, что каждый )-й столбец матрицы В(Т') (где 1<:)ши — 1) имеет единицу в (1+ 1)-й строке, а также в олной из предшествукэцих строк [см. правило 3). На тогда после удаления иервай строки из матрицы В [Т') получаем квадратную магри!!у порядка л — 1 треугольного вила с нулями под главной диагональю и с единицами на главной диаюиали. Пример 4.36. На риц 4.34,а изображено дерево Т, а па рис. 4.34,6 — дерева Т', полученное из Т перенумерацией ребер и вершин согласна правилам 1 — 3.
В табл. 4.10а и 4.106 прнвме- ТЛ вм ссотееютвснво Вгт) и В(Г). При этом, если удалим на В(Т') первую строку, то получим квадратную мачрипу треугсль. ного вида с нулями под главной двзгоналыо и едниияамв на главной диюоналн. и' г,) к кт б М г'ц) ек ь к, )ге (ц) —— г) а) Из утверждения 4.47, а также яз того очевидного факта, чпк если С вЂ” мультиграф, П вЂ” ориентированнмй мультнграф, по. лучаеммй из С введением ориентаяии на ребрах, то элемеьтм матрнам В (С) являются абсолютнмми величинами ссствегстзуююих элементов матриам ВЩ, слезует, что справедлию Утверждение 4АВ. Пусть Т вЂ” дерево с ажй еерюинама, Ю— оргрвф, лолучоеммд из Т ееедением ориентации на ребрик дереза Т.
Тогда лерьнумерагумб еериш» и дуг е О всегда макни добиться того. чтпбм нодматрица матрица Втд), яеянюиуиюя ре тасе аз акое теснине егсо вультагпм сс лючсниэ ьз В(О) лерзоа строки, была квадратной матрицед гюрядка л — 1 треуюльнпго вида с мулевыли зланектами под главной диамиалью и элементами из мнпжества ( — 1, Ц на глимюв даамиалк Иь утверждения 4.48 с учетом топь, что ранг мвтрнпы не меняется от перестановки строк в столбцоц слеаует, что снравыглнво Утвервщевне 4.49. Пусть Т вЂ” дерево с лм2 есрюилвмц О— орграф. полученный из Т введением ориентации на ребрах дерева Т.
Тогда гюдг В(О)=п — ! (еде ладг В(О) — ранг матрицы В(О». Покажем теперь, что справедлнэо Утвсрвщенне 4ЛО. Пусть С вЂ” сввзныд мультигрпф, Π— ориекгмровюигый мультиграф, лолучгнныа из С введением ориенюции на ребрах мулвтиерлдю С. Тогдаг П галаВ(О) =л — 1; 2) «склгочение из матрицы В[О) произвольной стрпки дает матрацу рюма л — !.
Донвжсм сначала справеллнвость первого утверждения. Поскольку, как уже отмечалась ране», сумма всех строк матрицы В(О) дает нулевую строку, имеем гааКВ(О) ы л — !. '(429) С другой сторонщ согласно утверждеюпо 4.49 ранг педиатры. цы матрнцм В(О), составленной пз столйюв матрнцм В (О), номера погорых ыютвсгствуют номерам ребер мультнграфа С, солержащпхсн в некотором астаиюм дереве мультнграфа С. раве» к — 1, а снсаокттельно, гапй В(О) ~л — 1, вкупе с учетом (4.39) получаем требуемое равспспю. Докажем теперь справедливость второго утвержденна. Преп В'(О) — матрица, полученная нэ В(О) после исключения ненотарой 1-9 стропы. В этом случае гапКВ'(О) щгапКВ(О) л — 1. Предположнм что гэпКВ'(О) (л — 1. Тогда некоторая >-я отра«в матрвшг В (О), содержащаяся в В'(О) (т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
