производных органических соединений
синтез тестов цифровых устройств
В работе были рассмотрены задачи из теории графов, которые уже стали классическими. Особенно часто в практическом программировании возникают вопросы о построении кратчайшего остова графа и нахождении максимального паросочетания. Известно также, что задача о нахождении гамильтонова цикла принадлежит к числу 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
if(k==n && j==vertex)out_way(n); //прошли все вершины
else
if(Nnew[j]){ // вершина не просмотрена
St[k]=j; // добавляем ее к пройденному пути
Nnew[j]=false; // просмотрена
gamilton_path(k+1); //строим путь дальше
Nnew[j]=true; //возвращаемся назад и строим другие циклы
}
}
int main(){
fscanf(fi,"%d",&n); //Считываем количество вершин
St = new int[n];
Nnew = new int[n];
for(int i = 0;i < n;i++)Nnew[i]=1; // Нет просмотренных вершин
graph = new bool*[n];
for(int i=0;i<n;i++){
graph[i] = new bool[n]; //выделяем память под строку
for(int j=0;j<n;j++){
fscanf(fi,"%d",&graph[i][j]);
}
}
Nnew[vertex]=false; //первая вершина уже просмотрена
St[0]=vertex; // вершина с которой начали проход
gamilton_path(1);//параметр означает количество пройденных вершин
fcloseall();
return(0);
}
2.Эйлеровым циклом называется цикл в графе, проходящий через все ребра графа ровно один раз. Для данного графа найти эйлеров цикл, если он существует.
#include <iostream.h>
#include <stdio.h>
struct Node{
int inf;
Node *next;
};
//============================Stack==============================
Node *init(){ // Инициализация стека
return NULL;
}
void push(Node *&st,int dat){ // Загрузка числа в стек
Node *el = new Node;
el->inf = dat;
el->next = st;
st=el;
}
int pop(Node *&st){ // Извлечение из стека
int value = st->inf;
Node *temp = st;
st = st->next;
delete temp;
return value;
}
int peek(Node *st){ // Получение числа без его извлечения
return st->inf;
}
//==============================================================
Node **graph; // Массив списков смежности
const int vertex = 1; // Первая вершина
FILE* fi = fopen("e_graph.txt","r"); //Файл с матрицей смежности
FILE* fo = fopen("e_cycle.txt","w"); // Результирующий файл
void add(Node*& list,int data){ //Добавление смежной вершины
if(!list){list=new Node;list->inf=data;list->next=0;return;}
Node *temp=list;
while(temp->next)temp=temp->next;
Node *elem=new Node;
elem->inf=data;
elem->next=NULL;
temp->next=elem;
}
void del(Node* &l,int key){ // Удаление вершины key из списка
if(l->inf==key){Node *tmp=l; l=l->next; delete tmp;}
else{
Node *tmp=l;
while(tmp){
if(tmp->next) // есть следующая вершина
if(tmp->next->inf==key){ // и она искомая
Node *tmp2=tmp->next;
tmp->next=tmp->next->next;
delete tmp2;
}
tmp=tmp->next;
}
}
}
bool eiler(Node **gr,int num){ // Определение эйлеровости графа
int count;
for(int i=0;i<num;i++){ //проходим все вершины
count=0;
Node *tmp=gr[i];
while(tmp){ // считаем степень
count++;
tmp=tmp->next;
}
if(count%2==1)return 0; // степень нечетная
}
return 1; // все степени четные
}
void eiler_path(Node **gr){ //Построение цикла
Node *S = init();// Стек для пройденных вершин
int v=vertex;// 1я вершина (произвольная)
int u;
push(S,v); //сохраняем ее в стек
while(S){ //пока стек не пуст
v = peek(S); // текущая вершина
if(!gr[v]){ // если нет инцидентных ребер
v=pop(S); fprintf(fo,"%d\ ",v); //выводим вершину
}else {
u=gr[v]->inf; push(S,u); //проходим в следующую вершину
del(gr[v],u); del(gr[u],v); //удаляем пройденное ребро
}
}
}
int main(){
int n; // Количество вершин
int zn;// Текущее значение
fscanf(fi,"%d",&n); graph=new Node*[n];
for(int i=0;i<n;i++)graph[i]=NULL;
for(int i=0;i<n;i++) // заполняем массив списков
for(int j=0;j<n;j++){
fscanf(fi,"%d",&zn);
if(zn) add(graph[i],j);
}
if(eiler(graph,n))eiler_path(graph);
else fprintf(fo,"Граф не является эйлеровым.");
return(0);
}
3.Построить остовное дерево минимальной стоимости для связанного взвешенного графа, используя алгоритм Прима.
#include <iostream.h>
#include <stdio.h>
#include <values.h>
FILE* fi = fopen("p_graph.txt","r"); //Входной файл
FILE* fo = fopen("p_ostov.txt","w"); //Выходной файл
struct edge{ // Структура для хранения ребра
int b,e;
int weigh;
};
int **graph; // исходный граф
int p; // количество вершин в графе
edge *SST; // остов
int num_ver=0; // количество ребер в остове
int *S; // вершины, включенные в остов
int num_s=0; //количество вершин в остове
int calc_ver(){ // подсчитывает число ребер в графе
int i=0,j,res=0;
while(i<p){j=i+1; while(j++<p)if(graph[i][j])res+=1; i++;}
return res;
}
bool added(int v){ // проверяет: добавлена вершина v в остов
for(int i=0;i<num_s;i++)if(v==S[i])return 1;
return 0;
}
void prim(){ // построение остова
S = new int[calc_ver()];
int *alf = new int[p]; // ближайшие вершины, добавленные в остов
int *bet = new int[p]; // длины ребер, соединяющие вершины с остовом
int u = 0; // произвольная вершина
S[num_s] = u; num_s++; // добавляем в остов
for(int v=0;v<p;v++)
if(graph[v][u]){alf[v] = u; bet[v] = graph[u][v];}//u - ближайшая вершина
else {alf[v] = -1; bet[v] = MAXINT;}
int w,x;
for(int i=0;i<p-1;i++){
x = MAXINT;
for(int v=0;v<p;v++){ // поиск ближайшей к остову вершины
if(bet[v]<x && !added(v)){w = v; x = bet[v];}
}
S[num_s] = w; num_s++; // добавляем найденную вершину к остову
// и ребро
SST[num_ver].b=alf[w];SST[num_ver].e=w;SST[num_ver].weigh=graph[alf[w]][w];
num_ver++;
for(int v=0;v<p;v++){
if(graph[v][w] && !added(v))// меняем ближайшую вершину остова
if(bet[v]>graph[v][w]){alf[v]=w; bet[v]=graph[v][w];}
}
}
}
void out(){
int weight=0;
fprintf(fo,"%d\n",num_ver);
for(int i=0;i<num_ver;i++){
fprintf(fo,"%2d\ %2d\ %2d\n",SST[i].b,SST[i].e,SST[i].weigh);
weight+=SST[i].weigh;
}
fprintf(fo,"%s%d","Вес найденного остова: ",weight);
}
int main(){
fscanf(fi,"%d",&p); //Считываем количество вершин
graph = new int*[p];
for(int i=0;i<p;i++){
graph[i] = new int[p]; //выделяем память под строку
for(int j=0;j<p;j++){
fscanf(fi,"%d",&graph[i][j]);
}
}
SST = new edge[calc_ver()];
prim();
out();
fcloseall();
return 0;
}
4. Построить остовное дерево минимальной стоимости для связанного взвешенного графа, используя алгоритм Краскала.
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
FILE* fi = fopen("k_graph.txt","r"); //Входной файл
FILE* fo = fopen("k_ostov.txt","w"); //Выходной файл
struct edge{ // Структура для хранения ребра
int beg,end;
int weigh;
};
edge *E; // массив с ребрами
edge *SST; //остов
int num_edge; //количество ребер в остове
int n; //количество ребер
bool *nov; //признак прохода вершины
void sort(edge *arr){ //сортировка ребер по весу
edge tmp;
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
if(arr[j].weigh<arr[j-1].weigh){
tmp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = tmp;
}
}
int smezh(int v1,edge v2){
//определяет вершину смежную с v1 через ребро v2
if(v1==v2.beg)return(v2.end);
else if(v1==v2.end)return(v2.beg);
else return -1; // вершина v1 и ребро v2 не инцидентны
}
bool cycle(int v,int v0){ //определяет наличие цикла
nov[v] = 0; // v пройдена
for(int i=0;i<num_edge-1;i++)
if(smezh(v,SST[i])!=-1) //если смежны
if(smezh(v,SST[i])==v0)return 1; //из конца ребра пришли в начало
else if(nov[smezh(v,SST[i])]) // новая вершина
if(cycle(smezh(v,SST[i]),v0))return 1;
nov[v] = 1; //возвращаемся назад
return 0;
}
void kruskal(){
num_edge = 0; //остов пуст
sort(E); // упорядочивание E по возрастанию веса
for(int i=0;i<n;i++){
SST[num_edge] = E[i]; num_edge++; //добавляем ребро
// если появляется цикл - удаляем
if(cycle(SST[num_edge-1].end,SST[num_edge-1].beg))num_edge--;
for(int i=0;i<n;i++)nov[i]=1;
}
}
void out(edge *mas,int num){ // вывод ребер
int sum=0;
fprintf(fo,"%d\n",num); // количество ребер
for(int i=0;i<num;i++){
fprintf(fo,"%d\ %d\ %3d\n",mas[i].beg,mas[i].end,mas[i].weigh);
sum+=mas[i].weigh;
}
fprintf(fo,"%s%d","Вес найденного остова: ",sum);
}
int main(){
fscanf(fi,"%d",&n); //считываем количество ребер
E = new edge[n];
SST = new edge[n];
nov = new bool[n+1];
for(int i=0;i<n;i++)nov[i] = 1;
for(int i=0;i<n;i++) //заполняем множество ребер
fscanf(fi,"%d%d%d3",&E[i].beg,&E[i].end,&E[i].weigh);
kruskal(); //строим остов
out(SST,num_edge); //выводим в файл
return 0;
}
5.Для заданного неориентированного графа найдите максимальное паросочетание.
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
FILE* fi = fopen("m_graph.txt","r");
FILE* fo = fopen("m_par.txt","w");
struct edge{ // ребро графа
int b,e;
};
int n; //количество ребер
edge *graph; // массив ребер
edge *matching; // паросочетание
int num_mat; //количество паросочетаний
bool smezh(edge q1,edge q2){ // 1 - если q1 и q2 смежны, иначе -0
return q1.b==q2.b||q1.b==q2.e||q1.e==q2.b||q1.e==q2.e;
}
void out(edge *m,int num){
fprintf(fo,"%d\n",num); // количество ребер
for(int i=0;i<num;i++)
fprintf(fo,"%d\ %d\n",m[i].b,m[i].e);
}
bool bad(){//возвращает 1, если в паросочетании есть смежное ребро
for(int i=0;i<num_mat-1;i++)
if(smezh(matching[i],matching[num_mat-1]))return 1;
return 0;
}
void solve(){ //находит максимальное паросочетание
num_mat = 0;
for(int i=0;i<n;i++){
matching[num_mat]=graph[i];num_mat++; // добавляем ребро
if(bad())num_mat--; // если уже есть смежные - удаляем
}
}
int main(){
fscanf(fi,"%d",&n);
graph = new edge[n];
matching = new edge[n];
for(int i=0;i<n;i++)
fscanf(fi,"%d%d",&graph[i].b,&graph[i].e);
solve();
out(matching,num_mat);
fcloseall();
return 0;
}
Приложение Б
Примеры входных и выходных файлов
1.
Входной файл "g_graph.txt":
5
0 0 1 1 0
0 0 0 1 1
1 0 0 0 1
1 1 0 0 0
0 1 1 0 0
Выходной файл "g_cycle.txt":
0 2 4 1 3 0
0 3 1 4 2 0
2.
Входной файл " e_graph.txt ":
5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
Выходной файл "e_cycle.txt":
1 4 3 2 4 0 3 1 2 0 1
3.
Входной файл " p_graph.txt ":
9
0 4 5 2 0 0 0 0 0
4 0 7 0 0 0 6 0 0
5 7 0 3 0 0 0 0 0
2 0 3 0 0 0 0 0 0
0 0 0 0 0 7 8 0 0
0 0 0 0 7 0 1 0 0
0 6 0 0 8 1 0 3 1
0 0 0 0 0 0 3 0 2
0 0 0 0 0 0 1 2 0
Выходной файл "p_ostov.txt":
8
0 3 2
3 2 3
0 1 4
1 6 6
6 5 1
6 8 1
8 7 2
5 4 7
Вес найденного остова: 26
4.
Входной файл " k_graph.txt ":
5
0 1 1
1 2 2
2 3 1
0 3 4
1 3 2
Выходной файл "k_ostov.txt":
3
0 1 1
2 3 1
1 2 2
Вес найденного остова: 4
5.
Входной файл " m_graph.txt ":
7
0 1
1 4
0 3
3 2
1 3
2 0
2 5
Выходной файл "m_par.txt":
2
0 1
3 2