Реферат: Графы. Решение практических задач с использованием графов (С++)

- Автоморфизм графов

конструктивное перечисление структурных изомеров для

производных органических соединений

синтез тестов цифровых устройств

Заключение

В работе были рассмотрены задачи из теории графов, которые уже стали классическими. Особенно часто в практическом программировании возникают вопросы о построении кратчайшего остова графа и нахождении максимального паросочетания. Известно также, что задача о нахождении гамильтонова цикла принадлежит к числу 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,"%d\n",vertex);

}

void gamilton_path(int k){

int v = St[k-1]; // текущая вершина

for(int j = 0;j < n;j++)

if(graph[v][j]==1) // есть ребро между v и j