Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Матрицы смежности и инцидентности




Пусть D =(V, X) ориентированный граф, V ={ v 1,..., v n}, X ={ x 1,..., x m}.

Матрица смежности ориентированного графа D − квадратная матрица

A (D)=[ aij ] порядка n, где

Матрица инцидентности − матрица B (D)=[ bij ] порядка n ´ m, где

Матрицей смежности неориентированного графа G =(V, X) называется квадратная симметричная матрица A (G)=[ aij ] порядка n, где

.

Для ориентированного графа

 

Матрицей инцидентности графа G называется матрица B (G)=[ bij ] порядка n ´ m, где

 

Связность. Компоненты связности

Подграфом графа G (ориентированного графа D) называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G (D).

Подграф называется собственным, если он отличен от самого графа.

Говорят, что вершина w ориентированного графа D (графа G) достижима из вершины v, если либо w = v, либо существует путь (маршрут) из v в w.

Граф (ориентированный граф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.

Компонентой связности графа G (сильной связности ориентированного графа D) называется его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (ориентированного графа D).

 

Матрицы достижимости и связности

Пусть A (D) – матрица смежности ориентированного псевдографа D =(V, X) (или псевдографа G =(V, X)), где V ={ v 1,…, v n}. Обозначим через Ak =[ a ( k ) ij ] k -ю степень матрицы смежности A (D).

Элемент a ( k ) ij матрицы Ak ориентированного псевдографа D =(V, X) (псевдографа G =(V, X)) равен числу всех путей (маршрутов) длины k из vi в vj.

Матрица достижимости ориентированного графа D − квадратная матрица T (D)=[ tij ] порядка n, элементы которой равны

Матрица сильной связности ориентированного графа D − квадратная матрица S (D)=[ sij ] порядка n, элементы которой равны

Матрица связности графа G − квадратная матрица S (G)=[ sij ] порядка n, элементы которой равны

Утверждение 3. Пусть D =(V, X) – ориентированный граф, V ={ v 1,…, v n}, A (D) – его матрица смежности. Тогда

1) T (D)=sign[ E + A + A 2+ A 3+… A n-1],

2) S (D)= T (D)& TT (D) (TT -транспонированная матрица, &- поэлементное умножение).

Пусть G =(V, X) – граф, V ={ v 1,…, v n}, A (G) – его матрица смежности. Тогда

S (G)=sign[ E + A + A 2+ A 3+… A n-1] (E - единичная матрица порядка n).

 

Расстояния в графе

Пусть - граф (или псевдограф). Расстоянием между вершинами называется минимальная длина пути между ними, при этом , , если не пути.

Расстояние в графе удовлетворяют аксиомам метрики

1) ,

2) (в неориентированном графе)

3)

4) в связном неориентированном графе.

Пусть связный граф (или псевдограф).

Диаметром графа G называется величина .

Пусть .

Максимальным удалением (эксцентриситетом) в графе G от вершины называется величина .

Радиусом графа G называется величина

Центром графа G называется любая вершина такая, что .

 

Образ и прообраз вершины и множества вершин

Пусть ориентированный граф - некоторая вершина .

 

Обозначим - образ вершины ;

- прообраз вершины ;

- образ множества вершин V1;

- прообраз множества вершин V1.

Нагруженные графы

Нагруженный граф − ориентированный граф D =(V, X), на множестве дуг которого определена некоторая функция , которую называют весовой функцией.

Цифра над дугой (см. рис. 5)− вес дуги (цена дуги).

Рис. 5.

Обозначения: для любого пути П нагруженного ориентированного графа D через l (П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути.

Если выбрать веса равными 1, то придем к ненагруженному графу.

Путь в нагруженном ориентированном графе из вершины v в вершину w, где v ¹ w, называется минимальным, если он имеет наименьшую длину.

Аналогично определяется минимальный путь в нагруженном графе.

Введем матрицу длин дуг C (D)=[ cij ] порядка n, причем

Свойства минимальных путей в нагруженном ориентированном графе

1) Если для " дуги , то " минимальный путь (маршрут) является простой цепью;

2) если минимальный путь (маршрут) то для " i, j: путь (маршрут) тоже является минимальным;

3) если − минимальный путь (маршрут) среди путей (маршрутов) из v в w, содержащих не более k +1 дуг (ребер), то − минимальный путь (маршрут) из v в u среди путей (маршрутов), содержащих не более k дуг (ребер).

 

Деревья и циклы

Граф G называется деревом если он является связным и не имеет циклов.

Граф G называется лесом если все его компоненты связности - деревья.

Свойства деревьев:

Следующие утверждения эквивалентны:

1) Граф G есть дерево.

2) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.

3) " две различные вершины графа G можно соединить единственной (и при этом простой) цепью.

4) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл

Утверждение 4. Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.

Утверждение 5. Пусть G связный граф, а − висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n (G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер.

Число называется цикломатическим числом графа G.


Решение контрольных задач

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...