Практическое занятие №9 . Треугольник Паскаля. Бином Ньютона. Комбинаторные схемы.

 

Элементы теории

Составим таблицу значений сочетаний C_n^m    для n,m = 0,1,2,3,4,5,6,7.

 

n \ m 0 1 2 3 4 5 6 7 0 1 . . . . . . . 1 1 1 . . . . . . 2 1 2 1 . . . . . 3 1 3 3 1 . . . . 4 1 4 6 4 1 . . . 5 1 5 10 10 5 1 . . 6 1 6 15 20 15 6 1 . 7 1 7 21 35 35 21 7 1	Эту таблицу можно неограниченно продолжать вниз и вправо. Она называется треугольником Паскаля. Еще удобнее ее записывать в виде равнобедренного треугольника.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1	Треугольник Паскаля обладает свойством: каждое число равно сумме двух чисел, стоящих над ним, поэтому таблицу можно без труда продолжать вниз, не прибегая к вычислению числа сочетаний. Нам знакомы формулы:

(a + b)¹ = a + b;      (a + b)² = a² + 2ab + b²;     (a + b)³ = a³ + 3a²b + 3ab² + b³.

 

Коэффициенты в правых частях этих формул взяты из строк треугольника Паскаля соответственно с номерами 1,2,3. При любом натуральном n справедлива формула, называемая бином Ньютона:

 

 

Коэффициенты в правой части формулы называют разложением степени биномаберутся и з строки с номером n   треугольника Паскаля.

Если вычисляется (а - b)ⁿ = (a + (-b))ⁿ, то в правой части формулы знаки чередуются.

Задания для самостоятельного выполнения

 

 

1. Запишите разложение бинома:

0) (2x – y )^4;		1) (x  + 3y)^4;
2) (5x – y )^4;		3) (x  + 2y)^4;
4) (3x + y )^4;		5) (x – 2y)^4;
6) (2x – y )^4;		7) (x  + 4y)^4;
8) (4x – y )^4;		9) (x  + 3y)^4;
Задание 2. Записать все размещения из элементов множества А по два элемента с повторениями: 0) А = {2,7,9}; 1) A = { x, y, z}; 2) A = { a, b, c}; 3) A = { X, Y, Z}; 4) А = {+,-,×}; 5) А = {!,#,%}; 6) А = {α,β,λ} 7) А = {←,↑,→}; 8) А = {В, П, МР}; 9) A = {Q,W,E}.	Задание 3. Записать все размещения из элементов множества А по два элемента без повторений:   10) А = {2,7,9}; 11) A = { x, y, z}; 12) A = { a, b, c}; 13) A = { X, Y, Z}; 14) А = {+,-,×}; 15) А = {!,#,%}; 16) А = {α,β,λ} 17) А = {←,↑,→}; 18) А = {В, П, МР}; 0) A = {Q,W,E}.
Задани 5. Сколько трехзначных чисел, меньших заданного числа А, можно образовать, используя цифры 2,3,4,5,6,8,9 без повторений, если: 0) А=450;     1) А=350; 2) А=250;     3) А=420; 4) А=410;     5) А=380; 6) А=370;     7) А=430; 8) А=390;     9) А=460.	Задание 6. Сколькими способами N пар, пришедших в кино, могут занять места, если все пять пар сидят подряд и:   0) N=4; 1) N=5; 2) N=7;   3) N=6; 4 ) N=8; 5) N=9;   6) N=3; 7) N=10;   8) N=12; 9) N=11.

Практическое занятие №10. Графы.  Виды графов. Изоморфизм графов.

 

Элементы теории

Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом. Соединения между узлами (V) графа называются ребрами (E). Если узлы графа не нумерованы, то ребра являются неориентированными. У графа с нумерованными узлами ребра ориентированы и называются дугами
(рис. 2).

Пара вершин может быть соединена двумя или более ребрами (дугами), такие ребра (дуги) называются кратными. Вершины, соединенные ребром (дугой) называются смежными.       Если ребро начинается и заканчивается в одной и той же вершине, то называется петлей.

Рис. 2. Примеры А) неориентированного и Б) ориентированного графов.

   Число ребер, исходящих из вершины vi (петля учитывается дважды), называется валентностью (степенью вершины) и обозначается: d (v_i).

Если V и E конечные множества, то и граф им соответствующий называется конечным. Граф называется вырожденным, если он не имеет ребер.

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

       Графы отображаются на плоскости набором точек и соединяющих их линий или векторов.

Грани могут отображаться и кривыми линиями, а их длина не играет никакой роли.

Граф G называется планарным (плоским), если его можно отобразить в плоскости без пересечения его граней (рис. 5).

Граф называется связным, если для любых двух вершин существует последовательность ребер их соединяющая (рис. 3), т.е. граф не имеет изолированных фрагментов (вершин, ребер).

Граф называется полным, если любые две вершины соединены только одним ребром (рис.4). Если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.

 Специальными видами графов являются деревья (рис. 6), кольца и списки, что не входит в рассмотрение нашего курса.

Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом.

3 5 2 1 4 5   Рис. 3. Пример связного плоского графа	4 1 4 3 2 1 3 2   Рис. 4. Пример полного графа		Рис. 5. Пример непланарного графа
ГрафG = (V, E) называется деревом, если: 1.в нем есть одна вершина, в которую не входят ребра; она называется корнем дерева; 2.в каждую из остальных вершин входит ровно по одному ребру; 3.все вершины достижимы из корня.		1 2 3 5 4   Рис. 6. Пример дерева

Ребро (дуга) и любая из его вершин называются инцидентными. Принято говорить, что ребро (дуга)  (u, v) соединяет вершины u и v.

Если вершина не инцидентна ни одному ребру (дуге), то она называется изолированной (d(vi)=0), если принадлежит только одному ребру (дуге), то называется висячей (d(vi)=1).

Основные положения о вершинах графа:

1. В графе G сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат называют леммой о рукопожатиях: если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях).

2. Число нечетных вершин любого графа четно.

3. Во всяком графе с n вершинами, где n ³2, всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

4. Если в графе с вершинами n>2 две вершины имеют одинаковую степень, то в этом графе всегда найдется либо одна вершина степени 0, либо одна вершина степени n - 1.

Два графа G1=(V1,E1) и G2=(V2,E2) называются изоморфными, если между их вершинами существует взаимно однозначное соответствие.

Алгоритм распознавания изоморфизма двух графов G ₁ (X, E)и G ₂ (Y, E)

1. Если X ≠ Y, то графы не изоморфны.

2. Выписываем все элементы обоих графов, определяя пары (x_i,x_j) и (y_i, y_j) для каждого элемента, где x_i, y_i  - число исходов для каждой вершины обоих графов, а x_j, y_j – число заходов.

3. Для каждого элемента x графа G₁ ищем  такой элемент y графа G₂,  что выполняется условие: число исходов x совпадает с числом исходов y, и число заходов x совпадает с числом заходов y. Найденные элементы x и y соединяем дугой, т.е. строим граф соответствия. Если соответствия нет, то графы неизоморфны.

4. Выписываем подстановку, которая переводит граф G₁ в граф G₂.

 

Примеры выполнения заданий

1.

3

2

3

2

 Докажите, что валентности вершин графов А и Б совпадают.

6

5

4

1

6

5

4

1

                               А                                           Б

Решение: А) d(v₁)=2,d(v₂)=3,d(v₃)=3,d(v₄)=2,d(v₅)=3,d(v₆)=3.

Б) d(v₁)=2,d(v₂)=3,d(v₃)=3,d(v₄)=2,d(v₅)=3,d(v₆)=3.

2. Докажите, что графы G ₁ (X ₁, E ₁) и G ₂ (Y ₂, E ₂) изоморфны.

2 3 2 X2 X4 X5 X3 4 1 X1 5 4 3

Y4 Y3 Y5 Y1 Y2

Решение:  

 

X1(3, 3)	X2(4, 4)	X3(3, 3)	X4(2, 2)	X5(2, 2)
Y1(4, 4)	Y2(2, 2)	Y3(3, 3)	Y4(3, 3)	Y5(2,2)

В результате получим подстановку:

Следовательно, графы G1(X, E) и G2(Y, E) изоморфны.

 

3. Решите задачу по вычислению валентности вершин графа

Школьник сказал своему приятелю: - У нас в классе 35 человек. Каждый из них дружит ровно с 11 одноклассниками... - Не может этого быть, - сразу ответил приятель, победитель математической олимпиады. Почему он так решил?

Решение: представим себе, что между каждыми двумя друзьями протянута ниточка. Тогда каждый из 35 учеников будет держать в руке 11 концов ниточек, и значит, всего у протянутых ниточек будет 11 35 = 385 концов. Но общее число не может быть нечётным, так как у каждой ниточки 2 конца.

 

4. Решите задачу по выявлению связности компонент графа

В компании из 7 мальчиков каждый имеет среди остальных не менее трех братьев. Докажите, что все семеро — братья.

Решение: возьмём любых двух мальчиков из этой компании. Предположим, что они не братья. Тогда каждый из них имеет среди оставшихся по три брата. По принципу Дирихле[1], у них есть общий брат, а значит, они братья. Итак, любые два мальчика из этой компании - братья, что и требовалось доказать.

 

5. Докажите, что граф с n вершинами, степень каждой из которых не менее (n - 1)/2, - связен.

Решение: рассмотрим две произвольных вершины и предположим, что они не соединены путем, то есть такой последовательностью ребер, в которой начало очередного ребра, совпадает с концом предыдущего. Каждая из этих двух вершин по условию соединена не менее, чем с (n - 1)/2 другими; при этом все упомянутые вершины различны - ведь если какие-то две из них совпадают, то есть путь, соединяющий исходные вершины. Таким

образом, мы указали не менее  (n - 1)/2 + (n - 1)/2 + 2 = n + 1 вершин. Противоречие.

 

6.Определите, являются ли данные графы деревьями:

 

Ответ: да, все указанные графы являются деревьями согласно свойствам деревьев.

Задания для самостоятельного выполнения

 

 

1. Докажите, что валентности вершин графов А и Б совпадают.

 

А                           Б

2. Заданы два графа G₁(V₁, E₁) и G₂(V₂, E₂). Выясните, изоморфны ли графы?

2. Определите виды графов и подсчитайте валентность вершин:

 

0)                                       Решение:	1)                                          Решение:
2)                                       Решение:	3)                                          Решение:
4)                                       Решение: А                             С В	5)                                          Решение:  А                                                                          В   С                                Д

 

6)                                       Решение:	7)                                         Решение:  А                     В                                             С         Д
8)                                       Решение:	9)                                         Решение:  А                                В                                               С                                Д

4.Определите виды графов и подсчитайте валентность вершин:

 

 

0) 1                             Решение: 2 3 4 5 6	1) 1                      Решение: 2 3 4 5 6
2) 2 1                                Решение: 7 4 5 6 3   1	3) 6 2 7 4 3 5 1 2                        Решение:
4) 7                                Решение: 6 2 3 4 5	5) 6 5 3 4 1                         Решение:
6) 5                                Решение: 4 3 2 1 6	7)                              Решение: 2 3 4 1 6 5
8) 2 1                                Решение: 3   4 5 6	9) 1                        Решение: 6 2 5 4   3

 

Практическое занятие №11.  Способы задания графов

 

Элементы теории

Неориентированный граф G (V, E) – непустое конечное множество узлов (вершин) V и набор неупорядоченных пар вершин (ребер) E.

 

Способы задания графа:

 

1) аналитический (в виде алгебраической системы);

2) геометрический (в виде произвольного рисунка);

3) матричный (в виде матриц смежности и инцидентности).

Пусть v1, v2,... vn - вершины графа G (V, E), а e1, e2,... em - его ребра.

Матрицей смежности неориентированного графа G называется матрица A(G) = ||aij||, i=1,...,n;  j = 1,..., n, у которой элемент aij равен числу ребер, соединяющих вершины vi и vj (соответственно, идущих из вершины vi в вершину vj).

 

 

 

Свойства матрицы смежности:

1) симметричная относительно главной диагонали,

2) значениями являются натуральные числа и ноль,

3) количество петель записывается на главной диагонали,

4) сумма значений по строке или в столбце равна валентности вершины.

Матрицей инцидентности для неориентированного графа с n вершинами и m ребрами называется матрица В(G) = [bij], i=1, 2,..., n, j = 1,2,..., m, строки которой соответствуют вершинам, а столбцы - ребрам. Элемент bij=1, если вершина vi инцидентна ребру ej и bij=0, если вершина vi не инцидентна ребру ej.

 

Свойства матрицы инцидентности:

1) несимметричная,

2) значениями являются ноль и единица,

3) сумма значений по строке или в столбце равна 2, если нет петель.

 

 

Примеры выполнения заданий

1. Граф G (V, E): V ={ a, b, c, d },   E ={(a, b),(b, a),(b, c),(c, b),(a, c),(c, a),(c, d),(d, c)} задан как алгебраическая система. а) Выясните, является ли заданное отношение эквивалентным. б) Для приведенного отношения задайте граф геометрически.