Реферат на тему операции над графами

Обновлено: 02.07.2024

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

Содержание

ЗАДАНИЯ. - 2 -
РЕФЕРАТ - 3 -
СОДЕРЖАНИЕ. - 4 -
ВВЕДЕНИЕ - 5 -
1 РАЗРАБОТКА ПРОГРАММЫ ДЛЯ РЕАЛИЗАЦИИ ГРАФА. - 6 -
1.1 АНАЛИЗ МАТЕМАТИЧЕСКИХ ТРЕБОВАНИЙ. - 8 -
1.2 КОДИРОВАНИЕ. - 18 -
1.3 ТЕСТИРОВАНИЕ. - 19 -
ЗАКЛЮЧЕНИЕ. - 21 -
ПРИЛОЖЕНИЕ А. - 22 -
ПРИЛОЖЕНИЕ Б. - 23 -
ПРИЛОЖЕНИЕ В. - 28 -
СПИСОК ЛИТЕРАТУРЫ: - 32 -

Работа содержит 1 файл

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ.doc

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Пензенский государственный педагогический университет им. В. Г. Белинского

Кафедра прикладной математики и информатики

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

Реализовать представление графа с помощью матрицы смежности. Реализовать основные операции над графами (дополнение графа, объединение графов, добавление ребра в граф, удаление вершины из графа, удаление ребра из графа, добавление вершины в граф).

Пояснительная записка содержит 30 листов, 7 рисунков, 2 таблиц, 3 приложений на 12 листах.

Дискретная Математика, ИНФОРМАТИКА, ПРОГРАММИРОВАНИЕ,ООП, С++, ГРАФ, ОПЕРЦИИ НАД ГРАФАМИ, дополнение графа, объединение графов, соединение графов, добавление ребра в граф, стягивание подграфа, удаление вершины из графа, удаление ребра из графа, добавление вершины в граф.

В работе реализован граф виде матрицы смежности на языке программирование С++. Написан код для вычисление основных операций над графами.

Исторически сложилось так, что теория графов зародилась двести с лишним лет назад именно в ходе решения головоломок. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания.

В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др. Как особый класс можно выделить задачи оптимизации на графах. Математические развлечения и головоломки тоже являются частью теории графов, например, знаменитая проблема четырех красок, интригующая математиков и по сей день. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.

Разработка программы для реализации графа.

Приведенные ниже этапы создания программы.

I этап. Создание любой программы начинается с постановки задачи или анализа требования. Изначально задача поставлена в терминах предметной области, и приведена в термины, более близкие к программированию.

• описаны исходные данные и результаты (типы, форматы, точность, способ передачи, ограничения);

• описаны задачи, реализуемой программой;

• способ обращения к программе;

• описаны возможные аварийные ситуации и ошибки пользователя.

Таким образом, функции, входные и выходные данные.

II этап. Проектирование (определение общей структуры и взаимодействия модулей). На этом этапе применилось технология нисходящего проектирования программы, основная идея которого теоретически проста: разбиение задачи на подзадачи меньшей сложности, которые можно рассматривать раздельно. При этом используется метод пошаговой детализации. Очень важной на этом этапе является спецификация интерфейсов, то есть способов взаимодействия подзадач.

Этапы проектирования и программирования совмещены во времени: в идеале сначала проектируется и кодируется верхний уровень, затем — следующий, и так далее. Такая стратегия применяется потому, что в процессе кодирования может возникнуть необходимость внести изменения, отражающиеся на модулях нижнего уровня.

IV этап. Тестирование. Этот этап записан последним, но это не значит, что тестирование не должно проводиться на предыдущих этапах. Проектирование и программирование обязательно должны сопровождаться написанием набора тестов — проверочных исходных данных и соответствующих им наборов эталонных реакций.

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

В программе проверена каждая из ветвей алгоритма. Общее число ветвей определено комбинацией всех альтернатив на каждом этапе. Отдельно проверена реакция программы на ошибочные исходные данные.

Матрица смежности — один из способов представления графа в виде матрицы.

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица Aразмера n, в которой значение элемента aij равно числу ребёр из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного гр афа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

Ниже приведён пример (рис 1.) неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, так что, в зависимости от конкретных приложений, элемент a11 может считаться равным либо единице (как показано ниже), либо двум.

Рисунок 1– Граф и представления графа в виде матрицы.

Матрица смежности полного графа Kn содержит единицы во всех своих элементах, кроме главной диагонали, на которой расположены нули.

Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

Матрица смежности неориентированного г рафа симметрична , а значит обладает действительными собственными значениями и ортогональным базисом из собственных векторов. Набор её собственных значений называется спектром графа, и является основным предметом изучения спектральной теории графов .

Два графа G1 и G2 с матрицами смежности A1 и A2 являются изо морфными если и только если существует перестановочная матрица P, такая что

Из этого следует, что матрицы A1 и A2 подобны , а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны.

Если A — матрица смежности графа G, то матрица A m обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер.

Матрица смежности и списки смежности являются основными структурами данных, которые используются для представления графов в компьютерных программах

Использование матрицы смежности предпочтительно только в случае неразряженных графов, с большим числом ребёр, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразряженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно n2 / 8 байт памяти, что может быть на порядок лучше списков смежности.

Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.

Подобные документы

Множеством именуется некоторая совокупность элементов, объединенных по какому-либо признаку. Над множествами определяют операции, во многом сходные с арифметическими. Операции над множествами интерпретируют геометрически с помощью диаграмм Эйлера-Венна.

реферат, добавлен 03.02.2009

Понятие множества, его обозначения. Операции объединения, пересечения и дополнения множеств. Свойства счетных множеств. История развития представлений о числе, появление множества натуральных, рациональных и действительных чисел, операции с ними.

курсовая работа, добавлен 07.12.2012

Особенности системы индексных обозначений. Специфика суммирования в тензорной алгебре. Главные операции в алгебре, которые называются сложением, умножением и свертыванием. Применение операции внутреннего умножения. Симметричные и антисимметричные объекты.

реферат, добавлен 07.12.2009

Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.

контрольная работа, добавлен 11.03.2011

Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.

презентация, добавлен 16.01.2015

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

контрольная работа, добавлен 08.12.2009

Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".

курсовая работа, добавлен 08.10.2014

Определение понятия множеств Г. Кантора, их примеры и обозначения. Способы задания, включение и равенство множеств, операции над ними: объединение, пересечения, разность, дополнение, их определение и наглядное представление на диаграмме Эйлера-Венна.

реферат, добавлен 11.03.2009

Сущность теории множеств и особенности ее практического применения. Операции над множествами и их главные закономерности. Порядок нахождения области определения функции, участков ее возрастания и убывания. Определение вероятности исследуемого действия.

контрольная работа, добавлен 02.12.2011

Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.

Полным графом G называется граф с п вершинами без петель, кратных и противоположных дуг (ориентация безразлична), у которого любые две вершины соединены ребром. Например

Бинарные операции над графами

Бинарные операции включают два графа.

Бинарные операции над графами. Наиболее важными бинарными операциями являются: объединение, пересечение, кольцевая сумма и дополнение. Операции могут выполняться как графически, так и с помощью матриц смежности каждого графа. Рассмотрим все бинарные операции двумя способами.

Объединение. Граф G=(X,А) называется объединением (или наложением) графов G₁₌ (Х₁, А₁) и G₂ = (Х₂, А₂), если множество его вершин является объединением Х₁ и Х₂, а множество ребер - объединением А₁ и А₂: Другими словами, в один граф добавляются все вершины и ребра одного и второго графа (одинаковые остаются по одному).

G = G₁ G₂ = (X₁ X₂, А₁ А₂).

В матрице смежности объединенного графа работает операция дизъюнкция по таблице истинности. Матрицы смежности графов G₁ и G₂ имеют вид

Объединение графов G₁ G₂ выглядит так

Пересечение. Граф G=(X,А) называется пересечением графов G₁=(Х₁,А₁) и G₂=(Х₂,А₂), если множество его вершин является пересечением Х₁ и Х₂, а множество ребер - пересечением А₁ и A₂: G = G₁ G₂ =(X₁ X₂, A₁ А₂). Другими словами, в один граф добавляются только те вершины и ребра, которые одинаковые и у одного и у второго графа.

Матрица смежности пересеченного графа G₁ G₂ составляется по конъюнкции и выглядит так

3. Кольцевая сумма. Граф G=(X,А)=G₁ G₂, порожденный на множестве ребер A₁A₂, представляет собой кольцевую сумму двух графов G₁=(Х₁,А₁) и G₂ =(Х₂, А₂). Другими словами, в кольцевой граф добавляются те ребра, которые разные у обоих графов, а одинаковые убираются (вершины остаются все). Кольцевая сумма графов G₁ и G₂ показана на рисунке:

Матрица смежности кольцевого графа G₁ G₂ составляется по сложению по модулю два и выглядит так

4. Разность. Граф G=(X,А) называется разностью графов G₁=(Х₁,А₁) и G₂=(Х₂,А₂), если множество его вершин является разностью Х₁ и Х₂, а множество ребер - разностью А₁ и. A₂: G = G₁ G₂ = (X₁ X₂, А₁ А₂). Операция разности некоммутативна, то есть G₁ G₂ G₂ G_1. Другими словами, в разностный граф добавляются только те ребра, которые есть у первого графа, но нет у второго (вершины остаются все).

Матрица смежности разностного графа G₁ G₂ составляется по вычитанию (1-1=0, 1-0=1, 0-1=0, 0-0=0) и выглядит так

5. Дополнением графа G=(X,А₁) является граф =(X,А₂) , у которого множество вершин совпадает с множеством вершин графа G, а множество ребер, не принадлежит графу G, то есть в любые две вершины смежны, если только они не смежны в G. Другими словами, в дополненный граф добавляются только те ребра, которых не хватает до полного графа (вершины остаются все).

Матрица смежности полного графа, состоит из всех 1, кроме главной диагонали. Матрица смежности дополненного графа G₁ G₂ составляется инверсии и выглядит так

Унарные операции над графами

Унарные операции определены на одном графе. Рассмотрим их.

Удаление вершины. Если x_i - вершина графа G=(X,А), то G-i является графом, получившимся после удаления из графа G вершимы i и всех ребер, инцидентных этой вершине. Удаление из графа вершины влечет удаление всех ребер, входящих в эту вершину. Удаление вершины 2 показано на рисунке:

- исходный граф G - граф G-2

Удаление ребра или удаление дуги. Если а_i - ребро графа G = (X, А), то G-а_i является графом, получающимся после удаления из G ребра а_i. Заметим, что концевые вершины ребра а_i, не удаляются. После удаления всех ребер граф оказывается без ребер. Удаление ребер (5,4) и (1,2) показано на рисунке:

- исходный граф G - граф G-(5,4),(1,2)

Замыкание или отождествление. Говорят, что пара вершин х_i и х_j в графе G замыкается (или отождествляется), если они замыкаются такой новой вершиной, что все дуги в графе G, инцидентные х_i и х_j, становятся инцидентными новой вершине. После замыкания, дуга или ребро, находящееся между вершинами, станет петлей. Например, результат замыкания вершин 2 и 3 показан на рисунке:

- исходный граф G

Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин. После стягивания, две вершины совмещаются в одну, а ребро или дуга, находящаяся между ними, удаляется. Граф, изображенный на следующем рисунке, получен стягиванием ребра (1,5):

- исходный граф G

Самостоятельная работа студентов

Переписать лекцию в тетрадь и прислать фото

Выполнить все бинарные операции (кроме дополнения) двумя способами для следующих графов:

Выполнить все унарные операции для следующего графа по следующим параметрам (удаление вершины 3, удаление дуги (46), замыкание вершин 1 и 3, стягивание дуги (46)).

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

type TUk1=^TEl1; //элемент списка вершин

TEl=record //элемент списка смежности

Head:TUk; //указатель на начало списка

Схематичное представление списка смежности ориентированного графа представлено на рисунке 2.1

Рисунок 2.3 – Схема списка смежности

Алгоритм нахождения источников ориентированного графа представлен на рисунке 2.4.

Рисунок 2.4 - Алгоритм нахождения источников орграфа

2.3 Описание программной реализации

2.3.1 Описание процедур и функций языка

Процедура New – резервирует фрагмент кучи для размещения переменной; формат обращения

TP – типизированный указатель. За одно обращение к процедуре можно зарезервировать не более 65521 байт динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.

Процедура Dispose – возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за типизированным указателем; формат обращения

TP – типизированный указатель. При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения.

2.3.2 Описание функций работы с динамической памятью, графами

Для решения поставленной задачи были разработаны следующие процедуры и функции:

1) procedure AddVer(n:integer); - добавление в список смежности вершины с номером n;

2) procedure AddDug(n,m:integer); - добавление в список дуги (n,m). n и m номера вершин источника дуги и стока соответственно;

3) procedure DelList(p:TUk1); - удаление списка смежных вершин. p – указатель на начало списка;

4) procedure DelVer(n:integer); - удаление вершины с номером n;

5) procedure DelDug(n,m:integer); - удаление дуги (n,m). n и m номера вершин источника дуги и стока соответственно;

6) procedure PrintGraph; - вывод списка смежности на экран в виде матрицы смежности;

7) procedure FindIstok; - поиск и вывод на экран всех источников орграфа.

Задание, выданное на летнюю практику, поставило определенные задачи:

1) научится создавать связные структуры данных, используя указатели;

2) научится создавать и манипулировать динамическими структурами данных, такими как связные списки, очереди и стеки;

3) понять работу различных приложений со связными структурами данных.

Решение выданного задания было реализовано с помощью языка программирования Паскаль.

Во время прохождения учебной практики был закреплен теоретический материал по разработке динамических структур данных, были получены практические навыки реализации динамических структур данных на языке высокого уровня для представления и обработки графов.

Читайте также: