Реализация алгоритма нахождения множеств элементарных циклов графа средствами языка С++
Содержание
Введение
Некоторые
сведения из теории графов
Способы
представления графа в информатике
Поиск
в глубину множества элементарных циклов графа
О
среде wxDev-C++
Разработка
в wxDev-C++
Руководство
пользователю
Заключение
Список
используемой литературы
Приложение
А
Введение
В настоящее время дискретная математика и
смежные с ней разделы привлекают большое внимание специалистов различных
областей науки и техники, являясь эффективным аппаратом формализации
современных инженерных задач, связанных с дискретными объектами. Особое
значение с практической точки зрения имеет теория графов, использующаяся при
проектировании интегральных схем и схем управления, исследовании автоматов и
логических цепей, при системном анализе, автоматизированном управлении производством,
при разработке вычислительных и информационных сетей, в схемотехническом и
конструкторско-топологическом проектировании, и т.д. Обширное применение теория
графов находит в современной вычислительной технике и кибернетике: в
теоретическом программировании, при проектировании ЭВМ, баз данных, систем
логического управления. Поэтому основное внимание в курсовой работе уделяется
изложению основ теории графов и алгоритмов поиска элементарных циклов в глубину
в неориентированных графах.
Некоторые сведения из теории графов
В теории графов объекты
представляются как вершиныграфа, а связи - как дуги, или рёбра. Граф или
неориентированный графG(рис.1) - это упорядоченная пара
<#"600882.files/image001.gif">
Рисунок 1 Неориентированный граф
Вершины и рёбра графа называются
также элементами графа, число вершин в графе | V | - порядком, число рёбер | E
| - размером графа.
Вершины u и v называются концевыми
вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь,
соединяет эти вершины. Две концевые вершины одного и того же ребра называются
соседними.
Два ребра называются смежными, если
они имеют общую концевую вершину.
Два ребра называются кратными, если
множества их концевых вершин совпадают.
Ребро называется петлёй, если его
концы совпадают, то есть e = {v,v}.
Ориентированный граф (сокращённо
орграф) G(рис.2) - это упорядоченная пара
<#"600882.files/image002.gif">
Рисунок 2 Ориентированный граф
Дуга - это упорядоченная пара вершин (v, w), где
вершину v называют началом, а w - концом дуги. Можно сказать, что дуга 
ведёт
от вершины v к вершине w.
Путём (или цепью) в графе называют конечную
последовательность вершин, в которой каждая вершина (кроме последней) соединена
со следующей в последовательности вершин ребром.
Ориентированным путём в орграфе называют
конечную последовательность вершин vi, для которой все пары (vi,vi + 1)являются
(ориентированными) рёбрами.
Циклом называют путь, в котором первая и
последняя вершины совпадают. При этом длиной пути (или цикла) называют число
составляющих его рёбер. Заметим, что если вершины u и v являются концами
некоторого ребра, то согласно данному определению, последовательность (u,v,u)
является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие
понятия.
Путь (или цикл) называют простым, если ребра в
нём не повторяются; элементарным, если он простой и вершины в нём не
повторяются. Несложно видеть, что, всякий путь, соединяющий две вершины,
содержит элементарный путь, соединяющий те же две вершины. Всякий простой
неэлементарный путь содержит элементарный цикл. Всякий простой цикл, проходящий
через некоторую вершину (или ребро), содержит элементарный (под-)цикл,
проходящий через ту же вершину (или ребро). Петля - элементарный цикл.
Граф с петлями и кратными ребрами (дугами)
называется псевдографом. Граф с кратными ребрами (дугами) и без петель
называется мультиграфом.
Граф, не содержащий петель и кратных ребер,
называется простым графом.
Две вершины графа xi и хj называются смежными,
если существует соединяющее их ребро (дуга). Два ребра (дуги) смежны, если они
имеют общую вершину
Множество вершин графа называется независимым,
если никакие две вершины этого множества не соединены ребром. Другими словами,
индуцированный этим множеством подграф состоит из изолированных вершин. Иногда
также говорят, что каждое ребро графа инцидентно не более чем одной вершине из
независимого множества.
Способы представления графа в информатике
Матрица смежности. Таблица, где как столбцы, так
и строки соответствуют вершинам графа. В каждой ячейке этой матрицы
записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу
(либо наоборот).
Недостатком являются требования к памяти, прямо
пропорциональные квадрату количества вершин, двумерный массив; матрица с
пропусками; неявное задание (при помощи функции).
Матрица инцидентности. Каждая строка
соответствует определённой вершине графа, а столбцы соответствуют связям графа.
В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается: 1в
случае, если связь j «выходит» из вершины i,−1,если связь «входит» в
вершину,0 во всех остальных случаях (то есть если связь является петлёй или
связь не инцидентна вершине)
Данный способ является самым ёмким (размер
пропорционален | E | | V | ) для хранения, но облегчает нахождение циклов в
графе.
Список рёбер - это тип представления
графа в памяти компьютерной программы, подразумевающий, что каждое ребро
представляется двумя числами - номерами вершин этого ребра. Список рёбер более
удобен для реализации различных алгоритмов на графах по сравнению с матрицей
смежности <#"600882.files/image004.gif">)
Перекрашиваем вершину u в серый
цвет.
Для всякой вершины w, смежной
<#"600882.files/image005.gif">
Рисунок 6 меню wxDev-C++
Файл→Создать→Проект (рис7)
Рисунок 7 Как создать проект в wxDev-C++
Далее в открывшемся окне выбрать тип проекта и
задать название(рис8).
Рисунок 8 создание проекта
В моем случае тип проекта - Console Application
название h1.
Далее необходимо задать расположение проекта на
компьютере.
В моем случае (рис9) это G:\Курсовая работа по
дис.мат\
Рисунок 9 расположение проекта
И нажать кнопку сохранить. Далее в открывшемся
поле редактора кода видим предварительно скомпонованный заголовок(рис10) из
нескольких стандартных библиотек и главной функции main, с которой начинается
выполнение программы.
Рисунок 10 Редактор кода wxDev-C++
Сам код моей программы в Приложении А.
Руководство пользователю
Моя программа ищет и выводит на экран простые
циклы. Она очень проста в использовании. Запустив , ее вы поймете это сами.
Итак, запустили, программа просит нас ввести
количество ребер в графе(рис3). Вводим, например 4.
Далее необходимо ввести ребра, поочередно одну и
вторую вершину каждого ребра(рис4).
Рисунок 3 первое, что видим после запуска
программы
граф алгоритм цикл программа
Рисунок 4 вводим ребра графа
Далее увидим результат - матрицу смежности и
элементарный цикл, которые программа выведет на экран в этом же окне(рис5).
Рисунок 5 результат работы программы.
Заключение
Современное состояние и тенденции развития
вычислительной техники как основного инструмента информатики таковы, что наряду
с увеличением функциональности вычислительная техника приобретает свойства,
позволяющие работать на ней пользователю, не разбирающемуся в программировании.
В этот период появился более качественный интерфейс программ. Появились
структуры графических данных и более крупные, интегральные информационные
единицы - объекты. Следствием стало бурное развитие объектно-ориентированных
систем программирования, таких как Visual C++, Visual BASIC и других, в основе
которых лежит обработка объектных структур данных. Также появились новые языки
программирования ADA, OCCAM.([3]) И если раньше большой популярностью
пользовались простые линейные алгоритмы то в настоящее время алгоритмы таких
типов как деревья, графы, списки, очереди - получают все большее
распространение.
Таким образом, развитие информационных
технологий, их проникновение во все области жизнедеятельности человека требуют
компьютерного отображения информации в виде соответствующих структур данных. И
графы, являясь одной из частей этих структур данных, играют важную роль в
современном программировании, графы встречаются в сотнях разных задач.
Список используемой литературы
.Судоплатов
С.В. Математическая логика и теория алгоритмов: учебник / С.В. Судоплатов, Е.В.
Овчинникова. М.: ИНФРА-М, 2004. - 224 с.
.
Иванов Б.Н. Дискретная математика. Алгоритмы и программы / Б.Н. Иванов. М.:
Лаборатория базовых знаний, 2003. - 288 с.
.
Кристофиес П. Теория графов. М.: ИНФРА-М, 2004. - 328 с.
Приложение А
//////////////////////////////////////////////////////////////////////////////////////
//Дана матрица смежности неориентированного
графа. Найти множество элементарных циклов
//графа (используется алгоритм поиска в глубину)
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////namespace
std;
/*создаем новые типы переменных и обзываем */
typedef string
T_vertice;set<T_vertice> T_vertices_set; //set<T_vertice> - множество
вершинvector<T_vertice>
T_vertices;T_vertices_set T_edge;set<T_edge> T_edges;map<T_vertice,
bool> T_row;map<T_vertice, T_row> T_matr;map<T_vertice, int>
T_vertice_time;
//////////////////////////////////////////////////////////////////////////////////////
/*функция вывода на экран матриц смежности*/
void print_matr(T_matr& matr,
const T_vertices& vertices)
{
(T_vertices::const_iterator vertice_row_it
= vertices.begin();_row_it != vertices.end(); ++vertice_row_it)
{(T_vertices::const_iterator
vertice_col_it = vertices.begin();_col_it != vertices.end(); ++vertice_col_it)
{<< '\t'
<<
matr[*vertice_row_it][*vertice_col_it];
} ::cout <<endl
<<endl
<<endl;
}
}
//////////////////////////////////////////////////////////////////////////////////////
/*ввод
вершин*/_vertices
get_vertices(const T_edges& edges)
{_vertices_set
vertices_set;(T_edges::const_iterator edge_it = edges.begin(); edge_it != edges.end();
++ edge_it)
{_set.insert(*edge_it->begin());_set.insert(*edge_it->rbegin());
}T_vertices(vertices_set.begin(),
vertices_set.end());
}
//////////////////////////////////////////////////////////////////////////////////////
/*получение
матрицы
смежности*/_matr
get_adjacency_matr(const T_edges& edges)
{ _matr
adjacency_matr;(T_edges::const_iterator edge_it = edges.begin(); edge_it !=
edges.end();
++ edge_it)
{_vertice v1 =
*edge_it->begin();_vertice v2 = *edge_it->rbegin();
_matr[v1][v2] =
adjacency_matr[v2][v1] = true;
}adjacency_matr;
}
//////////////////////////////////////////////////////////////////////////////////////
/*элементарные
циклы*/print_cycles
( T_vertices vertices, _matr&
adjacency_matr, _vertices& spanning_tree, _vertice_time& vertice_time,
& time, _vertice vertice_U
)
{_tree.push_back(vertice_U);_time[vertice_U]
= ++time;
(T_vertices::const_iterator
vertice_V_it = vertices.begin();_V_it != vertices.end(); ++vertice_V_it)
{(adjacency_matr[vertice_U][*vertice_V_it])
{(vertice_time[*vertice_V_it] == 0)
{_cycles
( ,_matr,_tree,_time,,
*vertice_V_it
);
}
{(*vertice_V_it !=
*(spanning_tree.rbegin() + 1)
&&
vertice_time[*vertice_V_it] < vertice_time[vertice_U])
{::cout << "Elementarnii
tsikl: "
<< std::endl;
(T_vertices::const_iterator
_vertice_it
= std::find(spanning_tree.begin(),
spanning_tree.end(), *vertice_V_it);_vertice_it != spanning_tree.end();
++tree_vertice_it)
{::cout << *tree_vertice_it
<< std::endl;
}
}
}
}
}
}
//////////////////////////////////////////////////////////////////////////////////////main()
{(0,"Rus");::global(locale(""));
n = 0;
{<< "Vvedite kolichestvo
reber neorintirovannogo grafa:";>> n;
}while(n <= 0);
<< "Vvedite rebra
neorintirovannogo grafa"
"(vershini v rebre ne dolzhni
sovpadat t.e. bez petel):";_edges edges;
{<< endl
<< "rebro #"
<< edges.size() + 1
<< ":"
<< endl
<< "\t->
";_vertice v1;>> v1;_edge edge_cur;_cur.insert(v1);
_vertice v2;<< "\t->
";>> v2; _cur.insert(v2); (edge_cur.size() == 2)
{.insert(edge_cur);
}
}while(static_cast<int>(edges.size())
< n);
_vertices vertices =
get_vertices(edges);
_matr adjacency_matr =
get_adjacency_matr(edges);<< "Matritsa smezhnosti grafa:"
<< std::endl;
_matr(adjacency_matr, vertices);_vertices
spanning_tree;_vertice_time vertice_time;time = 0;
_cycles
( ,_matr,_tree,_time,,.front()
);("PAUSE");
}