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

UptoLike

ВУЗ: 

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

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

Рубрика: 

22
которая начинается и оканчивается в вершине
w
, является кон-
туром
1
C . Удалим дуги контура
1
C из орграфа
G
. В получив-
шемся орграфе
1
G полустепени вершин, принадлежавших
1
C ,
уменьшились на единицу, полустепени остальных вершин не
изменились. Следовательно, для любой вершины
v
орграфа
G
будет выполняться равенство
vdvd
. Поэтому в орграфе
1
G можно выделить контур
2
C и т.д.
Достаточность доказывается путем объединения контуров в
эйлеров цикл (теорема 2.4). Теорема доказана.
Пусть
n
vvv ,...,,
2`1
– вершины, а
m
eee ,...,,
21
– рёбра ориен-
тированного графа
G
.
Определение 5.17. Матрица
ij
a размером
nm , где
,если,0
,,1
,,1
инцидентнане
взаходитесли
извыходитесли
ij
ij
ij
ij
ve
ve
ve
a
называется матрицей инцидентности для рёбер ориентирован-
ного графа
G
.
5.2. Задачи
1. В некоторой стране есть столица и еще 100 городов. Не-
которые города (в том числе и столица) соединены дорогами с
односторонним движением. Из каждого нестоличного города
выходит 20 дорог, и в каждый такой город входит 21 дорога.
Докажите, что в столицу нельзя проехать ни из одного города.
2. Докажите, что на ребрах связного графа можно так рас-
ставить стрелки, чтобы из некоторой вершины можно было доб-
раться по стрелкам до любой другой.
3. В некотором государстве каждый город соединен с каж-
дым дорогой. Король хочет ввести на дорогах одностороннее
движение так, чтобы, выехав из любого города, в него нельзя
было вернуться. Можно ли так сделать?

Страницы