Предыдущая страница реферата | 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 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки