ВУЗ:
Составители:
Рубрика:
begin
t:= top(stack);
if U[t]=nil then b:=false
else b:=not new [U[t]
↑
.dat];
while b do
begin
U[t]:=U[t]
↑
.next;
if U[t]=nil then b:=false
else b:=not new [U[t]
↑
.dat]
end;
if U[t]:
≠
nil then
begin
w:=U[t]
↑
.dat; stack
←
w;
T:=Т
∪
{t,w}; new[w]:=false
end;
else t
←
stack
end
end
Пример 11.2.
Порядок прохождения вершин при построении
покрывающего дерева графа (ветви дерева выделены).
2
1
3
4
7
6
5
8
9
T=(1,2)
∪
(2,3)
∪
(3,4)
∪
(4,6)
∪
∪
(6,5)
∪
(5,8)
∪
(5,9)
∪
(6,7)
Лекция 12. Эйлеровы графы. Алгоритм поиска эйлерова цик-
ла в графе.
Начало теории графов как раздела математики связывают с так
называемой
задачей о кенигсбергских мостах.
Задача.
Город Кенигсберг (Калининград) был построен на бере-
гах и двух островах реки Преголи. В городе было семь мостов, ко-
торые соединяли острова между собой и с береговыми частями
города (рис. 12.1).
Можно ли, выйдя из дома, вернуться обратно,
пройдя по каждому мосту только один раз? Сопоставим рисунку
граф
(рис. 12.2), вершины которого соответствуют четырем разде-
45
Страницы
- « первая
- ‹ предыдущая
- …
- 43
- 44
- 45
- 46
- 47
- …
- следующая ›
- последняя »
