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

UptoLike

ВУЗ: 

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

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

Рубрика: 

7
Свойства бинарных отношений. Отношение
ρ
называется рефлек-
сивным, если (x, x) ∈
ρ
; антирефлексивным, если (x, x) ∉
ρ
; симметрич-
ным, если (x, y) ∈
ρ
↔ (y, x) ∈ с; антисимметричным, если (x, y) ∈
ρ
и
(y, x) ∈
ρ
→ x = y; асимметричным, если (x, y) ∈
ρ
→ (y, x) ∉
ρ
; транзи-
тивным, если (x, y) ∈
ρ
и (y, z) ∈
ρ
→ (x, z) ∈
ρ
; линейным, если (x, y) ∈
ρ
или (y, x) ∈
ρ
.
Из множества всех отношений выделяется класс отношений, одно-
временно симметричных, транзитивных и рефлексивных. Такие отно-
шения называются отношениями эквивалентности.
К отношениям порядка относятся: а) отношение квазипорядка, облада-
ющее свойствами рефлексивности, транзитивности; б) отношение частич-
ного порядка на множестве Х (часто обозначаемое <= или >=), обладающее
свойствами рефлексивности, антисимметричности, транзитивности; в) от-
ношение строгого порядка на множестве Х (часто обозначаемое < или >),
обладающее свойствами антирефлексивности, асимметричности, транзи-
тивности; г) отношение линейного (полного) порядка, обладающее наряду
со свойствами отношения частичного порядка свойством линейности.
Раздел 3. Основные понятия теории графов
Понятие графа как математической модели; геометрическое и абст-
рактное представление графов; типы графов (неориентированный и
ориентированный); понятие смежности и инцидентности; матрицы
смежности.
Литература: [1, c. 8 –10, 21, 24].
Теория графов, являясь разделом дискретной математики, использу-
ется для описания и изучения отношений между дискретными объекта-
ми. При этом объекты геометрически можно представить в виде мно-
жества точек, называемых вершинами графа (V = {v
i
}), а отношения
между ними представляются самонепересекающимися линиями, связы-
вающими вершины. Если линии не ориентированы, то их называют
ребрами (
u
), а сам граф – неориентированным (рис. 1, а), а если линии
ориентированы, то их называют дугами (u), а граф – ориентированным
(рис. 1, б), или орграфом. Если множество вершин и ребер (или дуг)
конечно, то граф называется конечным.
Вершины, соединенные ребром или дугой, называются смежными.
Ребра, имеющие общую вершину, также смежны между собой. Говорят,

Страницы