Элементы теории графов. Сюсюкалов А.И - 10 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

Составители: 

Рубрика: 

6
Д о к а з а т е л ь с т в о. Необходимость. Пусть
G
– дву-
дольный граф,
C
– один из его циклов длины
k
. Пройдём все
рёбра этого цикла в той последовательности, в какой они в нём
расположены, начиная с некоторой вершины
v
. Так как концы
каждого ребра лежат в разных долях, то
k
– чётное число.
Достаточность без доказательства.
Определение 1.22. Двудольный граф, у которого каждая
вершина одной доли соединена ребром с каждой вершиной дру-
гой доли, называется полным двудольным графом.
Полный двудольный граф, доли которого состоят из
p
и
q
вершин, обозначается
qp
K
,
. На рис. 4 изображены некоторые
полные двудольные графы. Граф
p
K
,1
называется звездой.
Полный двудольный граф
qp
K
,
имеет
q
p
рёбер.
Теорема 1.8 (о сумме степеней вершин двудольного графа).
Суммы степеней вершин долей двудольного графа равны.
Д о к а з а т е л ь с т в о. Пусть
k
vvv ,...,,
21
– вершины одной
доли, а
p
uuu ,...,,
21
– вершины другой доли. Тогда из одной до-
ли выходит
k
vdvdvd ...
21
рёбер, а из другой –
p
ududud ...
21
рёбер. Равенство сумм следует из того,
что это одни и те же рёбра. Теорема доказана.
Граф
G
, имеющий
n
вершин и
m
рёбер, представляется
матрицей размером
m
n
, называемой матрицей инцидентно-
сти. Строки матрицы соответствуют вершинам, а столбцы –

Страницы