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

UptoLike

ВУЗ: 

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

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

Рубрика: 

4. Относительно регулярности структуры графы делятся: на нерегулярные или
обычные; на регулярные, или однородные (рис. 21,б).
Однородный граф имеет степень 3, если для всех u
∈
V ρ(u)=3. Для
ориентированного oднopoдного графа ρ
+
(
u)=ρ
–
(
u)=3, u
∈
V.
() ()
nvvm
n
i
n
i
ii
*3
11
∑∑
==
−+
===
ρρ
5. Относительно точек пересечения на плоскости графы делятся на плоские
(планарные) и неплоские.
Граф G=(V, E) называется плоским, если он может быть нарисован на плоскости
(или сфере) таким образом, что произвольные две дуги графа не пересекаются друг с
другом.
Надо различать плоские графы от нарисованных неплоских графов, для которых
возможно устранить
пересечения дуг.
На рис. 22,а изображен граф, нарисованный как неплоский. На рис. 22,б он
представлен как плоский за счет другого начертания ребра (1, 3). Последний называют
также картой графа.
Граф G может быть преобразован в реберный и двудольный.
Вершины реберного графа G
l
, соответствуют ребрам исходного графа G (m
вершин), а каждое его ребро соединяет вершины, которым в исходном графе
соответствуют ребра, инцидентные одной вершине.
Двудольный граф K(V
1
U
V
2
, E) содержит два подмножества вершин V
1
, V
2
⊂
V,
⏐V
1
⏐=n
1
, ⏐V
2
⏐=n
2
, причем V
1
∩V
2
=∅ и каждая дуга (ребро) графа соединяет вершины,
принадлежащие только разным подмножествам (рис. 23,а).
2
5
1
3
4
6
а) б)
Рис. 21
1
2
4
3
1
2
4
3
a) б)
Рис. 22

Страницы