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

•.!? сг;г4еП лйо т аикй графа <? Еазнваетоя прямоугольная b(G) типа - cxpojra коа-орой соотаетствуют вврша- нааГа отслйаи рейрам графа & , прячем (С,^ ) -й элемент sio5 aaiTCXW равен , _ Р . - ) I • ^ яйЦ'ЗДвнтна Л-у ; Н " ( . о , в противном олучае. Сзжгяы, что 2КД матриц п 8С(?) завяоит от нумерации ЕзрцяГи'рэбар графа G . Предагаем доказать проотое утверж­ дение, что матрицы смежнооти Л инцкдэндий 6 ( t f j овяза!1Ы_ .^ooTEOisifflew/4 = &Ь - г д е Д(.' - « f ) / " ( > / ' > Тек как какдое ребро графа шгцэдентно двум разным варши- „аа, то каудай столбец матрицы шшд ещий содар)г.йТ ровно два едиштеных элемаята, т . 9. ^ ° -=• ^ .Из оа~ рвделзния матр1;цк6{;<г) смруат также, тго любая отрока матри­ цы &С(г) pai?Ha сумме но модул» 2 всех осте ты.;'/": отрок, т.е. V i , i fc - S t ^ 4 C ™ J A ) , Ойооновашта применения этях матри; для описания графов служит оледуэщая Теотема 5.1. Матрица /ff-tr М определяет граф с точностью до 51зомор|.гчма. Утварж,цвние этой теорамы надо понимать так. что воли г р а - <FS[ О Е Н изоморфны ( ( г И ), то сущеотвуют нумерации их BejfflBH, при которнх матр.щы ЛС"? ) иДСИ) совпадают (Л (б^}=/1(Н)), и обратно, если графн (5 и Н чмеют "динаковые матрицы, смеж- ноота, то они изоморфны. Это же справедливо в но .отиошони:, к катрще йнцидекциЁ £ >((?). Утверздбше теоремы 5.1 отайовктоя очевидгам, с ли вер­ шины графов перенумероват так, ^гтобы ооответотвующие х. :'г другу при изоморфизме вершины имели одинаковые номэра. Из твораш S . I следует, что шдов свойство графа, не и з - нвнящееся при изоморфных пвеобразованиях, может быть огоюано о помощью матриц А ( ^ ) и^л Ь . §5.2. Некоторне возможности применения маттагт омнжнооти Т^орвн^ '^,2. Чиоло маршрутов длшщ оо'диаадщих в и рш- ни Vi. й1^' графа ^ =(\/,X ) « равно D-My элементу матргшу д" . Здесь Д - Я - я степень матрицы омежнооти = rpaja (?. Докаватвльогво щюведем индакцией по дайне маршрута Y\,