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

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

Пример 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 человек?

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