Задача о числе упорядоченных разбиений множества. Задача о числе перестановок с повторениями
Задача о числе упорядоченных разбиений множества: Всего во множестве n-элементов, разбиение на два подмножества m1 и m2. R(m1,m2)= = Задача о числе перестановок с повторениями: Полиномиальная формула. Бином Ньютона. Полиномиальная формула: ( + +…+xk)n= Суммирование производится по всем целочисленным решением уравнения , – полиномиальный коэффициент, вычисляется по формуле Бином Ньютона: (x+y)n= Свойства сочетаний. 1. Симметрия 2. Свойство Паскаля 3. 4. Формула включений исключений. │ │=│ │+│ │+…+│ │-│ │-…-│ │-…-│ │+│ │+…+│ │- │ │ U\│ │=U-│ │-│ │-…-│ │+│ │+…+│ │+…+│ │-│ │-…-│ │+ │ │ Графы. Виды графов: орграфы, мультиграфы, псевдографы. Отношения смежности и инцидентности. Степени вершин в графе и орграфе. Графом G(V,X) называется упорядоченное множество двух множеств: V – множество вершин, Х – множество ребер, при этом элементы множества Х являются неупорядоченные пары, состоящие из элементов множества V, предполагается, что V – не пустое множество. Положим, что │V│=n,│X│=m, т.е. граф G содержит m-вершин и n-ребер. Ребро х={Vi;Vj}, Vi,Vj – концы ребра; х – инцидентно Vi,Vj. Vi,Vj – инциденты ребру х. Два ребра, имеющих одну и туже вершину называются смежными. Два конца одного и того же ребра называются смежными вершинами. Степенью вершины δ(V) называется число ребер, инцидентных этой вершине. Вершина V, для которой выполняется условие δ(V)=1 называется концевая. Вершина V, для которой выполняется условие δ(V)=0 называется изолированная. Если элементами множества Х являются упорядоченные пары, то граф называется ориентированным. Если элементами Х является пары с равными элементами, то граф называется графом с петлями или псевдографом. Если среди элементов множества Х есть одинаковые пары, то они называются кратными ребрами, сам граф – мультиграфом, а количество одинаковых ребер – кратностью. Переопределим понятие степень вершины для орграфа: Полустепенью исхода из вершины V называется число (V) равное количеству дуг, для которых V является началом. Полустепенью захода в вершину V называется число (V) равное количеству дуг, которые заходят в вершину V. Теорема Эйлера: сумма степеней (полустепеней) всех вершин графа (орграфа) равно удвоенному числу ребер (дуг). Операции над графами. 1. Одноместные (унарные): а) удаление ребра, при этом множество вершин сохраняется б) добавление ребра в) добавление вершины, которую можно связать с некоторыми ребрами г) удаление вершины совместно с инцидентными ей ребрами д) стягивание ребра – удаление пары смежных вершин и добавление новой вершины, смежной с теми вершинами, которые были смежны хотя бы с одной из удаленных вершин. е) дополнение графа – дополнением графа Г является граф Г ', который дополняет исходный граф до полного. 2. Бинарные а) объединением G1(V1,X1) и G2(V2,X2) является G1∪ G2(V1∪ V2; X1∪ X2) б) пересечение G1(V1,X1) и G2(V2,X2) является G1∩ G2(V1∩ V2; X1∩ X2)
Популярное: Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (817)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |