Теория графов и комбинаторика

Т«ог^бмв 5.4> Если i-pay О- аквет матртату чшаов С и тгат- рщу икдпдещпй В , то С Ь - Q C w o d S y ) . Докада-гедьотво. Внчиолмм ( t , J ) - 2 эламент (С& )•,матрицы С& .По правилу умноя0.ч:;я мятац имеем (СВ^),у .= ^ См^^к . Слагаемое C^ k ^J k '^O, воли когда ребро к прякадаени'г i -щ Ц!: к.ту Z С ч пьщмдантно вериннэ . Еолп Xf^ то ё . Следовательно, uM l 11МЭ0ТОЯ два pedpa,' ИЕпддектных вордлгке образом, а оуша 2Г. <^ск -^4к I :mq9. К даа слагаемых, рашых ! , и поэ­ тому (С"^~ j-i-i =О {w\d4 ?^) . Матрицы цкмов орграфов опрелеляются олодующям образом. Пуоть <? =0 А Г -орграф; <?'=.(V'', ^ осноаашге орграфа <7 ; й/, , C~iyWi ~ проо'ши Ц1:№' графа G . Езля дет й'гк Г п некоторого ребра .С в:--/олпяеток условиеУй X , то говорят, что С ;5 ооотчетствуют друг другу. 1ля краткос­ ти будем roBOiMTb, что дуга принадл^киг ""ч:'лу.2{( f e i i ) , оолп E)XOMj' ит-лу прпЕЯД/хекят podpo JXi , ооотвотс!Г1)у1.)Щйа даго Г - Ка-хдиЬ цчкл иогпо оркектировать двумл crrooc6ai.i:i: iro тсаоо- Boli клг. против чаооЕОЙ стрелки. ГГуоть = (Р1, I ворг-гш встрвчаегоя при обходе цикпа Z(< - в нaIIpaгJлeIши , указанном его оривЕтациой, раньше зерьтиш . Тогда говорят, что ор;10ктац!!я д у г иТ ' . соответотгует ориентации цикла £ к . Матрицей циклов орграфа / Р к.эзываотоя матрица С~ (!С0'= - 1 отроки Которой соответотвуат циклам 2 к , , а отол/ды дугам -й элемент'^^^ ра­ вен г О, Т: j I , ориентация ^ Ооответствуат ^ . _ у оркентацз'Л • J V j - I . T j <r H орцектацпя на ооответот- V ВУЙ! ОРИВНТАЦТТА i{, . ГЛАВА 6 . ОПЕРАЦИИ НАД ГРАФА.® В §2.2 уяв ошп! ввадеш операции удаления и добавления вершин и pedep. Опредалкы новые оиерацип над графами, которив позволят выражать сложные графы через простна. ПУСТЬ ЕЧ=-С\/КХ<)> , IKil=i4il^b/%Ai-l=h- Еолн графы (?< pa осматриваются о точностью до изоморфизма,- -Г. 37