Лекции по дискретной математике. Ч.II. Комбинаторика, разостные уравнения, алгоритмы на графах. Гайдамака Ю.В - 47 стр.

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

дем продолжать ее, насколько возможно, выбирая каждый раз но-
вое ребро. Т.к. степени всех вершин четны, попав в очередную,
отличную от v
1
, вершину, мы всегда будем иметь в распоряжении
еще не пройденное ребро. Поэтому построение цепи P
1
закончится
в вершине v
1
, т.е. P
1
будет циклом. Если P
1
содержит все ребра
графа G, то это и будет требуемый эйлеров цикл. В противном
случае, удалив из G все ребра цикла P
1
, получим граф G
1
. Т.к. P
1
и
G имели вершины только четных степеней, то и G
1
имеет вершины
только четных степеней. В силу связности графа G графы P
1
и G
1
должны иметь хотя бы одну общую вершину v
2
. Начиная с верши-
ны v
2
, построим цикл P
2
в графе G
1
аналогично построению цикла
P
1
в графе G. Обозначим через P
1
’ и P
1
” части цикла P
1
от v
1
до v
2
и от v
2
до v
1
соответственно (рис.12.3). Получим новый цикл P
3
=
=P
1
’
∪
P
2
∪
P
1
”, который, начиная с v
1
, проходит по ребрам цепи P
1
’
до v
2
, затем по всем ребрам цикла P
2
, и возвращается в v
1
по реб-
рам цепи P
1
”. Если P
3
не эйлеров цикл,
то повторяем предыдущую процедуру.
Получим еще больший цикл. В силу
конечности графа G этот процесс за-
кончится построением эйлерового цик-
ла.
v
1
P
1
”
v
2
P
1
’
P
2
Рис. 12.3.
На этой идее основан алгоритм нахождения эйлерового цикла в
графе.
Обозначения: G=(V,E) - связный граф без вершин нечетной степе-
ни, V={v
1
,…,v
n
};
u[v] - список инцидентности для вершины v, u[1..n];
stack - рабочий стек;
res - стек, содержащий последовательность вершин
эйлерового цикла.
begin
stack:=0; res:=0;
v:= произвольная вершина графа;
stack
←
v;
while stack
≠
0 do
begin
v:=top (stack);
if u[v]
≠
nil then
47

Страницы