- •Матрицы графов и их свойства.
- •Матрица смежности орграфа
- •Матрица инциденций.
- •Для любого реберного (p,q) графа G с матрицей инциденций В
- •Построим граф:
- •Пример операций над
- •Пример:
- •Матрица С не определяет однозначно граф G. Оба графа имеют цикл:
- •Если граф G имеет матрицу инциденций В и матрицу циклов С, то
- •Задача:
- •4) Композицию G1[G2] и G2[G1]
Матрицы графов и их свойства.
Матрица смежности.
Матрицей смежности (смежностей) А=||aij||
графа G с p вершинами называется (рxр)
матрица, в которой |
аij = 1, если вершина |
|
υ смежна υj, и аij = 0 |
противном случае. |
|
Итак,i |
существует взаимно |
|
однозначноесоответствие между графами с |
||
р вершинами и симметрическими |
бинарными (рxр) – матрицами |
|
с нулями на |
||
|
||||
главной диагонали. |
|
|
0 11 0 1 |
|
|
|
1 0 1 0 0 |
|
|
|
|
|
|
|
|
А |
|
11 0 11 |
|
|
|
|
0 0 1 0 1 |
|
|
|
|
1 0 11 0 |
|
|
|
|
|
|
Суммы элементов матрицы А по строкам равны степеням вершин графа G (ρ(1)=3, ρ(2)=2, ρ(3)=4, ρ(4)=2, ρ(5)=3.
Матрица смежности орграфа
определяется аналогично: А=А(Д)=||aij||, где аij = 1, если дуга υiυj принадлежит Д, и аij = 0 в противном случае. Итак, А(Д) не обязательно симметрична.
Матрицу смежности данного графа можно рассматривать как матрицу смежности симметрического орграфа.
Линейным подграфом орграфа Д называется подграф, в котором у каждой вершины полустепень исхода и полустепень захода равны 1. Таким образом, такой подграф содержит непересекающийся набор простых контуров.
Остовной подграф - подграф графа G, содержащий все его вершины.
Матрица инциденций.
Матрица инциденций определяет граф с точностью до изоморфизма.
Теорема с связи матрицы смежностей G и матрицы инциденций G. Пусть ВТ – транспонируемая матрица к В.
B=||bij||, размерность nxm (n вершин, m дуг). bij = 1, если xi является начальной
вершиной дуги aj.
bij = -1, если xi является конечной вершиной дуги aj.
bij = 0, если xi не является концевой
Для любого реберного (p,q) графа G с матрицей инциденций В
А(где(G))Iq= –BTединичнаяB-2Iq, матрица порядка q. Имеется в виду реберный граф (G) все вершины которого взаимно однозначно сопоставлены ребрам графа G, причем две вершины в (G) смежны тогда и только тогда,
G:
11 0 |
|
|
|
11 0 |
|
||
|
|
|
ВТ |
|
|
|
|
 1 0 1 |
|
1 0 1 |
|
||||
|
|
|
|
|
|
|
|
0 11 |
|
|
|
|
0 11 |
|
|
|
11 0 |
|
11 0 |
|
|
2 11 |
|
|
|
|
|
|
|
1 2 1 |
|
ВТ В |
1 0 1 1 0 1 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 11 |
0 11 |
11 2 |
|
Построим граф:
Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент, равный 1, и один, равный -1, либо все элементы столбца равны 0.
Если G – неориентированный граф, то его матрица инциденций определяется также, за исключением того, что все элементы, равные -1, заменяются на +1.
Обобщение на случай мультиграфа:
А=(aij)n,n, aij = числу ребер в G, соединяющей Vi и Vj
1 1 1 0
1 0 2 1
1 2 0 10 1 1 0
V1 |
1 0 |
0 |
|
|
|
0 1 |
0 |
|
|
V 2 |
|
|
||
|
|
1 |
|
|
V 3 |
1 1 |
|
||
V 4 |
|
0 0 |
|
|
|
1 |
Пример операций над
ОбъединениеграфамиG1 G2. - граф с множеством вершин V=V1 V2, а множество ребер Х=Х1 Х2.
Соединение графов: G1+G2 состоит из G1 G2 и всех ребер, соединяющих V1 и V2.
G1+G2:
Если G - связный граф, то nG с n компонентами, каждая из которых
Пример:
Произведение G1xG2. Рассмотрим 2 вершины
U=(
V=
Композиция G=G1[G2] также имеет V=V1xV2 в качестве множества вершин и вершина U=(U1,U2) смежна с V=(V1,V2) тогда и только
тогда, когда [U1 adj V1] или [U1=V1 и U2 adj V2]
не
изоморфны