8
.pdf
Теория графов
Степени вершин графа.
Определение. Степенью вершины deg(j) неориентированного графа называют количество инцидентных вершине j ребер, при этом каждая инцидентная ей петля считается два раза.
m |
|
iP1 |
aij : |
Другими словами, deg(j) = |
|
= |
|
Теорема. Сумма степеней всех вершин неориентированного графа равна удвоенному количеству ребер,
X
deg(j) = 2 jEj:
j2V
Теория графов
Степени вершин графа.
Определение. Степенью вершины deg(j) неориентированного графа называют количество инцидентных вершине j ребер, при этом каждая инцидентная ей петля считается два раза.
m |
|
iP1 |
aij : |
Другими словами, deg(j) = |
|
= |
|
Теорема. Сумма степеней всех вершин неориентированного графа равна удвоенному количеству ребер,
X
deg(j) = 2 jEj:
j2V
Доказательство.
n
P
deg(j)
j=1
Теория графов
Степени вершин графа.
Определение. Степенью вершины deg(j) неориентированного графа называют количество инцидентных вершине j ребер, при этом каждая инцидентная ей петля считается два раза.
m |
|
iP1 |
aij : |
Другими словами, deg(j) = |
|
= |
|
Теорема. Сумма степеней всех вершин неориентированного графа равна удвоенному количеству ребер,
X
deg(j) = 2 jEj:
j2V
Доказательство.
nn m
P P P deg(j) = aij
j=1 |
j=1 i=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Теория графов
Степени вершин графа.
Определение. Степенью вершины deg(j) неориентированного графа называют количество инцидентных вершине j ребер, при этом каждая инцидентная ей петля считается два раза.
m |
|
iP1 |
aij : |
Другими словами, deg(j) = |
|
= |
|
Теорема. Сумма степеней всех вершин неориентированного графа равна удвоенному количеству ребер,
|
|
Xdeg(j) = 2 jEj: |
||||||||||||
|
|
j2V |
|
|
|
|
|
|
|
|
|
|
|
|
Доказательство. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
n |
m |
m |
n |
||||||||||
jP1 |
jP1 iP1 |
iP1 jP1 |
||||||||||||
deg(j) = |
|
aij = |
|
|
aij |
|||||||||
= |
= |
= |
= |
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Теория графов
Степени вершин графа.
Определение. Степенью вершины deg(j) неориентированного графа называют количество инцидентных вершине j ребер, при этом каждая инцидентная ей петля считается два раза.
m |
|
iP1 |
aij : |
Другими словами, deg(j) = |
|
= |
|
Теорема. Сумма степеней всех вершин неориентированного графа равна удвоенному количеству ребер,
X
|
|
deg(j) = 2 jEj: |
|
|
|
|
|
|
|
|
|
|
|||
|
|
j2V |
|
|
|
|
|
|
|
|
|
|
|
|
|
Доказательство. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
n |
m |
m |
n |
m |
||||||||||
jP1 |
jP1 iP1 |
iP1 jP1 |
iP1 |
||||||||||||
deg(j) = |
|
aij = |
|
|
aij = |
2 |
|
|
|
|
|
|
|
|
|
= |
= |
= |
= |
= |
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Теория графов
Степени вершин графа.
Определение. Степенью вершины deg(j) неориентированного графа называют количество инцидентных вершине j ребер, при этом каждая инцидентная ей петля считается два раза.
m |
|
iP1 |
aij : |
Другими словами, deg(j) = |
|
= |
|
Теорема. Сумма степеней всех вершин неориентированного графа равна удвоенному количеству ребер,
X
deg(j) = 2 jEj:
j2V
Доказательство.
n |
n |
m |
m |
n |
m |
|
|
|
|
|
|
|
|
|
|
|
jP1 |
jP1 iP1 |
iP1 jP1 |
iP1 |
2 = 2m: |
||||||||||||
deg(j) = |
|
|
aij = |
|
aij = |
|||||||||||
= |
= |
= |
= |
= |
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Теория графов
Матрица инцидентности.
Пусть дан простой граф G = (V ; E). V = f1; 2; : : : ; ng:
Определение. Матрица B = (bij ) размера n n называется матрицей смежности графа G, если
(
bij =
1; если вершины i и j смежные;
0; если вершины i и j не смежные:
Теория графов
Матрица инцидентности.
Пусть дан простой граф G = (V ; E). V = f1; 2; : : : ; ng:
Определение. Матрица B = (bij ) размера n n называется матрицей смежности графа G, если
(
1; если вершины i и j смежные;
bij =
0; если вершины i и j не смежные:
Для каждого i; j 2 V имеем bii = 0 и bij = bji .
Теория графов
Изоморфизм графов
Определение. Неориентированные графы G = (V ; E) и G0 = (V 0; E0) изоморфны, если существуют биективные отображения f : V ! V 0 и g : E ! E0 такие, что
e 2 E инцидентна a 2 V () g(e) 2 E0 инцидентна f (a) 2 V 0:
Теория графов
Изоморфизм графов
Определение. Неориентированные графы G = (V ; E) и G0 = (V 0; E0) изоморфны, если существуют биективные отображения f : V ! V 0 и g : E ! E0 такие, что
e 2 E инцидентна a 2 V () g(e) 2 E0 инцидентна f (a) 2 V 0:
Для случая простых графов для изоморфизма достаточно существования биективного отображения f : V ! V 0 такого, что
a; b 2 V смежные () f (a); f (b) 2 V 0 смежные: