Aлгоритмы на графах
| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: ответы по биологии, диплом 2011
| Добавил(а) на сайт: Башкатов.
Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата
– включаем в него новый путь;
– идем по старому пути от до;
– повторяем процесс для вершины и т.д.
Для окончания доказательства (и построения алгоритма) заметим, что база индукции очевидна: если ребро одно, то оно – петля.
Хотя доказательство проведено для неориентированных графов, оно сразу переносится на ориентированные, только требование четности заменяется теперь на такое: число входящих в каждую вершину ребер должно быть равно числу выходящих.
Осталось заметить, что предложенный в доказательстве алгоритм линеен, т.е. число действий прямо пропорционально числу ребер.
Program Euler;
const n=9;
m: array[1..n, 1..n] of boolean=
(
(False, True, True, False, False, False, False, False, False),
(True, False, True, False, False, False, True, True, False),
(True, True, False, True, True, False, False, False, False),
(False, False, True, False, True, False, False, False, False),
(False, False, True, True, False, True, False, True, False),
(False, False, False, False, True, False, True, True, True ),
(False, True, False, False, False, True, False, True, True ),
(False, True, False, False, True, True, True, False, False),
(False, False, False, False, False, True, True, False, False)
);
Type
list=^node;
node=record
i: integer;
next: list
Рекомендуем скачать другие рефераты по теме: экологические рефераты, конспект 2 класс.
Категории:
Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата
Главная