![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Матица достижимости неориентированного графа.Утверждение. Если А – матрица смежности графа Доказательство. Методом математической индукции по числу п. База индукции. При п = 1 утверждение верно, так как всякое ребро графа G – это маршрут длины 1. Индуктивное предположение. Пусть утверждение справедливо для всех n £ k. Индуктивный переход. Рассмотрим матрицу Аk+1. В ней В силу индуктивного предположения произведение Следствие. Пусть В некоторых случаях при вычислениях степеней матрицы А и матрицы С важно знать не число соответствующих маршрутов, а только есть ли в графе эти маршруты или нет. Тогда при вычислении элементов матриц А2, А3, … , Ар-1 вместо обычного сложения используют операцию Å, введенную нами при рассмотрении матриц конечных бинарных отношений. В результате матрицы А, А2, А3, …,Ap-1, C состоят только из нулей и единиц. Полученная таким образом матрица С называется матрицей достижимости графа G. Граф G связен тогда и только тогда, когда каждый элемент матрицы достижимости равен 1 (р ³ 3).
|