Разработка приложения для поиска максимально удалённых вершин в графе - Курсовая работа

1.6 Обобщение понятия графа 1.7 Способы представления графа в информатике 2.2 Классы и диаграмма классовОбъекты представляются как вершины, или узлы графа, а связи - как дуги, или ребра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или ребрах. Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение "Википедии" можно смоделировать при помощи ориентированного графа (орграф), в котором вершины - это статьи, а дуги (ориентированные ребра) - гиперссылки. E - это множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых ребрами.Ориентированный граф (сокращенно орграф) G - это упорядоченная пара G := (V, A), для которой выполнены следующие условия: · V - это непустое множество вершин или узлов, ·Записывается упорядоченной тройкой G := (V, E, A), где V, E и A определены так же, как выше.Граф G называется изоморфным графу H, если существует биекция f из множества вершин графа G в множество вершин графа H, обладающая следующим свойством: если в графе G есть ребро из вершиныПутем (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром. Циклом называют путь, в котором первая и последняя вершины совпадают. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Путь (или цикл) называют простым, если ребра в нем не повторяются; элементарным, если он простой и вершины в нем не повторяются. · Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).· двудольным, если его вершины можно разбить на два непересекающихся подмножества V_1 и V_2 так, что всякое ребро соединяет вершину из V_1 с вершиной из V_2. Более абстрактно, граф можно задать как тройку (V, E, ?), где V и E - некоторые множества (вершин и ребер, соотв.), а ? - функция инцидентности (или инцидентор), сопоставляющая каждому ребру e ? E (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается: · 1, в случае, если связь j «выходит» из вершины i, ·-1, если связь «входит» в вершину, · 0, во всех остальных случаях (то есть если связь является петлей или связь не инцидентна вершине) Пусть эта процедура для каждой вершины возвращает длину самого длинного пути от этой вершины до некоторого листа (на рисунке около каждой вершины написано значение, которое вычислить эта процедура). NODE_TYPE NODETYPE = NODE_TYPE.NOT_CONNECTED; //0 - Not connected, 1 - OK node, 2 - Path node if (!PATHNODES.Contains(i)) foreach (GRAPHEDGE edge in graph.edges)Результатом курсовой работы является приложение, позволяющее найти максимально удаленные вершины в графе.

Содержание

Введение

1. Теория графов

1.1 Ориентированный граф

1.2 Смешанный граф

1.3 Изоморфные графы

1.4 Прочие связанные определения

Результатом курсовой работы является приложение, позволяющее найти максимально удаленные вершины в графе. Программный продукт имеет графический интерфейс и имеет возможность сохранения и загрузки графов. Приложение реализовано с помощью языка программирования Microsoft Visual C#, с использованием среды разработки Microsoft Visual Studio 2012.

Введение

Появление компьютеров стало прорывом для всего человечества. В настоящее время с помощью них возможно производить расчеты с огромной скоростью. Они позволяют решать разнообразные задачи, одной из которых является поиск и составление путей от пункта А в пункт Б. Для таких задач наиболее применима теория графов.

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

Приложение разработано с помощью языка программирования Microsoft Visual C#, так как функционал данного языка программирования позволяет максимально быстро решить задачи такого типа. Выбранный нами язык программирования работает с библиотекой Microsoft .net framework, которая включает в себя огромное количество средств для работы с данными такого рода и позволяет значительно ускорить процесс создания приложения.

В качестве среды разработки, была использована среда Microsoft Visual Studio версии 12, так как данная среда включает в себя широкий набор инструментов для управления и создания различных компонентов программного продукта (графический интерфейс, диаграмма классов и т.п.)1. Wikipedia/ Википедия. Теория графов

2. Джон Шарп. Microsoft Visual C# 2008 Step by Step (Изучение Microsoft Visual C# 2008 шаг за шагом) / Джон Шарп.

3. Джейми Плендерлейт. Microsoft Visual Studio 2008 Programming (Программирование в Microsoft Visual Studio 2008) / Джейми Плендерлейт, Стив Бунн.

4. Фрэнк Харари. Теория графов / Фрэнк Харари.

Размещено на