Графы

  • 23 дек. 2013 г.
  • 6128 Слова
Министерство образования Российской Федерации
Поморский государственный университет им. М.В. Ломоносова
Математический факультет
Кафедра алгебры и геометрии

КУРСОВАЯ РАБОТА
на тему: «Матрицы в теории графов»

Выполнила студентка
2 курса, 22 группы,
очного отделения
математического факультета
Научный руководитель
Кандидат
физико-математических наук,
доцент кафедры алгебры игеометрии

Архангельск - 2010

Оглавление

Введение
Глава 1. Теоретическая часть
1.1 Основные понятия
1.2 Способы задания графов
1.2.1 Латинская матрица
1.2.2 Матрица смежностей
1.2.3 Матрица инциденций
1.2.4 Матрицы связности и достижимости. Матрица контрдостижимости
1.3 Метрические характеристики графа
1.4 Выявление маршрутов с заданным количеством рёбер
1.5 Определение экстремальных путей награфах. Метод Шимбелла
1.6 Нахождение кратчайших путей. Алгоритм Дейкстры
1.7 Алгоритм нахождения максимального пути
Глава 2. Практическая часть
Заключение
Список литературы

Введение

Теория графов применяется при анализе функционирования сложных систем, таких как сети железных дорог, телефонные и компьютерные сети, ирригационные системы. Эта теория традиционно является эффективнымаппаратом формализации задач экономической и планово-производственной практики, применяется в автоматизации управления производством, в календарном и сетевом планировании.
В теоретико-множественной и геометрической формах определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойстваграфов. Матричная форма задания графов обладает достаточной наглядностью при любой степени сложности графа и, что самое важное, позволяет автоматизировать процесс обработки информации, представленной в терминах теории графов, – любая матрица графа может быть введена в ЭВМ.
В настоящее время интенсивно развивается раздел теории графов, касающийся построения маршрутов, удовлетворяющих специальнымограничениям: эйлеровы и гамильтоновы циклы; маршруты, избегающие запрещенных переходов; самонепересекающиеся и непересекающиеся цепи; бинаправленные двойные обходы и т.д.
Интерес к задачам маршрутизации объясняется их использованием в качестве математических моделей многих проблем управления и автоматизации проектирования.
Цель моей курсовой работы – научиться решать классические задачи, касающиеся различныхматриц в теории графов.
Задачами данной работы будут:
1. изучить основные матрицы графов и их теоремы;
2. научиться строить матрицы по графическому рисунку графа и графы по данной матрице;
3. изучить метрические характеристики графов, связанные с матрицами;
4. научиться находить пути графа по матрице (минимальные и максимальные).
теорема путь граф матрица

Глава 1. Теоретическая часть

1.1Основные понятия

Пусть S – непустое множество, V(2) – множество всех его двухэлементных подмножеств, U ϵ V(2).
Пара (S, U) называется неориентированным графом. Элементы множества S называются вершинами графа, а элементы множества U – рёбрами.
Граф G = (S, U) – это конечное множество вершин S и рёбер U.
Если в паре вершин xi и xj указано направление связи, то есть какая-то из вершин являетсяпервой, то соединяющий их отрезок uk называется дугой, а вершины, определяющие дугу, называются концевыми вершинами.
Если концевые вершины совпадают, то дугу называют петлёй.
В графе G могут существовать дуги (рёбра) о одинаковыми концевыми вершинами. Такие дуги называются параллельными.
Если в графе G = (S, U) все элементы множества U изображаются дугами, то граф называется ориентированнымили орграфом, если рёбрами, то неориентированным
Два ребра называются смежными, если они имеют общий конец.
Вершина x1 и ребро u1 называются инцидентными, если x1 является концом ребра u1, и неинцидентными в противном случае.
Граф G называется, простым, если он не содержит петель и параллельных дуг.
Типы графов:
- Мультиграф, в нём не допускаются петли, но...
tracking img