Дискретная математика. Громов Ю.Ю - 60 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

60
Изучая свойства циклов какого-либо графа, можно определить при-
надлежность этого графа к определённому классу, например к классу
двудольных графов.
Теорема (Кёнига). Неориентированный граф G является двудоль-
ным тогда и только тогда, когда все его циклы имеют чётную длину
(чётны). ■
Так, граф G на рис. 23, а является двудольным графом, поскольку
все семь его циклов чётны. Этот же граф на рис. 24 изображён в традици-
онном для двудольных графов виде, когда множество вершин разбито на
два подмножества. Заметим, что вершины любого ребра графа G разме-
щены в разных его долях.
Если в двудольном неориентированном графе G каждая вершина из
одного множества вершин V
1
соединена ребром с каждой вершиной из
другого множества вершин V
2
, то граф G называется полным двудольным
графом и обозначается K
m, n
, где m – число вершин в множестве V
1
, а n –
число вершин в множестве V
2
. Заметим, что граф K
m, n
имеет всего (m + n)
вершин и mn рёбер.
Полный двудольный граф K
1, n
на-
зывается звёздным графом (звездой), он
не содержит ни одного цикла и является
деревом. Колесом W
n
при n
≥
3 называет-
ся звезда K
1, n−1
, у которой вершины со
степенью, равной 1, образуют простой
цикл.
Например, на рис. 25, а и б изображены звезда K
1,5
и колесо W
6
соот-
ветственно.
Задачи и упражнения
1. Определить цикломатическое число ν(G), выбрать остов D(G) и
построить соответствующую ему базисную цикломатическую матри-
цу B(G), а также построить цикломатическую матрицу C(G) представлен-
ного ниже графа G. Если граф G является двудольным графом, то изобра-
Рис. 24
a
b
c
d
e
f
g
h
m
а)
Рис. 25
б)

Страницы