Дискретная математика. Прокушев Л.А. - 11 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

9
поскольку пара вершин v
i
и v
j
соединяются одинаковыми ребрами [v
i
,
v
j
] =
=[v
j
,
v
i
], т. е. достаточно рассматривать только половину матрицы выше
главной диагонали. Очевидно, что матрица смежности графа без петель и
кратных ребер является булевой матрицей, состоящей из нулей и единиц.
Раздел 4. Основные понятия неориентированного графа
Абстрактное описание; степень вершины; разбиение графа на составля-
ющие части; маршруты и циклы; связность графа; разновидности графов.
Литература: [1, c. 10–21].
Пусть V – непустое множество вершин графа v ∈ V. В неориентирован-
ном графе ребром, соединяющим две вершины v
i
и v
j
, называется неупо-
рядоченная пара [v
i
,
v
j
] или [v
j
, v
i
], при этом ребро обозначается
u
= [v
i
,
v
j
].
Множество ребер является конечным подмножеством (возможно пус-
тым) неупорядоченного произведения V&V (т. е.
u
⊂ V&V ) с элемента-
ми вида [v, w], где v, w ∈ V и допустимо совпадение элементов пары v = w.
Тогда граф G можно определить как совокупность G = (V,
U
).
Можно ввести отображение инцидентности графа – Г. Если верши-
ны v, w ∈ V являются граничными точками ребра
u
∈
U
, то это можно
обозначить
u
~[v, w] (читается “ребро u соединяет вершины v и w”) и
ввести отображение Г(u) = [v, w] – это означает, что ребро инцидентно
каждой из вершин v и w и, наоборот, вершины инцидентны ребру.
Поскольку отображение инцидентности графа Г включает множе-
ство ребер графа
U
, постольку описание графа как совокупности мно-
жества вершин V и отображения Г множества
U
в V&V вида G = (V, Г)
полностью определяет граф.
Степенью вершины
δ
(v) называется число концов ребер, инцидентных вер-
шине v (т. е. петля учитывается дважды). Для изолированной вершины
δ
(v) = 0.
Вырожденным называется граф, у которого все вершины изолированы.
Разбиение графа на составляющие
Суграфом графа G называется граф G’ = (V,
U
′
), где
U
′
⊂
U
, т. е.
суграф получается из исходного графа удалением некоторого числа ре-
бер (с сохранением вершин).

Страницы