Формирование списка окрестностей вершин ориентированного графа по заданной матрице инцидентности
Особенности формирования списка окрестностей вершин ориентированного графа по заданной матрице инцидентности. Рассмотрение основных способов представления графов, анализ матрицы смежности. Знакомство со средой разработки Microsoft Visual Studio 2005.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 13.12.2015 |
| Размер файла | 1,8 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1.Графы
Множество различных задач может быть естественным образом сформулировано в терминах точек и связей между ними, т.е. в терминах графов (задачи составления расписания, транспортные задачи, задачи анализа сетей и т.д.). Эффективные алгоритмы решения задач теории графов имеют поэтому большое практическое значение.
Графом называется пара (X,U), где X - конечное множество вершин, а U - набор неупорядоченных и упорядоченных пар вершин. Обозначим граф G=(X,U). Неупорядоченная пара вершин называется ребром, упорядоченная - дугой. Граф, содержащий только ребра, называется неориентированным, только дуги - ориентированным, или орграфом.
Рис. 1
Если вершины v и u соединены ребром e, то говорят, что они смежны между собой, а ребро e инцидентно каждой из них. Количество ребер графа, инцидентных вершине v называется степенью данной вершины. Для ориентированного графа выделяют входящую степень, равную количеству входящих ребер и исходящую степень, равную количеству исходящих ребер, а степенью вершины в таком случае называют сумму ее входящей и исходящей степени. Вершины, имеющие степень 0, называют изолированными.
Рис. 2
Для орграфа на рис.3 входящие степени вершин 1,2,3,4,5 равны соответственно 0,1,1,1,0, исходящие - 2,0,0,1,0. Степени вершин, получаемые сложением входящих и исходящих степеней равны 2,1,1,2,0. Таким образов, вершина 5 - изолированная.
Ребро, соединяющее вершину саму с собой, называется петлей. Если одну пару вершин соединяют два или более ребер, то такие ребра называют кратными. Граф называется простым, если он не содержит ни петель, ни кратных ребер, иначе граф называется мультиграфом. (В некоторых источниках граф с кратными ребрами называют мультиграфом, с петлями - псевдографом). Простой граф, любая пара вершин которого соединена ребром, называется полным.
Граф называется разреженным, если общее количество ребер значительно меньше их возможного количества. Иначе граф называется плотным.
Рис. 3
2.Способы представления графов
Большинство задач на графах касается определения компонент связности, поиска маршрутов, нахождения расстояний и т.п. При их численном решении на ЭВМ граф должен быть представлен неким дискретным способом. Одно из направлений теории графов связано с их представлением с помощью алгебраических форм - матриц. Такое представление графов удобно для решения многих практических задач. Ниже рассматриваются некоторые такие представления.
3.Матрица смежности графа
Матрицей смежности ориентированного графа с n вершинами называется матрица A=[aij], i,j=1,…,n, в которой aij=1, если существует ребро (xi, xj) и aij=0, если вершины xi, xj не связаны с ребром (xi, xj). Матрица смежности однозначно определяет структуру графа. Ребро типа петли в матрице смежности представляется соответствующим единичным диагональным элементом. Недостатком представления графа с помощью матрицы смежности является отсутствие возможности представления кратных рёбер.
Рис. 4
На рисунке приведён пример ориентированного графа и его матрицы смежности.
Матрицу смежности удобно использовать и для представления т.н. ВЗВЕШЕННЫХ графов. Граф называется взвешенным, если каждому его ребру сопоставлено число. Простой взвешенный граф может быть представлен своей матрицей весов W=[wij] - вес соединяющего вершины i, j. Веса несуществующих рёбер полагают равными 0 или . Матрица весов, таким образом, будет являться простым обобщением матрицы смежности.
4.Матрица инцидентности графа
Матрицей инцидентности для неориентированного графа с n вершинами и m рёбрами называется матрица B=[bij], i=1, 2, …, n, j=1, 2, …, m, строки которой соответствуют вершинам, а столбцы - рёбрам. Элементы bij=1, если вершина xi инцидентна uj, bij=0, если вершина xi не инцидентна uj.
Матрицей инцидентности для ориентированного графа с n вершинами и m рёбрами называется матрица B=[bij], i=1, 2, …, n, j=1, 2, …, m, строки которой соответствуют вершинам, а столбцы - рёбрам. Элементы bij=1, если ребро uj выходит из вершины xi, bij=-1, если ребро uj не выходит из вершины xi, bij=0, если вершина xi не инцидентна uj.
Матрица инцидентности однозначно определяет структуру графа. На рисунке представлен пример матрицы инцидентности для ориентированного графа из предыдущего пункта.
Рис. 5
5.Список окрестностей графа
Ориентированный или неориентированный граф может быть однозначно представлен списком окрестностей своих вершин. Список окрестностей состоит из списков Dots[x] вершин графа, смежных с вершиной x. Списки Dots[x] составляются для каждой вершины графа. Для примера опишем списком окрестностей граф, представленный выше на рисунке.
Рис. 6
6.Программная часть
Программа формирования списка окрестностей вершин ориентированного графа по заданной матрице инцидентности написана на языке программирования C++ в интегрированной среде разработки Microsoft Visual Studio 2005. Программа имеет имя «Курсовая работа (программ. 2 семестр)».
Программа содержит около 250 строк кода и занимает около 60 КБ на жёстком диске.
граф матрица microsoft
7.Функциональное назначение
Программа позволяет:
· Вводить матрицу инцидентности из файла;
· Выводить на экран и в файл список окрестностей вершин, степень захода выбранной вершины;
· Находить вершину с наибольшей степенью захода;
· Составлять список окрестности по матрице инцидентности ориентированного графа;
8.Логическая структура
Программа разбита на функции. Структурная схема программы представлена в приложении 2.1
Список функций:
void constr_list(dyn_list &l) функция создающая пустой список
Принимает структуру типа dyn_list, переданную по адресу, что позволяет изменять сам список, а не его локальную копию
bool chk_empty(dyn_list l) функция проверки списка на пустоту.
Принимает структуру dyn_list переданную по значению.
Если список пуст возвращает true, если нет false.
void comp_in(dyn_list &l, int n, int **ptarray, int V, int K)
Функция добавления в список нового элемента.
dyn_list &l - список переданный по адресу
int n - номер вершины
int **ptarray,int V, int K - исходная матрица инцидентности и её размерности
int search(dyn_list l)
Функция определения максимальной степени захода графа
dyn_list l - список переданный по значению.
Возвращает функция максимальную степень захода
comp* search1(dyn_list l, int n)
Функция ищет элемент с максимальной степенью захода.
dyn_list l - список переданный по значению
int n - максимальная степень захода графа
Возвращает функция указатель на элемент с максимальной степенью захода
void comp_del(dyn_list &l, comp* c)
Функция удаляющая выбранную вершину списка
dyn_list &l - список переданный по адресу
comp* c - вершина которую необходимо удалить
void print_list(dyn_list l)
Функция выводящая на экран список
dyn_list l - список переданный по значению
void out_file(dyn_list l)
Записывает данные в файл.
dyn_list l - список переданный по значению
9.Входные и выходные данные
Программа получает данные из файла (по умолчанию course.txt), в котором хранится матрица инцидентности ориентированного графа. На основе считанных из файла данных строится динамический линейный список, хранящий список окрестностей ориентированного графа.
На выходе выводятся:
· список окрестностей вершин, которым задан данный граф;
· максимальная степень захода вершины ориентированного графа;
· список окрестностей вершин графа после удаления вершины с максимальной степенью захода
Компоненты списка имеют следующую структуру:
struct comp {
int name;
int okr[100];
comp* next;
};
Алгоритм функции int search (dyn_list l)
Параметры, принимаемые функцией:
dyn_list l - список переданный по значению
Рисунок 2.2 (Приложение)
Алгоритм основной функции
Анализ временной и ёмкостной сложности
Анализ временной сложности
n - количество вершин, m количество ребер
void out_file (dyn_list l)
F1=1+5Q(n)
void comp_del (dyn_list &l, comp* c)
F2=4+2(Q(m))^2*Q(n)+Q(n)
void print_list (dyn_list l)
F3=1+3Q(m)*Q(n)
void constr_list (dyn_list &l)
F4=1
bool chk_empty (dyn_list l)
F5=1
void comp_in(dyn_list &l, int n, int **ptarray, int V, int K)
F6=6+2*Q(m)*(Q(n)+1)
int search (dyn_list l)
F7=2+(4+2*Q(m))Q(n)
int search1 (dyn_list l, int n)
F8=(Q(m)^2+3)*Q(n)
int main
F=5+n*m+11Q(n)+F1+F2+F3+F4+F5+F6+F7+F8
10.Анализ ёмкостной сложности
Каждый узел динамического списка, использующегося в программе, имеет следующую структуру:
struct comp {
int name;
int okr[100];
comp* next;
}
Размер этой структуры 408 байт/
Список передается в функции с помощью следующей структуры^
struct dyn_list{
comp* head;
comp* tail;
}
n - количество вершин,
void out_file (dyn_list l)
F1=20
void comp_del (dyn_list &l, comp* c)
F2=432
void print_list (dyn_list l)
F3=20
void constr_list (dyn_list &l)
F4=8
bool chk_empty (dyn_list l)
F5=8
void comp_in(dyn_list &l, int n, int **ptarray, int V, int K)
F6=420
int search (dyn_list l)
F7=28
int search1 (dyn_list l, int n)
F8=28
int main()
F=28+408*(n+1)
11.Решение контрольных примеров
Пример 1:
Исходный граф
Рис.7
Матрица инцидентности
Рис. 8
Результат работы программы:
Список окрестностей вершин.
1 2 3
2 1 3
3 1 2 4 5
4 3 5 6
5 3 4 6
6 4 5
Максимальная степень захода 3
Список окрестностей вершин после удаления
1 2 3
2 1 3
3 1 2 4
4 3 6
6 4
Пример 2:
Исходный граф
Рис. 9
Матрица инцидентности
Рис. 10
Результат работы программы:
Список окрестностей вершин
1 2 5
2 1 3 4
3 2 8
4 2 7
5 6 1 7
6 12 5 11 7
7 4 9 11 6 5
8 3 9
9 8 10 7
10 9 14
11 7 14 6
12 13 6
13 15 12 14
14 10 15 11 13
15 14 13
Максимальная степень захода 4
Список окрестностей вершин после удаления
1 2 5
2 1 3 4
3 2 8
4 2
5 6 1
6 12 5 11
8 3 9
9 8 10
10 9 14
11 14 6
12 13 6
13 15 12 14
14 10 15 11 13
15 14 13
Пример 3:
Исходный граф
Рис. 11
Рис. 12
Результат работы программы
Список окрестностей вершин
1 2 5
2 1 8
3 8 4
4 3 9
5 6 1
6 11 5
7 11 13
8 2 3 13
9 4 14
10 15 11
11 10 6 7
12 13 16
13 7 8 14 17 12
14 9 18 13
15 19 10
16 17 19 12
17 20 16 13
18 14 20
19 16 15
20 18 17
Максимальная степень захода 5
Список окрестностей вершин после удаления
1 2 5
2 1 8
3 8 4
4 3 9
5 6 1
6 11 5
7 11
8 2 3
9 4 14
10 15 11
11 10 6 7
12 16
14 9 18
15 19 10
16 17 19 12
17 20 16
18 14 20
19 16 15
20 18 17
Исходный код программы
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <math.h>
using namespace std;
struct comp {
int name;
int okr[100];
comp* next;
};
struct dyn_list {
comp* head;
comp* tail;
};
void out_file(dyn_list l)
{
ofstream out("D://out.txt");
int u = 0;
while (l.head != NULL)
{
u = 0;
out << l.head->name + 1 << " ";
for (int i = 0; i<100; i++)
if (l.head->okr[i] != 0)
u = u + 1;
for (int j = 0; j<u; j++)
out << abs(l.head->okr[j]) << " ";
out << "\n";
l.head = l.head->next;
}
out.close();
}
void comp_del(dyn_list &l, comp* c)
{
int o = 0;
comp* k = new comp();
k = l.head;
while (k != NULL)
{
o = 0;
for (int x = 0; x<100; x++)
if (k->okr[x] != 0)
o = o + 1;
for (int m = 0; m < o; m++)
{
if (abs(k->okr[m]) == c->name + 1)
{
for (int x = m; x < o; x++)
{
k->okr[x] = k->okr[x + 1];
}
k->okr[o] = 0;
}
}
k = k->next;
}
if (c == l.head)
{
l.head = c->next;
return;
}
comp* r = new comp();
r = l.head;
while (r->next != c)
r = r->next;
r->next = c->next;
delete c;
}
void print_list(dyn_list l)
{
int u;
while (l.head != NULL)
{
u = 0;
cout << l.head->name + 1 << " ";
for (int i = 0; i<100; i++)
if (l.head->okr[i] != 0)
u = u + 1;
for (int j = 0; j<u; j++)
cout << abs(l.head->okr[j]) << " ";
cout << "\n";
l.head = l.head->next;
}
}
void constr_list(dyn_list &l)
{
l.head = NULL;
}
bool chk_empty(dyn_list l)
{
return (l.head == NULL);
}
void comp_in(dyn_list &l, int n, int **ptarray, int V, int K)
{
comp* c;
c = new comp;
c->name = n;
memset(c->okr, 0, sizeof(c->okr));
int mas = 0;
for (int f = 0; f<K; f++)
if (ptarray[n][f] != 0)
{
mas = mas + 1;
for (int l = 0; l<V; l++)
{
if ((ptarray[l][f] != 0) && (l != n))
{
if (ptarray[l][f] == -1)
c->okr[mas - 1] = -l - 1;
else
c->okr[mas - 1] = l + 1;
}
}
}
c->next = NULL;
if (chk_empty(l))
l.head = c;
else
l.tail->next = c;
l.tail = c;
}
int search(dyn_list l)
{
int max = 0, num = 0;
while (l.head != NULL)
{
max = 0;
int o = 0;
for (int k = 0; k<100; k++)
if (l.head->okr[k] != 0)
o = o + 1;
for (int i = 0; i<o; i++)
{
if (l.head->okr[i]>0)
max = max + 1;
}
if (max>num)
num = max;
l.head = l.head->next;
}
return num;
}
comp* search1(dyn_list l, int n)
{
while (l.head != NULL)
{
int o = 0;
for (int k = 0; k<100; k++)
if (l.head->okr[k] != 0)
o = o + 1;
int max = 0;
for (int j = 0; j<o; j++)
{
if (l.head->okr[j]>0)
{
max = max + 1;
}
}
if (max == n)
return l.head;
l.head = l.head->next;
}
return l.head;
}
int main()
{
setlocale(0, "");
int n, m;
cout << "Введите количество строк матрицы инциндентности";
cin >> n;
cout << "Введите колчество столбцов матрицы инциндентности";
cin >> m;
int **ptarray = new int*[n];
for (int count = 0; count < n; count++)
ptarray[count] = new int[m];
dyn_list vars;
constr_list(vars);
ifstream inp("D://course2.txt");
int buf = 0;
for (int i = 0; i<n; ++i)
{
for (int j = 0; j<m; ++j)
{
inp >> ptarray[i][j];
}
}
inp.close();
int x;
comp* p = new comp();
for (int i = 0; i<n; ++i)
{
comp_in(vars, i, ptarray, n, m);
}
int ind = 0;
while (ind != 5)
{
cout << "Для вывода на экран списка окрестностей нажмите 1" << "\n";
cout << "Для вывода максимальной степени захода нажмите 2 " << "\n";
cout << "Для удаления вершины из списка нажмите 3" << "\n";
cout << "Для вывода текущего списка в файл нажмите 4" << "\n";
cout << "Для выхода из программы нажмите 5" << "\n";
cin >> ind;
switch (ind) {
case 1:
print_list(vars);
break;
case 2:
x = search(vars);
cout << "\n" << "Максимальная степень захода " << x << "\n";
break;
case 3:
x = search(vars);
p = search1(vars, x);
if (p)
{
comp_del(vars, p);
print_list(vars);
}
break;
case 4:
out_file(vars);
break;
default:
if (ind = 5)
{
}
else
cout << "Вводите только числа указанные на экране!";
break;
}
}
system("PAUSE");
return 0;
}
Заключение
Во время выполнения курсовой работы был разработан алгоритм, решающий поставленную задачу. По составленному алгоритму была написана программа, позволяющая:
· Вводить матрицу инцидентности из файла;
· Выводить на экран и в файл список окрестностей вершин, степень захода выбранной вершины;
· Находить вершину с наибольшей степенью захода;
· Составлять список окрестности по матрице инцидентности ориентированного графа;
Приложение
Рис. 13
Рис. 14
Рис. 15
Рис. 16
Размещено на Allbest.ru
Подобные документы
Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа. Формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Анализ временной и емкостной сложности алгоритма.
курсовая работа [8,1 M], добавлен 07.09.2012Разработка программного продукта для поиска максимально удалённых вершин в графе. Характеристика ориентированного, смешанного и изоморфного графов. Обзор способов представления графа в информатике. Алгоритм поиска пути. Графический интерфейс программы.
курсовая работа [384,0 K], добавлен 10.01.2015Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов.
курсовая работа [1,1 M], добавлен 26.06.2012Теоретическое обоснование теории графов. Методы нахождения медиан графа. Задача оптимального размещения насосной станции для полива полей. Алгоритм Флойда, поиск суммарного расстояния до вершин. Функция нахождения индекса минимального значения в массиве.
курсовая работа [336,8 K], добавлен 28.05.2016Математические графы, области их применения. Способы раскраски вершин и ребер графов, задачи на их применение. Разработка алгоритма, работающего на основе операций с матрицей смежности. Описание логической структуры программы. Пример зарисовки графа.
курсовая работа [145,5 K], добавлен 27.01.2013Корректность определения кратчайших путей в графе и рёбра отрицательной длины. Анализ алгоритмов Дейкстры, Беллмана-Форда, Флойда-Уоршелла. Вычисление кратчайших расстояний между всеми парами вершин графа. Топологическая сортировка ориентированного графа.
презентация [449,3 K], добавлен 19.10.2014Рассмотрение основ работы в Microsoft Visual Studio 2010 с языком программирования С#. Реализация программы обработки данных авиапассажиров. Выбор метода ввода данных из текстового файла. Создание фильтра для обработки списка по определенным критериям.
курсовая работа [1,4 M], добавлен 17.01.2016Основные понятия и определения теории графов: теоремы и способы задания графа, сильная связность графов. Построение блок-схем алгоритма, тестирование разработанного программного обеспечения, подбор тестовых данных, анализ и исправление ошибок программы.
курсовая работа [525,6 K], добавлен 14.07.2012История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7.
контрольная работа [646,9 K], добавлен 19.01.2016Введение в Microsoft Visual Studio. Диалоговое окно "Восстановленные файлы" интегрированной среды разработки. Веб-обозреватель интегрированной среды разработки. Диалоговое окно "Проверка подлинности прокси-сервера". Сохранение и восстановление файлов.
реферат [22,0 K], добавлен 29.05.2013
