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

Доказательство. Утверхданпе п."а" оледуот из того, что изомойязм определяатоя парой взаимно однозначных ооответст- и ; п."б" следует и з теоремы 4,3; у т - верждениз я, "в" является пря1>им следотвиэм теореш 4.2 в оле- ду з т из того, что, воля ^ t / j ) _ простой цикл дай­ ны К в графе 6 , то У ,•••, ^(•^кУ, J ) ) является прротьм_цшаом дощнн К в графе Н . Таким образом, удаетоя установить- пзаишо однозначное соответствие меаду множествами простых циклов ••хлт К графов <? и Н . Установление изомор^ности графов я в л я в . т р у д с емк о й задачей. Если графы (? и Н имеют по И вершин, тс полное чис­ л о всех взаимно однозначных соответствий м а в д их мнокеотваш вершин разно И ! Перебор всех этих возможноотей весьма зат­ руднителен, а при больших "1 и >. ЗЕ ' ЗМОЕОК . У СЛОВИЯ теоремы 4 . 4 позволяют разбить мнокества вершн графов на группы и резко сократить число паребираешх вариантов. ГЛАВА 5. !.1АТКШ0Е ПВДОТАВгаЕ® ГРАФОВ Задание графа в виде пары множеств ( V tX ) оказывается н е ВПСЛН9 удобшм, особенно при ранении • задач на ЭВЛ. Рассмот­ рим тг:* называешв матричные представления графов, позволяющие описать графы о помощью числовых массивов. .. С'5.1. Мэтпшш омежнооти и инпиденпий Пусть =-,CV, У) - ?1лзф. Пврек;,жруем вершин и ребра: , Х ={ х , , а ; ^ , i , Матрицей смежности графа называется квадратная .матри-" ца А№) порядка р , C^,J) -й элемент которой определяатоя фор­ мулой , • . , di-, - 4 ^ ' в. t в противнем случае.. Матрица А(6^) сйладает следующими проотейшклш овойотваки; I ) Ai^) ~ симметричная матрица ( А = Л )• Зтс следует из_ симметричности отношения омекнсоти вершн в ^ ф э х ; 2)Vt^<jp С - (? ) 1 граф не содергат петель; Z-^Ц ~ ^ Действительно, число единиц в ^-й отроке матри11ы рявяо ЧЕолу вершин смежных о , т . е . равно отвпснн j-sepiunro iTc. 33