IX Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Матрицы графов

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Давыдова Д.С. 1

---

1МАОУ СШ № 59 "Перспектива"

Блюмин С.Л. 1

---

1ЛГТУ

Работа в формате PDF

126.9 KB

Автор работы награжден дипломом победителя III степени

Диплом школьникаСвидетельство руководителя

Введение

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

Цель

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

1.2 Задачи:

Научиться расписывать матрицы для графов

Освоить действия над матрицами

Разобрать и показать на конкретных примерах получение лапласиана графа

Рассмотреть различные применения 

В ходе работы я буду использовать учебные пособия Л.Н.Домнина, Белоусова И. В и Селезневой С.Н.

2. Основная часть

2.1. Типология графовых структур

[1](Неориентированным) графом G называется пара (V, E), где V — непустое конечное множество вершин; E — конечное множество ребер, причем каждому ребру e ∈ E сопоставлена неупорядоченная пара вершин, т.е. e = (v,w), где v,w ∈ V. Обозначения: 

V(G) — множество вершин графа G,

E(G) — множество ребер графа G.

Типы графов:

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

рёбра которого имеют направление. Направленные рёбра также именуются  дугами. 

неориентированные графы: 

ни одному ребру которого не присвоено направление. 

смешанные графы: 

рёбра могут быть ориентированными, а некоторые — неориентированными.  

2.2. Матрицы ориентированных графов

Во время действия алгоритма часто требуется модифицировать граф. [2]Матрицей A размера m×n называется прямоугольная таблица чисел, функций или алгебраических выражений, содержащая m строк и n столбцов. Числа m и n определяют размер матрицы. Числа, функции или алгебраические выражения, образующие матрицу, называются матричными элементами. Будем обозначать их строчными буквами с двумя индексами. Первый индекс i=1,2,. . . ,m указывает номер строки, а второй индекс j=1,2,…,n — номер столбца, в которых располагается соответствующий элемент. Представление графа с помощью матриц предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.

[3]Матрица смежности. Определим матрицу смежности как симметричную квадратную матрицу А=[a_i,j] порядка n, в которой элемент a_i,jравен 1, если в графе есть ребро {v_i , v_j }, т. е. v_i и v_jсмежны, и 0, если такого ребра нет.

Матрица инцидентности. Определим матрицу инцидентности графа как прямоугольную матрицу B=[b_i,j] размера n×m, в которой элементb_i,jравен 1, если вершина v_iинцидентна ребруe_j, и 0 в противном случае.

Диагональная матрица. Последовательность a₁₁, a₂₂, . . . , a_nn диагональных матричных элементов образует главную диагональ квадратной матрицы, идущую из ее левого верхнего угла в правый нижний угол.

Транспонированная матрица. Переход от матрицы A к матрице A^T , в которой строки и столбцы поменялись местами с сохранением порядка.

2.3. Действия над матрицами

Сложение матриц. Суммой A + B двух матриц A = (a_i,j) и B = (b_i,j) одинакового размера m × n называется матрица C = (c_i,j), элементы которой

c_i,j = a_i,j + b_i,j для всех i=1,2,. . . ,m и j=1,2,. . . ,n.

Умножение матриц. Умножение матрицы A на матрицу B определено, лишь когда число столбцов первой матрицы в произведении равно числу строк второй. Тогда произведением матриц A m×k B k×n называется матрица C m×n , каждый элемент которой c_i,j равен сумме попарных произведений элементов i–й строки матрицы A на соответствующие элементы j–го столбца матрицы B. ( см. приложение 1)

3. Создание матриц

I – матрица инцидентности

A_o – матрица смежности

I^T – транспонированная матрица инцидентности

A_o^T – транспонированная матрица смежности

A_o + A_o^T = А

D – диагональная матрица

I × I^T = L

A + D = L

3.1 Первыйграф

I

I^T

A_o

A_o^T

A

D

I × I^T = L

D + A = L

3.2. Второй граф

I

I^T

A_o

A_o^T

A

D

I × I^T = L

D + A = L

4.Преимущества матричного подхода

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

5.Практическое применение графов

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

6. Заключение

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

7. Список литературы

Селезнева С.Н. C 29 Основы дискретной математики: Учебное пособие. – М.: Издательский отдел факультета ВМК МГУ имени М.А. Ломоносова (лицензия ИД N 05899 от 24.09.2001 г.); МАКС Пресс, 2010. – 60 с.

Белоусов И. В. МАТРИЦЫ И ОПРЕДЕЛИТЕЛИ: учебное пособие по линейной алгебре. / Кишинев: 2006/.

Элементы теории графов: учеб. Пособие / Л.Н.Домнин. – Пенза: Изд-во Пенз. Гос. Ун-та, 2007. – 144 с.: 75 ил., 13 табл., библиогр., 18 назв.

Министерство образования и науки Российской Федерации Федеральное агенство по образованию. Елецкий государственный университет им. И. А. Бунина. О. Б. Гладких, О. Н. Белых. Основные понятия теории графов. Учебное пособие
2008

8. Приложения.

1.