Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Матица достижимости неориентированного графа.




Читайте также:
  1. Блок-схема осциллографа.
  2. Деревья. Остов графа. Цикловой базис графа
  3. Малюнок № 1.19. Задання декартового добутку множин за допомогою графа.
  4. Матрица инцидентности неориентированного графа.
  5. Матрица инцидентности ориентированного графа.
  6. Отступление историографа. Земельный вопрос
  7. Представление графа. Транзитивное замыкание
  8. Связность графа. Компоненты связности. Матрица связности
  9. Цифрового запоминающего осциллографа.

Утверждение. Если А – матрица смежности графа , то элемент матрицы Ап равен числу маршрутов длины п, соединяющих вершины vi и vj графа G.

Доказательство. Методом математической индукции по числу п.

База индукции. При п = 1 утверждение верно, так как всякое ребро графа G – это маршрут длины 1.

Индуктивное предположение. Пусть утверждение справедливо для всех n £ k.

Индуктивный переход. Рассмотрим матрицу Аk+1. В ней .

В силу индуктивного предположения произведение есть число маршрутов длины k + 1, соединяющих вершину vi с вершиной vj с предпоследней вершиной всех таких маршрутов - vm. Значит, сумма действительно равна числу маршрутов длин k + 1, соединяющих вершину vi с вершиной vj.

Следствие. Пусть – связный граф с р вершинами. Тогда любые две вершины графа можно соединить простой цепью. Но в простой цепи не может быть более (р - 1) ребер. Следовательно, все элементы матрицы отличны от нуля. Ясно, что верно и обратное утверждение.

В некоторых случаях при вычислениях степеней матрицы А и матрицы С важно знать не число соответствующих маршрутов, а только есть ли в графе эти маршруты или нет. Тогда при вычислении элементов матриц А2, А3, … , Ар-1 вместо обычного сложения используют операцию Å, введенную нами при рассмотрении матриц конечных бинарных отношений. В результате матрицы А, А2, А3, …,Ap-1, C состоят только из нулей и единиц.

Полученная таким образом матрица С называется матрицей достижимости графа G. Граф G связен тогда и только тогда, когда каждый элемент матрицы достижимости равен 1 (р ³ 3).


Дата добавления: 2014-12-03; просмотров: 12; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты