Студопедия

КАТЕГОРИИ:

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


Свойства матриц смежности и инцидентности




1. Пусть G=(V, X) – мультиграф (V={v1, …, vn}). Тогда сумма элементов матрицы A(G) по i-ой строке (или по i-му столбцу) равна .

2. Пусть Д=(V, X) – ориентированный псевдограф (V={v1, …, vn}). Сумма элементов матрицы A(Д) по i-ой строке равна , сумма элементов по i-му столбцу равна .

3. Пусть Д=(V, X) – ориентированный мультиграф. Тогда

а) сумма строк матрицы B(Д) является нулевой строкой;

б) любая строка матрицы B(Д) является линейной комбинацией остальных строк;

в) rang B(Д) n(Д)-1 (n(Д) – кол-во вершин);

г) для любого контура в Д сумма столбцов матрицы В(Д), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.

4. Пусть G – мультиграф с непустым множеством ребер. Тогда при покоординатном сложении по модулю 2:

а) сумма строк матрицы В(G) является нулевой строкой;

б) любая строка матрицы B(G) является суммой остальных строк;

в) для любого цикла в G сумма столбцов матрицы B(G), соответствующих рёбрам, входящим в этот цикл, равна нулевому столбцу.

Обозначим через Ak=[aij(k)] – k-тую степень матрицы смежности A.

Утверждение 1. Элемент aij(k) матрицы A(k) ориентированного псевдографа Д=(V, X) (псевдографа G=(V, X)), где V={v1, …, vn} равен числу всех путей (маршрутов длины k) из vi в vj.

Утверждение 2. Для того, чтобы n-вершинный орграф Д с матрицей смежности А=А(Д) имел хотя бы один контур, необходимо и достаточно, чтобы матрица K=A2+A3+…+An имела ненулевые диагональные элементы.

Утверждение 3. Для того, чтобы n-вершинный ориентированный псевдограф Д с матрицей смежности А=А(Д) имел хотя бы один контур, необходимо и достаточно, чтобы матрица K=A+A2+…+An имела ненулевые диагональные элементы.


Поделиться:

Дата добавления: 2015-01-29; просмотров: 123; Мы поможем в написании вашей работы!; Нарушение авторских прав





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