Введение
Теория графов постоянно развивающийся раздел математики. Графами представляют различные схемы: электрические цепи, авиалинии, метро, железные дороги, социограммы. В настоящее время трудно указать область человеческой деятельности, в которой нельзя было бы применить методы теории графов. Благодаря наглядности, графы проясняют алгоритмы решения задач и находят применение в разнообразных практических вопросах.
Целью моего проекта является показать, как составляются матрицы инцидентности и смежности графов, и вычисляется лапласиан. Объяснить, как их складывать и умножать. Найти практическое применение графам и матрицам.
Задачи:
1. Научиться расписывать матрицы для графов
2. Освоить действия над матрицами
3. Разобрать и показать на конкретных примерах получение лапласиана графа
4. Рассмотреть различные применения
В ходе работы я буду использовать учебные пособия Л.Н.Домнина, Белоусова И. В и Селезневой С.Н.
1. Типология графовых структур
[1](Неориентированным) графом G называется пара (V, E), где V — непустое конечное множество вершин; E — конечное множество ребер, причем каждому ребру e ∈ E сопоставлена неупорядоченная пара вершин, т.е. e = (v,w), где v,w ∈ V. Обозначения:
V(G) — множество вершин графа G,
E(G) — множество ребер графа G.
Типы графов:
- ориентированный граф:
рёбра которого имеют направление. Направленные рёбра также именуются ?дугами.
- неориентированные графы:
ни одному ребру которого не присвоено направление.
- смешанные графы:
рёбра могут быть ориентированными, а некоторые?— неориентированными.
2. Матрицы ориентированных графов
Во время действия алгоритма часто требуется модифицировать граф. [2] Матрицей A размера m×n называется прямоугольная таблица чисел, функций или алгебраических выражений, содержащая m строк и n столбцов. Числа m и n определяют размер матрицы. Числа, функции или алгебраические выражения, образующие матрицу, называются матричными элементами. Будем обозначать их строчными буквами с двумя индексами. Первый индекс i=1,2,. . . ,m указывает номер строки, а второй индекс j=1,2,…,n — номер столбца, в которых располагается соответствующий элемент. Представление графа с помощью матриц предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.
[3]Матрица смежности. Определим матрицу смежности как симметричную квадратную матрицу А=[ai,j] порядка n, в которой элемент ai,j равен 1, если в графе есть ребро {vi , vj }, т. е. vi и vj смежны, и 0, если такого ребра нет.
Матрица инцидентности. Определим матрицу инцидентности графа как прямоугольную матрицу B=[bi,j] размера n×m, в которой элемент bi,j равен 1, если вершина vi инцидентна ребру ej , и 0 в противном случае.
Диагональная матрица. Последовательность a11, a22, . . . , ann диагональных матричных элементов образует главную диагональ квадратной матрицы, идущую из ее левого верхнего угла в правый нижний угол.
Транспонированная матрица. Переход от матрицы A к матрице AT , в которой строки и столбцы поменялись местами с сохранением порядка.
3. Действия над матрицами
Сложение матриц. Суммой A + B двух матриц A = (ai,j) и B = (bi,j) одинакового размера m × n называется матрица C = (ci,j), элементы которой
ci,j = ai,j + bi,j для всех i=1,2,. . . ,m и j=1,2,. . . ,n.
Умножение матриц. Умножение матрицы A на матрицу B определено, лишь когда число столбцов первой матрицы в произведении равно числу строк второй. Тогда произведением матриц A m×k B k×n называется матрица C m×n , каждый элемент которой ci,j равен сумме попарных произведений элементов i–й строки матрицы A на соответствующие элементы j–го столбца матрицы B:
Создание матриц
I – матрица инцидентности
Ao – матрица смежности
IT – транспонированная матрица инцидентности
AoT – транспонированная матрица смежности
Ao + AoT = А
D – диагональная матрица
I × IT = L
A + D = L
1 Первый граф
I
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
|
V1 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
V2 |
1 |
1 |
0 |
0 |
0 |
-1 |
0 |
V3 |
0 |
-1 |
1 |
0 |
0 |
0 |
0 |
V4 |
0 |
0 |
-1 |
1 |
0 |
0 |
-1 |
V5 |
0 |
0 |
0 |
-1 |
-1 |
1 |
0 |
V6 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
IT
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
|
A1 |
-1 |
1 |
0 |
0 |
0 |
0 |
A2 |
0 |
1 |
-1 |
0 |
0 |
0 |
A3 |
0 |
0 |
1 |
-1 |
0 |
0 |
A4 |
0 |
0 |
0 |
1 |
-1 |
0 |
A5 |
1 |
0 |
0 |
0 |
-1 |
0 |
A6 A7 |
0 0 |
-1 0 |
0 0 |
0 1 |
-1 0 |
0 1 |
Ao
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
|
V1 |
0 |
0 |
0 |
0 |
1 |
0 |
V2 |
1 |
0 |
1 |
0 |
0 |
0 |
V3 |
0 |
0 |
0 |
1 |
0 |
0 |
V4 |
0 |
0 |
0 |
0 |
1 |
0 |
V5 |
0 |
1 |
0 |
0 |
0 |
0 |
V6 |
0 |
0 |
0 |
1 |
0 |
0 |
AoT
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
|
V1 |
0 |
1 |
0 |
0 |
0 |
0 |
V2 |
1 |
0 |
0 |
0 |
1 |
0 |
V3 |
0 |
1 |
0 |
0 |
0 |
0 |
V4 |
0 |
0 |
1 |
0 |
0 |
1 |
V5 |
1 |
0 |
0 |
1 |
0 |
0 |
V6 |
0 |
0 |
0 |
0 |
0 |
0 |
A
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
|
V1 |
0 |
1 |
0 |
0 |
1 |
0 |
V2 |
1 |
0 |
1 |
0 |
1 |
0 |
V3 |
0 |
1 |
0 |
1 |
0 |
0 |
V4 |
0 |
0 |
1 |
0 |
1 |
1 |
V5 |
1 |
1 |
0 |
1 |
0 |
0 |
V6 |
0 |
0 |
0 |
1 |
0 |
0 |
D
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
|
V1 |
2 |
0 |
0 |
0 |
0 |
0 |
V2 |
0 |
3 |
0 |
0 |
0 |
0 |
V3 |
0 |
0 |
2 |
0 |
0 |
0 |
V4 |
0 |
0 |
0 |
3 |
0 |
0 |
V5 |
0 |
0 |
0 |
0 |
3 |
0 |
V6 |
0 |
0 |
0 |
0 |
0 |
1 |
I × IT = L
2 |
-1 |
0 |
0 |
-1 |
0 |
-1 |
3 |
-1 |
0 |
-1 |
0 |
0 |
-1 |
2 |
-1 |
0 |
0 |
0 |
0 |
-1 |
3 |
-1 |
-1 |
1 |
1 |
0 |
-1 |
3 |
0 |
0 |
0 |
0 |
-1 |
0 |
-1 |
D + A = L
2 |
-1 |
0 |
0 |
-1 |
0 |
-1 |
3 |
-1 |
0 |
-1 |
0 |
0 |
-1 |
2 |
-1 |
0 |
0 |
0 |
0 |
-1 |
3 |
-1 |
-1 |
1 |
1 |
0 |
-1 |
3 |
0 |
0 |
0 |
0 |
-1 |
0 |
-1 |
2. Второй граф
I
A1 |
A2 |
A3 |
A4 |
A5 |
|
V1 |
1 |
-1 |
0 |
0 |
0 |
V2 |
-1 |
0 |
0 |
-1 |
-1 |
V3 |
0 |
1 |
-1 |
0 |
0 |
V4 |
0 |
0 |
0 |
0 |
1 |
V5 |
0 |
0 |
1 |
1 |
0 |
IT
v1 |
v2 |
v3 |
v4 |
v5 |
|
A1 |
1 |
-1 |
0 |
0 |
0 |
A2 |
-1 |
0 |
1 |
0 |
0 |
A3 |
0 |
0 |
-1 |
0 |
1 |
A4 |
0 |
-1 |
0 |
0 |
1 |
A5 |
0 |
-1 |
0 |
1 |
0 |
Ao
v1 |
v2 |
v3 |
v4 |
v5 |
|
V1 |
0 |
1 |
0 |
0 |
0 |
V2 |
0 |
0 |
0 |
0 |
0 |
V3 |
1 |
0 |
0 |
0 |
0 |
V4 |
0 |
1 |
0 |
0 |
0 |
V5 |
0 |
1 |
1 |
0 |
0 |
AoT
v1 |
v2 |
v3 |
v4 |
v5 |
|
V1 |
0 |
0 |
1 |
0 |
0 |
V2 |
1 |
0 |
0 |
1 |
1 |
V3 |
0 |
0 |
0 |
0 |
1 |
V4 |
0 |
0 |
0 |
0 |
0 |
V5 |
0 |
0 |
0 |
0 |
0 |
A
v1 |
v2 |
v3 |
v4 |
v5 |
|
V1 |
0 |
1 |
1 |
0 |
0 |
V2 |
1 |
0 |
0 |
1 |
1 |
V3 |
1 |
0 |
0 |
0 |
1 |
V4 |
0 |
1 |
0 |
0 |
0 |
V5 |
0 |
1 |
1 |
0 |
0 |
D
A1 |
A2 |
A3 |
A4 |
A5 |
|
V1 |
2 |
0 |
0 |
0 |
0 |
V2 |
0 |
3 |
0 |
0 |
0 |
V3 |
0 |
0 |
2 |
0 |
0 |
V4 |
0 |
0 |
0 |
1 |
0 |
V5 |
0 |
0 |
0 |
0 |
2 |
I × IT = L
2 |
-1 |
-1 |
0 |
0 |
-1 |
3 |
0 |
-1 |
-1 |
-1 |
0 |
2 |
0 |
-1 |
0 |
-1 |
0 |
1 |
0 |
0 |
-1 |
-1 |
0 |
2 |
D + A = L
2 |
-1 |
-1 |
0 |
0 |
-1 |
3 |
0 |
-1 |
-1 |
-1 |
0 |
2 |
0 |
-1 |
0 |
-1 |
0 |
1 |
0 |
0 |
-1 |
-1 |
0 |
2 |
Преимущества матричного подхода
• Возможность оптимизации вычислений и распределенного хранения данных;
• строгая алгебраическая формализация;
• применимость средств линейной алгебры и основанных
на ней методов прикладной математики;
• вариативность представления в зависимости от условий задачи.
Практическое применение графов
[4]Теория графов находит применение в различных областях современной математики и ее многочисленных приложений, в особенности это относится к экономике, например, когда надо выбрать наилучшие варианты развозки товаров по магазинам, строительных материалов. При составлении больших проектов, содержащих различные виды работ, часто возникает ситуация, когда ту или иную работу можно начать лишь по окончании других. Так, при строительстве дома нельзя приступить к отделочным работам, пока не возведены стены, и нельзя возводить стены до укладки фундамента. Последовательность работ изображается в виде сетевых графиков. Они применяются при планировании деятельности предприятия.
Например, зная дату начала строительства и время, необходимое для выполнения каждой работы, можно выяснить, к какому сроку следует подвезти материалы или пригласить бригады специалистов: плотников, маляров, электриков и т. д.
Сетевые графики используют не только строители, но и конструкторы машин с большим количеством узлов и деталей, диспетчеры железных дорог и многие другие специалисты
Заключение
Я показала, как составляются матрицы инцидентности и смежности для ориентированных графов, как их складывать и умножать, вычислять лапласиан. Также я подробно разобрала два графа. Нашла практическое применение графам и матрицам.
Библиографическая ссылка
Давыдова Д.С. МАТРИЦЫ ГРАФОВ // Старт в науке. – 2020. – № 4. ;URL: https://science-start.ru/ru/article/view?id=1940 (дата обращения: 05.10.2024).