Графы. Решение практических задач с использованием графов (С++)
| Категория реферата: Рефераты по математике
| Теги реферата: реферат влияние на человека реферат древняя культура, диплом рф
| Добавил(а) на сайт: Мосенцев.
Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата
- Автоморфизм графов
конструктивное перечисление структурных изомеров для
производных органических соединений
синтез тестов цифровых устройств
Заключение
В работе были рассмотрены задачи из теории графов, которые уже стали классическими. Особенно часто в практическом программировании возникают вопросы о построении кратчайшего остова графа и нахождении максимального паросочетания. Известно также, что задача о нахождении гамильтонова цикла принадлежит к числу NP-полных, т.е. эффективный алгоритм для ее решения не найден – приведенная программа ищет цикл методом перебора. Все задачи реализованы на языке С++, листинги которых приводятся в приложении А, примеры входных и выходных данных – в приложении Б.
Список литературы
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М: МЦНМО, 2001
Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978.
Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001.
В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999.
Приложение А
1. Гамильтоновым циклом в графе называется цикл, проходящий через все вершины графа ровно один раз. Для данного графа найти гамильтонов цикл, если он существует.
#include <iostream.h>
#include <stdio.h>
FILE* fi = fopen("g_graph.txt","r"); // Файл с матрицей смежности
FILE* fo = fopen("g_cycle.txt","w"); // Файл с найденными циклами
bool **graph; //Матрица смежности для хранения графа
int n; //Количество вершин в графе
const int vertex = 1; // первая вершина при поиске
int *St; //Массив для хранения просмотренных вершин
int *Nnew; //Массив признаков: вершина просмотрена или нет
void out_way(int n){ //Процедура вывода Гамильтонова цикла
for(int i=0;i<n;i++)
fprintf(fo,"%d ",St[i]);
fprintf(fo,"%dn",vertex);
Рекомендуем скачать другие рефераты по теме: реферат памятники, бесплатные рефераты без регистрации.
Категории:
Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата
Главная