 |
Матрицы смежности и инцидентности
Пусть D=(V,X) ориентированный граф, V={v1,...,vn}, X={x1,...,xm}.
Матрица смежности ориентированного графа 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={v1,…, vn}. Обозначим через 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={v1,…, vn}, A(D) – его матрица смежности. Тогда
1) T(D)=sign[E+A+A2+A3+… An-1],
2) S(D)=T(D)&TT(D) (TT-транспонированная матрица, &- поэлементное умножение).
Пусть G=(V,X) – граф, V={v1,…, vn}, A(G) – его матрица смежности. Тогда
S(G)=sign[E+A+A2+A3+… An-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.
Решение контрольных задач
