Лекции по дискретной математике. Ч.II. Комбинаторика, разостные уравнения, алгоритмы на графах. Гайдамака Ю.В - 26 стр.

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

Тема. Теория конечных графов
Лекция 7. Неориентированные графы: основные понятия;
маршруты, цепи, циклы; связность; деревья и
леса.
Основные понятия
Пусть V - непустое множество, V
(2)
- множество всех его двух-
элементных подмножеств, т.е. (u,v)
∈
V
(2)
, если u,v
∈
V.
Определение. Неориентированным графом (или просто графом)
называется пара G=(V,E), где E
⊆
V
(2)
.
Элементы множества V называются вершинами
графа, а эле-
менты множества E - ребрами.
Определение
. Если e=(u,v)
∈
E, то вершины u,v называются
смежными
, а ребро e=(u,v) называется ребром, инцидентным вер-
шинам u и v.
Если V и E - конечные множества, то G называется конечным
графом.
Рассмотрим графы G=(V,E) и G*=(V*,E*),и пусть
ϕ
:V
→
V*- би-
екция (взаимно однозначное отображение).
Определение
. Если для любых вершин u и v графа G их образы
ϕ
(u) и
ϕ
(v) смежны в G* тогда и только тогда, когда u и v смежны в
G, то эта биекция называется изоморфизмом графа G на граф G*.
Если такой изоморфизм существует, то граф G изоморфен графу
G*.
Пример 7.1.
Неизоморфные графы
Изоморфные графы
26

Страницы