Материал: baldin_kv_red_matematika_dlia_gumanitariev
Эйлеровыцепи
Как уже упоминалось, с задачи о кенингсбергских мостах началась теория графов. На рис. 1. 6 показан план расположения семи мостов на реке Преголь в городе Кенингсберге (ныне Калининград). Задача состоит в том, чтобы пройти каждый мост по одному разу и вернуться в исходную точку [10, 21, 25].
|
C |
|
|
c |
|
d |
g |
Река Преголь |
A |
e |
D |
аb
f
B
Рис. 1.36
Так как существенны только переходы через мосты, план города можно свести к изображению графа, в котором ребра соответствуют мостам, а вершины — раз- С личным, разделенным мостами, участ-
gками города (рис. 1. 7).
c |
|
d |
|
|
Л. Эйлер обратился к общей зада- |
|
|
А |
|
|
e |
D |
че, касающейся теории графов: в каких |
|
|
|
|
случаях в конечном графе можно найти |
||
|
|
|
|
|
|
|
a |
|
b |
f |
|
такой цикл, в котором каждое ребро гра- |
|
|
|
|
|
|
фа участвовало бы один раз? |
|
|
B |
|
|
|
|
|
|
|
|
|
|
Если такой цикл (замкнутая цепь) |
|
|
|
|
|
|
|
|
|
|
Рис. 1.37 |
|
есть, он называется эйлеровым, а граф, |
||
|
|
|
содержащий его — эйлеровым графом. |
|||
|
|
|
|
|
|
Л. Эйлер сформулировал и доказал |
теорему: конечный граф G является Эйлеровым графом тогда и только тогда, когда: а) граф является связным; б) степени всех его вершин четные.
46
Из теоремы Л. Эйлера следует, что задача о кенингсбергских мостах не имеет решения (граф на рис.1. 7 не Эйлеров, так как степени всех его четырех вершин являются нечетными d(A) = 5; d(B) = ; d(C) = ; d(D) = ).
Если обобщить задачу Л. Эйлера, то надо искать наименьшее число не пересекающихся по ребрам цепей Ni, которые необходимы для того, чтобы покрыть конечный связный граф G, т. е. включающий все его ребра в цепи Ni. Решение этой задачи сводится к задаче Л. Эйлера.
Задачидлясамостоятельногорешения
1.Дано: Х = {-5, 17, 22, 4, 101}; Y = {-17, 0, 22, 4, 102, 505}.
Найти Х < Y, Х > Y, Х\Y, Y\Х, ХDY.
2.Дано: Х=(-`;5]; Y=[-7;607).
Найти Х < Y, Х > Y, Х/Y, Y/Х.
. Докажите, что отрезки [0,1] и [0,5] равномощны.
4.Дано: Х = {1, 2, }; Y = {7, 8} = {(1,7), (1,8), (2,8), ( ,7)}.
Построить матрицу и граф отношения .
5.Сколькими способами в отделе, состоящем из 100 человек можно выбрать начальника и его заместителей?
6.Есть шесть видов конвертов без марок. Сколькими способами можно выбрать конверт и марку для отправки письма?
7.Из двенадцати человек надо выбрать пять и разместить их на занумерованных стульях (по одному человеку на стул). Сколькими способами это можно сделать?
8.Сколькими способами можно посадить за стол четырех мужчин и четырех женщин так, чтобы женщины и мужчины не сидели рядом?
9.Сколько различных восьмизначных чисел можно составить, используя цифры ,4,5?
10.Найти матрицы инцидентности для 2 графов:
47
|
1 |
1 |
|
|
|
|
|
|
7 |
|
|
2 |
|
|
1 |
|
|||
|
4 |
2 |
8 |
|
2 |
8 |
|||
6 |
7 |
|
|
|
5 |
2 |
4 5 |
6 |
4 |
|
4 |
5 |
|
10 |
9 |
12 |
1 |
|
9 |
|
|
|
|
||||||
|
|
|
|
|
6 |
6 |
11 |
10 |
5 |
|
|
|
|
|
|
||||
11. Найти матрицы смежности для графов: |
|
||||||||
1 |
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
вопросыдлясамопроверки
1.Какие способы задания множеств вы знаете?
2.Какое множество называется универсальным?. Какое отношение называется бинарным?
4.Что называется числом сочетаний из n элементов по m?
5.Что называется числом размещений из n элементов по m?
6.Что называется перестановкой из n элементов?
7.Какие графы называются изоморфными?
8.Какие графы называются Эйлеровыми?
9.Что такое степень вершины графа?
10.Какие графы называют деревьями?
11.Что такое k-раскраски графа?
12.Какие графы называют планарными?
48
2.ЭлеМентылинейнОй
ивектОрнОйалгебры
Линейная алгебра — это часть математики, посвященная в основном теории матриц и связанной с нею теории линейных преобразований, векторных пространств. Она включает теорию форм, теорию инвариантов, тензорную алгебру.
В данном учебнике мы рассмотрим понятие матрицы, ее применение для решения систем линейных алгебраических уравнений (СЛАУ), а также определители, векторы, собственные числа и векторы матриц.
2.1.Матрицы,определителииихсвойства
Матрицей называется прямоугольная таблица размером m (число строк) на n (число столбцов), заполненная некоторыми математическими объектами [28]. Мы будем рассматривать матрицы, элементами которых являются действительные числа.
Как правило матрицы обозначают большими буквами (A, B,…), а их элементы маленькими буквами с двумя индексами, указывающими номер строки и номер столбца (aij, bij,…). Прямоугольную матрицу размера m n записывают следующим образом:
Если заменить строки матрицы ее столбцами (столбцы строками), то получим транспонированную матрицу, которую обозначают заглавной буквой с индексом T наверху:
49
Рассмотрим некоторые типы матриц [19, 29].
Если число строк матрицы равно числу ее столбцов, то мы имеем квадратную матрицу:
Элементы a11, a22, …, ann называются главной диагональю, а их сумма — это след матрицы.
Элементы a1n, a2(n-1), …, an1 составляют побочную диагональ. Если все элементы матрицы, кроме элементов, стоящих на главной диагонали, равны нулю, то мы имеем диагональную
матрицу:
Если все ненулевые элементы диагональной матрицы равны 1, то мы имеем единичную матрицу:
50