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

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

потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) – объема памяти для каждого представления. Здесь p – число вершин, а q – число ребер.

Матрица смежности

Представление графа с помощью квадратной булевой матрицы M, отражающей смежность вершин, называется матрицей смежности, где

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

Для матрицы смежности n(p,q) = O(p2).

Замечание

Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.

Матрица инциденций

Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа

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

а для орграфа

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

Для матрицы инциденций n(p,q) = O(pq).

Списки смежности

Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей на списки смежных вершин, где элемент списка представлен структурой

N : record v : 1..p; n :↑ N end record,

называется списком смежности. В случае представления неориентированных графов списками смежности n(p,q) = O(p+2q), а в случае ориентированных графов n(p,q) = O(p+q).

Массив дуг

Представление графа с помощью массива структур

E : array [1..q] of record b,e : 1..p end record,

отражающего список пар смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = O(2q).

Обзор задач теории графов

Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.

Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.

Далее перечислим некоторые типовые задачи теории графов и их приложения:

- Задача о кратчайшей цепи

замена оборудования

составление расписания движения транспортных средств

размещение пунктов скорой помощи

размещение телефонных станций

- Задача о максимальном потоке

анализ пропускной способности коммуникационной сети

организация движения в динамической сети

оптимальный подбор интенсивностей выполнения работ

синтез двухполюсной сети с заданной структурной надежностью

задача о распределении работ

- Задача об упаковках и покрытиях

оптимизация структуры ПЗУ

размещение диспетчерских пунктов городской транспортной сети

- Раскраска в графах

распределение памяти в ЭВМ

проектирование сетей телевизионного вещания

- Связность графов и сетей

проектирование кратчайшей коммуникационной сети

синтез структурно-надежной сети циркуляционной связи

анализ надежности стохастических сетей связи

- Изоморфизм графов и сетей

структурный синтез линейных избирательных цепей

автоматизация контроля при проектировании БИС

- Изоморфное вхождение и пересечение графов

локализация неисправности с помощью алгоритмов поиска МИПГ

покрытие схемы заданным набором типовых подсхем

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

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

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

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

Заключение

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

}

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,"%dn",num_ver);

for(int i=0;i<num_ver;i++){ 

fprintf(fo,"%2d %2d %2dn",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,"%dn",num); // количество ребер

for(int i=0;i<num;i++){

fprintf(fo,"%d %d %3dn",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,"%dn",num); // количество ребер

for(int i=0;i<num;i++) 

fprintf(fo,"%d %dn",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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: