Дискретная математика. Никищенков С.А - 14 стр.

UptoLike

ВУЗ: 

СамГУПС | Самара

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

Рубрика: 

связями (рис. 20,а). Оно интерпретируется как "быть сравнимым со всеми и с собой";
б) слабополое (Х
×
Х)\Δ (без единицы) или полный граф G
p
без петель (рис. 20,б).
Оно интерпретируется как "быть сравнимым со всеми, но не с собой";
в) однонаправленное универсальное отношение – это бинарное отношение,
наличие в котором дуги (v
i
, v
j
) исключает присутствие дуги (v
j
, v
i
) противоположной
направленности v
i
, v
j
∈
V (рис. 20,в).
2.5. Виды графов
Графы классифицируются относительно свойств их элементов.
1. По наличию ориентации дуг графы делятся:
на ориентированные, или орграфы, для двух любых вершин u и v
выполняется условие (u, v)
≠
(v, u), т.е. стрелка направлена в одну сторону: ∀(u, v)∈E [(u,
v)
≠
(v, u)];
на неориентированные, или неорграфы, для двух любых вершин u и v
выполняется условие (u, v)=(v, u), т.е. стрелки направлены в разные стороны: ∀(u, v)∈E
[(u, v)=(v, u)].
Неориентированные дуги называются рёбрами и представляются линиями без
стрелок. Граф, имевший и дуги, и ребра, называется смешанным. Он сводится к орграфу
заменой каждого ребра на 2
дуги противоположной направленности.
Каждому орграфу можно поставить в соответствие неорграф, заменив дуги
первого ребрами, т.е. лишив их ориентации. Такой неорграф называется соотнесённым.
2. Относительно кратности дуг графы делятся:
на графы с одиночными ребрами, где для любых двух вершин u и v
выполняется условие ρ(u, v)≤1, т.е. число рёбер не более одного
: ∀(u, v)∈E ρ(u, v)≤1;
на мультиграфы, содержащие кратные ребра – с ρ(u, v)≥1.
3. Относительно структуры дуг графы делятся:
на графы с простыми ребрами;
на гиперграфы H=(V, E), ребра которых инцидентны более, чем двум
вершинам, т.е. сами являются графами. В примере, изображенном на рис. 21,а, V={1, 2, 3,
4, 5, 6}, E={(1, 2, 3, 4), (3, 5, 6)}.
v
1
v
2
v
4
v
3
v
1
v
2
v
4
v
3
v
1
v
2
v
4
v
3
а) б) в)
Рис. 20

Страницы