Задача перехода для ориентированного графа: матрица смежности - матрица инцидентности
Преобразование матрицы смежности ориентированного графа в матрицу инцидентности. Бьерн Страуструп как разработчик языка Си++. Матрица Инцидентности как отношение между ребром и его концевыми вершинами. Листинг программы, руководство пользователя.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 30.03.2015 |
| Размер файла | 2,1 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
[Введите текст]
Министерство образования Российской Федерации
Уфимский государственный авиационный технический университет
Факультет информатики и робототехники
Курсовая работа
по дисциплине: Дискретная математика
«Задача перехода для ориентированного графа: матрица смежности - матрица инцидентности»
г. Уфа
2013 г.
Цель работы
Целью курсовой работы является закрепление основ и углубление знаний приемов программирования на языке С++, получение практических навыков в создании программного продукта.
На языке программирования C++ разработать программу решения задачи Задача перехода для ориентированного графа: матрица смежности - матрица инцидентности.
Введение
В теоретико-множественной и геометрической форм определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов. Матричная форма задания графов обладает достаточной наглядностью при любой степени сложности графа и, что самое важное, позволяет автоматизировать процесс обработки информации, представленной в терминах теории графов, - любая матрица графа может быть введена в ЭВМ.
При задании графов в матричной форме могут учитываться либо отношения смежностей (вершин или ребер (дуг)), либо отображения инцидентности (вершин и ребер (дуг)). В связи с этим матрицы графов делятся на два основных класса: матрицы смежностей и матрицы инциденций.
В данной работе рассматривается преобразование матрицы смежности ориентированного графа в матрицу инцидентности.
1. Математическая часть
2. Описание используемого программного обеспечения
Разработчиком языка Си++ является Бьерн Страуструп. В своей работе он опирался на опыт создателей языков Симула, Модула 2, абстрактных типов данных. Основные работы велись в исследовательском центре компании Bell Labs.
Непосредственный предшественник Си++ - язык Си с классами - появился в 1979 году, а в 1997 году был принят международный стандарт Си++, который фактически подвел итоги его 20-летнего развития. Принятие стандарта обеспечило единообразие всех реализаций языка Си++. Не менее важным результатом стандартизации стало то, что в процессе выработки и утверждения стандарта язык был уточнен и дополнен рядом существенных возможностей.
Язык Си++ является универсальным языком программирования, в дополнение к которому разработан набор разнообразных библиотек. Поэтому, строго говоря, он позволяет решить практически любую задачу программирования. Тем не менее, в силу разных причин (не всегда технических) для каких-то типов задач он употребляется чаще, а для каких-то - реже.
Си++ как преемник языка Си широко используется в системном программировании. На нем можно писать высокоэффективные программы, в том числе операционные системы, драйверы и т.п. Язык Си++ - один из основных языков разработки трансляторов.
Поскольку системное программное обеспечение часто бывает написано на языке Си или Си++, то и программные интерфейсы к подсистемам ОС тоже часто пишут на Си++. Соответственно, те программы, даже и прикладные, которые взаимодействуют с операционными системами, написаны на языке Си++.
Распределенные системы, функционирующие на разных компьютерах, также разрабатываются на языке Си++. Этому способствует то, что у широко распространенных компонентных моделей CORBA и COM есть удобные интерфейсы на языке Си++.
Обработка сложных структур данных - текста, бизнес-информации, Internet-страниц и т.п. - одна из наиболее распространенных возможностей применения языка. В прикладном программировании, наверное, проще назвать те области, где язык Си++ применяется мало.
Разработка графического пользовательского интерфейса на языке Си++ выполняется, в основном, тогда, когда необходимо разрабатывать сложные, нестандартные интерфейсы. Простые программы чаще пишутся на языках Visual Basic, Java и т.п.
В целом надо сказать, что язык Си++ в настоящее время является одним из наиболее распространенных языков программирования в мире.
3. Используемые функции
# include - обеспечивает преимущества использования заголовочных файлов, которые содержат операторы C++ или программные определения.
Cout - выводит сообщение, которое запрашивает какие-либо данные.
Cin - чтение введенных данных.
For - Цикл со счётчиком, в котором некоторая переменная изменяет своё значение от заданного начального значения до конечного значения с некоторым шагом, и для каждого значения этой переменной тело цикла выполняется один раз, в котором указывается счётчик (так называемая «переменная цикла»), требуемое количество проходов (или граничное значение счётчика) и, возможно, шаг, с которым изменяется счётчик If - Условный оператор реализует выполнение определённых команд при условии, что некоторое логическое выражение (условие) принимает значение «истина» true.
4. Решение задачи вручную
Рис. 1
Дан ориентированный граф с 5 вершинами и 6 маршрутами. Построим матрицу смежности:
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.
Матрицей смежности вершин ориентированного графа G называется квадратная матрица A(G)=aij порядка n (n - число вершин графа), элементы которой aij равны числу дуг, исходящих из вершины xi и заходящих в вершину xj.
Из определения следует, что сумма элементов i-й строки матрицы A(G) орграфа равна полустепени исхода +(xi), а по i-му столбцу - полустепени захода -(xi). По-прежнему элементы этой матрицы - целые положительные числа и число ноль. Матрица смежностей вершин орграфа может оказаться симметричной относительно главной диагонали лишь в редких частных случаях.
Сумма элементов -й строки равна , то есть
Аналогично сумма элементов -го стоблца равна , то есть .
Следовательно, матрица смежности примет вид:
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
1 0 0 0 0
1 1 0 0 0
Исходя из матрицы смежности мы можем построить матрицу инцидентности.
Инцидентность -- отношение между ребром и его концевыми вершинами, т. е. если в графе -- вершины, а -- соединяющее их ребро, то вершина и ребро инцидентны, вершина и ребро также инцидентны.
Необходимо отметить, что между строками матрицы инцидентности B(G) существует очевидная зависимость. Так как каждый столбец этой матрицы содержит только два единичных элемента или состоит только из нулей, если столбец соответствует петле, то сумма по модулю 2 всех строк равна нулю. Поэтому без потери информации о графе вместо матрицы B(G) можно рассматривать сокращенную матрицу Bo(G), получаемую из B(G) вычеркиванием любой строки (чаще всего вычеркивается последняя строка). Таким образом, из p строк матрицы B(G) связного графа (см. п. 5) одна строка всегда линейно зависима, т.е. ранг матрицы B(G) не может превышать p-1 (ранг матрицы B(G) в точности равен p-1).
Матрицей инцидентности (инциденций) ориентированного графа называется матрица , для которой , если вершина является началом дуги , , если является концом дуги , в остальных случаях .
Элементы матрицы определяются следующим образом:
1, если вершина xi является началом дуги ej
bij =-1, если вершина xi является концом дуги ej;
0, если вершина xi не инцидентна дугу ej .
Матрица инцидентности данного орграфа имеет вид:
-1 1 -1 0 -1 0
1 0 0 -1 0 0
0 -1 0 0 0 1
0 0 1 0 0 -1
0 0 0 1 1 0
5. Листинг программы
#include <iostream.h>
#include<conio.h>
#include<stdio.h>
#include <iomanip.h>
#include <windows.h>
#include <winuser.h>
#pragma hdrstop
//-----------------------------------------------------#pragma argsused
char* rus(const char* text)
{char *bufRus=new char[strlen(text)];
CharToOem(text, bufRus);
return bufRus;}
int main(int argc, char* argv[])
{int **matrix, **matrix1, **smej, *mat, str[30], n=0, m=0, i=0, j=0, mg=0, t=0, y=0, k=0, g=0, v=0, q;
cout<<rus("Введите количество остановок: ");
cin>>n;
cout<<rus("Введите количество маршрутов: ");
cin>>m;
for (i = 0; i < m; i++) {
cout<<rus("Введите количество остановок в ")<<i+1<< rus(" маршруте: ");
cin>>str[i];
t=str[i]+t-1;
g=g+str[i];}
mat=new int[g];
for (i = 0; i < m; i++){
cout<<rus("Остановки ")<<i+1<<rus("-ого маршрута через пробел")<<endl;
for (j = 0; j < str[i]; j++) {cin>>mat[y];y++;}}
matrix1=new int*[2];
for(i=0;i<2;i++)
matrix1[i]=new int[t];
matrix1[0][0]=mat[0]; matrix1[1][0]=mat[1];
mg=str[0]-1;
for (j=1; j<t; j++)
{i=0; if (j==mg){k++; matrix1[i][j]=mat[j+k]; matrix1[i+1][j]=mat[j+1+k];mg=str[k]-1+mg;}
else { matrix1[i][j]=mat[j+k]; matrix1[i+1][j]=mat[j+k+1];}}
cout<<rus("Матрица инцедентности вершин ребрам")<<endl;
for(int i=0; i<2; i++){
for(int j=0; j<t; j++){
cout<<setw(4)<<matrix1[i][j];}
cout<<"\n\n";}
matrix=new int*[n];
for(i=0;i<n;i++)
matrix[i]=new int[t];
cout<<rus("Матрица смежности вершин ")<<endl;;
smej=new int*[n];
for(i=0;i<n;i++)
smej[i]=new int[n];
{cout<<rus("орграфа")<<endl;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){ smej[i][j]=0;
for(int x=0; x<1; ++x){
for(int b=0; b<t; b++){
if (i+1==matrix1[x][b] && j+1==matrix1[x+1][b]) {smej[i][j]=1;}}}}}}
for(i=0; i<n; i++){
for(j=0; j<n; j++){
cout<<setw(4)<<smej[i][j];}
cout<<"\n\n";}
cout<<rus("Матрица инцидентности ")<<endl;
{cout<<rus("орграфа")<<endl;
for(int j=0; j<t; j++){
for(int i=0; i<n; i++){matrix[i][j]=0;
for(int x=0; x<1; ++x){if (i+1==matrix1[x][j]){matrix[i][j]=1;} }
for(int x=1; x<2; ++x){if (i+1==matrix1[x][j]){matrix[i][j]=-1;} }}}}
for(i=0; i<n; i++){
for(j=0; j<t; j++){cout<<setw(4)<<matrix[i][j];}
cout<<"\n\n";}
system("pause");
return 0;}
матрица идентичность программа листинг
6. Руководство пользователя
После запуска программа запрашивает количество вершин, количество маршрутов и какие вершины соответствуют данным маршрутам, тем самым создавая ориентированный граф. Затем формирует матрицу инцидентности вершин заданным ребрам. Далее формирует матрицу смежности, из которой в дальнейшем формируется матрица инцидентности заданного орграфа.
Рис. 2
После нажатия любой клавиши программа завершает свою работу.
Вывод
На языке программирования C++ разработана программа перехода для ориентированного графа: матрица смежности - матрица инцидентности. Так же выяснили что по матрице смежности ребер графа (орграфа) всегда можно определить ребра графа (дуги орграфа) как пары инцидентных им вершин, а для графов с параллельными ребрами (дугами), кроме того, и кратности ребер (дуг).
Однако если ребра (дуги) были пронумерованы, то восстановить их номера по матрице смежности невозможно. В этом смысле матрица инцидентности оказывается более информативной, чем матрица смежности, поскольку позволяет получить полную информацию о ребрах (дугах), включая их нумерацию.
Рассмотренные в этом параграфе матрицы графов играют большую роль в теории графов. Существуют и другие матрицы графов, однако их роль менее значительна.
Список использованной литературы
1. Нейбауэр. А. моя первая программа на С/С++./ Пер. с англ. - СПб.: Питер, 1996.
2. Штилт. Г. Самоучитель С++ 3-е изд./ Пер. с англ. - СПб.: ВНV-Санкт-Петербург, 1998.
3. Подбельский В.В., Фомин С.С. Программирование на языке СИ - М.: Финансы и статистика, 1999.
4. Подбельский В.В. Язык Си++. - М.: Финансы и статистика, 1999.
5. Касаткин А.И., Вальвачев А.Н. от Turbo C к Borland C++/ Под ред. А.И. Касаткина, - Минск: Вышейшая школа, 1992.
6. Березин Б.И., Березин С.Б. Начальный курс С и С++. - М.: Диалог-Мифи, 1996.
Размещено на Allbest.ru
...Подобные документы
Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Задача о кенигсбергских мостах, четырех красках, выходе из лабиринта. Матрица инцидентности для неориентированного и (ориентированного) графа. Степень вершины графа. Ориентированное дерево. Линейные диаграммы или графики Ганта. Метод критического пути.
презентация [258,0 K], добавлен 23.06.2013Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.
реферат [81,0 K], добавлен 23.11.2008Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
лабораторная работа [42,2 K], добавлен 11.03.2012Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа [225,5 K], добавлен 14.05.2012Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Разработка логико-формальной модели описания методики изготовления винных изделий. Разделение ингредиентов и продукции на множества. Исследование на рефлексивность, транзитивность, симметричность. Построение графа, матрицы смежности и инцидентности.
контрольная работа [165,2 K], добавлен 07.06.2010Построение логических взаимосвязей между цветами при помощи аппарата дискретной математики. Структуры объекта в виде множеств, граф отношений между ними. Исследование на рефлексивность, транзитивность, симметричность. Матрицы смежности и инцидентности.
контрольная работа [129,4 K], добавлен 07.06.2010Понятия теории графов. Понятия смежности, инцидентности и степени. Маршруты и пути. Матрицы смежности и инцедентности. Алгоритм поиска минимального пути в ненагруженном ориентированном орграфе на любом языке программирования, алгоритм фронта волны.
курсовая работа [466,3 K], добавлен 28.04.2011История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Понятие "граф" и его матричное представление. Свойства матриц смежности и инцидентности. Свойства маршрутов, цепей и циклов. Задача нахождения центральных вершин графа, его метрические характеристики. Приложение теории графов в областях науки и техники.
курсовая работа [271,1 K], добавлен 09.05.2015Алгоритм перехода к графическому представлению для неориентированного графа. Количество вершин неориентированного графа. Чтение из матрицы смежностей. Связи между вершинами в матрице. Задание координат вершин в зависимости от количества секторов.
лабораторная работа [34,0 K], добавлен 29.04.2011Граф как совокупность объектов со связями между ними. Характеристики ориентированного и смешанного графов. Алгоритм поиска кратчайшего пути между вершинами, алгоритм дейкстры. Алгебраическое построение матрицы смежности, фундаментальных резервов и циклов.
методичка [29,4 M], добавлен 07.06.2009Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
презентация [36,1 K], добавлен 16.09.2013Построение диаграммы псевдографа, матрицы инцидентности и матрицы соседства вершин. Восстановление дерева по вектору с помощью алгоритма Прюфера. Построение таблицы истинности для функции и совершенной конъюнктивной и дизъюнктивной нормальной форм.
контрольная работа [181,9 K], добавлен 25.09.2013Понятие матрицы достижимости и связности. Операция удаления вершины из графа. Алгоритм выделения компонент сильной связности. Разработка и листинг программы на языке Turbo Pascal, осуществляющей вычисление матрицы достижимости по заданному алгоритму.
курсовая работа [584,3 K], добавлен 26.04.2011Понятие "матрица" в математике. Операция умножения (деления) матрицы любого размера на произвольное число. Операция и свойства умножения двух матриц. Транспонированная матрица – матрица, полученная из исходной матрицы с заменой строк на столбцы.
контрольная работа [26,2 K], добавлен 21.07.2010Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009
