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

1 . ПроБзрка. Теорема, очавидно, оправедлмва при И-1 . Это прямо олелузт и з определения матрицы омеетости графа. 2. Индуктивное предполо-'сонио. Допустим, чпо теоромгз спра- велливгз V ^ К , 3 . Ин,^ривный шаг. Пуоть V0= K-f-l . Зкчколим элементЙ £ ^ маттацы А * = • А . П о правилу умножения магркц получим: CRH) ^ .CKJ » „ t в о 0 1 ы ~ МНО- жеотво номеров -вершин омеишшс о . В поС-тЕедной оумме нуле­ в о й йудут те олагаемыа, для которых •§ - И » » i - Do воех оотгзльных олагаешх Лл, (".=•/ , -1 = -i.Yt . Поэтода л (iKti J ч - Z 1 - Полученная оуша равна чиолу(1^—l/Jj- маршрутов лДины K+i , ^ а к как по индуктавному предполозкению каждое и з олагаемых равно чполу ( 1/i;, — ) -карш- Вутов длигш К , а каждый "акой -•ар-'фут может бнть продолкен до вершины добавлением ребра ( Ь СлздотЕиз I . ( L,j . ) -й элемент матрицн _(лри ) равзн чполу проотых (г^--1^)-цвпзй длина 2 ; -й элзмзнт матрицы А ^ равен отепени с((1Гс) вершины t i ; . Слздотвие 2. Раоотояниа J (iTi , ТГ^ ) меаду вершинами "Л' и V j графа (х равно наименьшему пз целых таоел И , для кото- / * * \ м i ^ р н х э.чемеят л ; ; матрицы А отличен от нулл,т.е. :^метим, что еоли граф (? овязный, то Отоюда оледует, что утверждение оледотвия 2 может йнть положено в оонову алгоритмов проверки овязнооти графов и отыока!шя рао- стояний^ меяоду вершинами. Теорема 5 . 3 . Граф & =(V,Х ) не овязный тогда и только тог­ д а , когда существует нумерации в е р м н , при которой-матрица смвж- ноотн А W ) имеет квазидиагональный вид. Примером такой нумерации является "сквозная нумерация вер­ шин графа с переходами к следующей компоненте, когда вое вер­ шины предыдущих компонент уяе перенумерованы. Поллов доказатель- отво этой теоремы предлагается читателю в качестве упражнения. 55.3. Мвтриш омэшооти ^тvльтиnзaйoв. псовдогпаФов, ОРГРЙ ^ ЮВ По аналогии о предыдущими параграфами могут быть введены понятия матриц дта.мультпграфов, поввдогра|юв и орграфов. Матрицей смежности мультиграфа & , имеющего р вершин, .НЕЗнвается квадратная матрица типа рлр , -2 элемент которой й-i^ равен таолу кратных ребер, ооедпняввдх вершины и 1^- , . • • , . • 3 5 '