Матрица инциденций вершин и ребер

Представление графа с помощью матрицы, отражающей инцидентность вершин и ребер называется матрицей инциденций.

Для неографа:

М =

Для ориентированного графа:

H =

Пример 1. (Неограф)

v1 L1 v2

G: L4 L5 L2

v4 L3 v3

G: - матрица инциденций вершин и ребер для графа G

Пример 2.(Орграф)

V1 L1 V2

D: L4 L5 L2

V4 L3 V3

D: - матрица смежности вершин и ребер в орграфе

Матрица смежности вершин

Матрица инциденций вершин отражает смежность вершин.

Пример 1.

а1 а2

G: а5

а3 а4

A_G=(A_{i, j}) = ; A_G=

Для мультиграфа G матрица инцидентности дуг и вершин

B_G=(B_{i, j}) =

Это – матрица размера m×n, I = 1,2…,m

J = 1,2,…,n

Пример 2.

a2 4 a3

3

1 2

a1

B_G=

m×n_3×6

Тема: Комбинаторика

1. Размещения из n элементов по m это - упорядоченные подмножества из n элементов по m.

Число размещений

(n-факториал)

2. Перестановки - размещение и n элементов по n т.е. частный случай размещений число перестановок P_n=n!

3. Сочетания – подмножество из п элементов по m, отличающихся друг от друга хотя бы одним элементом называются сочетаниями. Число сочетаний

Пример:

1. Сколькими способами можно расположить 5 различных книг на полке? Р₅=1*2*3*4*5=120 способов.

2. Сколько способов распределить 3 различных путевки среди 8 человек бригады?

3. Сколько способов распределить 3 одинаковых обязанностей в группе из 25 человек?

способов т.к. обязанности одинаковы – это сочетания

Применение формул Крамера к решению систем линейных уравнений.

Рассмотрим применение формул Крамера к решению систем двух линейных уравнений с двумя неизвестными.

Решение. Вычислим определитель системы и определители _х и _у:

Найдем значение х и у по формуле Крамера:

Итак, решение системы есть (3:-1).

72. Решите систему уравнений

Решение. Вычислим определитель системы и определители _х и _у:

Так как =0, а _х≠0, _у≠0, то система не имеет решений (уравнения противоречивы).

73. решить систему уравнений

Решение. Находим

Данная система имеет бесчисленное множество решений (коэффициенты при неизвестных пропорциональны).

74. Решить систему уравнений

Решение. Вычислим определить системы и определители при неизвестных:

Найдем значения x, y, z по формулам Крамера.

Итак, получаем ответ: (1;-1;2).

Тема 3. Решение систем линейных уравнений методом Гаусса.

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

При выполнении прямого хода используют следующие преобразования:

1. Умножение или деление коэффициентов свободных членов на одно и то же число;

2. Сложение и вычисление уравнений;

3. Перестановку уравнений системы;

4. Исключение из системы уравнений, в которых все коэффициенты при неизвестных и свободных членов равны нулю.

Используя метод Гаусса, решить систему уравнений.

Решение. Переставим третье уравнение на место первого:

Запишем расширенную матрицу:

Что бы в 1-м столбце получить а21=а31=0, умножим 1-ю строку на 3, а затем на 2 вычтем результаты из 2-й и 3-й строк:

Разделим 20-ю строку на 8, полученные результаты умножим на 3 и вычтем из 3-й строки:

Запишем новую эквивалентную систему, которой соответствует расширенная матрица:

Выполняя обратный ход, с помощью последовательных подставок находим неизвестные:

Итак, получаем ответ: (1; 2: 3).