Элементы теории графов. Сюсюкалов А.И - 23 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

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

Рубрика: 

18
8. Каждое ребро полного графа с 11 вершинами покрашено
в один из двух цветов: красный или синий. Докажите, что либо
«красный», либо «синий» граф не является плоским.
5. ОРИЕНТИРОВАННЫЕ ГРАФЫ
5.1. Определения и свойства
Определение 5.1. Ориентированный граф
G
, или орграф,
состоит из конечного непустого множества
V
и множества
E
упорядоченных пар элементов из
V
. Элементы множества
V
называются вершинами орграфа, элементы множества
E
– ду-
гами орграфа.
Определение 5.2. Если
vux , – дуга, то вершины
u
и
v
называются ее концевыми вершинами, причем
u
называется
началом дуги, а
v
– концом дуги.
Определение 5.3. Дуга с совпадающими началом и концом
называется петлей. Можно рассматривать орграфы с несколь-
кими дугами, имеющими общее начало и общий конец. Такие
дуги называются параллельными.
На рисунке дуга изображается направленной линией, иду-
щей от начала дуги к концу. Например, если
5,4,3,2,1V ,
87654321
,,,,,,, eeeeeeeeE , где
2,1
1
e ,
1,3
2
e ,
1,3
3
e ,
2,3
4
e ,
4,2
5
e ,
2,4
6
e ,
4,3
7
e ,
4,4
8
e , то орграф можно изобразить, как на рис.14. В этом
орграфе
2
e и
3
e – параллельные дуги, а
8
e – петля.
1
e
2
e
3
e
5
e
4
e
7
e
6
e
8
e
Рис.14
Определение 5.4. Вершины орграфа называются смежны-
ми, если они являются концевыми вершинами некоторой дуги. В
противном случае вершины называются несмежными.

Страницы