38. «Треугольник Паскаля»
Биномиальные коэффициенты можно подучить с помощью треугольника Паскаля (пользуясь операцией сложения).
В верхней строке пишутся две единицы. Все следующие строки начинаются и оканчиваются единицей. Промежуточные числа получаются сложением соседних чисел вышестоящей строки.
Практическая значимость треугольника Паскаля заключается в том, что с его помощью можно восстановить по памяти не только известные формулы, но и формулы куба суммы (разности) , четвертой степени и выше.
Пример: (a + b)6=a6+6a5b + 15a4b2+20a3b3 + 15a2b4+6ab5+b6.
3 9. Ориентированные графы. Динамика графа. Матрицы смежности, инциденций и достижимости.
Ориентированный граф - это граф, на ребрах которого обозначены разрешенные направления движения, проще говоря, расставлены стрелочки. - входящая степень вершины - это число входящих в нее ребер; - исходящая (или выходящая) степень вершины - это число выходящих из нее ребер; - путь из вершины A в вершину B - это последовательность ребер и промежуточных вершин, по которым можно дойти из A в B; длина пути определяется, как обычно (число ребер); простой путь - как обычно, путь, в котором вершины (и тем более, ребра) не повторяются; - ориентированный цикл - это замкнутый простой путь в ориентированном графе; - сильно связный ориентированный граф - это ориентированный граф, где из любой вершины в любую есть путь (для каждой пары вершин A и B есть как путь из A в B, так и путь из B в A); - компонента сильной связности - это часть графа, которая сама по себе сильно связна, но ее нельзя расширить так, чтобы она осталась сильно связной; между разными компонентами сильной связности могут быть ребра, но все ребра между двумя разными компонентами направлены в одну и ту же сторону.
Динамика Графа.
Графы принято изображать в виде диаграмм, состоящих из точен или кружков и линий, соединяющих некоторые из этих точек ( кружков) При этом точки соответствуют вершинам графа, а соединяющие пары точек линии — ребрам
Матрица смежности
Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aijравно числу рёбер из i-й вершины графа в j-ю вершину.
Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".
40. Изоморфизм графов.
Два графа G и G, называются изоморфными если между множеством их вершин существует такое взаимно-однозначное соответствие, при котором в одном из графов ребрами соединены вершины в том и только в том случае, если в другом графе ребрами соединены те же вершины Для орграфов дуг также должна быть одинаковой.