Сочетания без повторений.

Сочетания без повторений.

Сочетаниями именуют композиции, составленные из n разных частей по k (k =< n) частей, которые отличаются хотя бы одним элементом. Сочетания обозначаются: Cnk C - 1-ая буковка французского слова combinasion - сочетание.

Составим из n частей различные сочетания по k частей в каждом. Их будет Cnk . Снутри каждого сочетания, состоящего из k частей Сочетания без повторений., образуем различные композиции, учитывающие порядок следования в их частей. Таких композиций будет Pk, т.к. мы в нашем сочетании образовываем перестановки. Всего разных композиций из n частей по k в каждой, отличающихся друг от друга или составом (элементами), или порядком их следования, будет Cnk • Pk . Но такие композиции именуются Сочетания без повторений. размещениями. Таким макаром, Ank = Cnk • Pk, тогда:

.

Задачка: в шахматном турнире участвует 7 человек; сколько партий будет сыграно, если меж хоть какими 2-мя участниками должна быть сыграна партия?

Решение: имеем сочетания без повторений из 7 частей по 2; их число: .

Сочетания с повторениями.

Если в сочетаниях некие элементы (либо все) возможно окажутся схожими Сочетания без повторений., то такие сочетания именуются сочетаниями с повторениями. Их число определяется по формуле: .

Задачка: сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?

Решение: имеем сочетания с повторениями из 4 по 7 по, их число: .

3.Графы

3.1.Главные понятия

3.1.1.История теории графов

3.1.2.Определения

3.1.3.Смежности и инцидентность

3.1.4.Изоморфизм графов

3.2.Представление графов в ЭВМ

3.2.1.Требования к представлению графов

3.2.2.Матрица смежности

3.2.3.Матрица Сочетания без повторений. инциденций

3.3.Геометрическая реализация графов

3.4.Маршруты, цепи, циклы

3.4.1.Определения

3.4.2.Эйлеровы графы

3.4.3.Гамильтоновы графы

3.5.Заключение


Графы

Посреди дисциплин и способов дискретной арифметики теория графов и в особенности методы на графах находят более обширное примене­ние в программировании. Дело в том, что тео­рия графов предоставляет очень удачный язык для описания программных (ну и многих других) моделей.

Этот тезис можно Сочетания без повторений. объяснить последующей аналогией. Понятие дела также можно вполне выразить через понятие огромного количества. Но независящее определение понятия дела удобнее - введение особых определений и обозначений упрощает изложение теории и делает ее более понятной.

То же относится и к теории графов. Стройная система особых определений и обозначений тео­рии графов позволяют Сочетания без повторений. просто и доступно обрисовывать сложные и тонкие вещи.

В особенности принципиально наличие приятной графической интерпретации понятия графа. Само заглавие «граф» предполагает наличие графической ин­терпретации. Рисунки позволяют сходу «усмотреть» сущность дела на интуитивном уровне, дополняя и украшая мучительные оптимальные текстовые доказатель­ства и сложные формулы.

2.1.Главные понятия

История теории графов

Теория графов Сочетания без повторений. неоднократно переоткрывалась различными создателями при решении разных прикладных задач.

1. Задачка о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и возвратиться в начальную точку (рис. 3.1). Эта задачка была решена Эйлером в 1736 году.

Рис. 3.1. Иллюстрация к задачке о Кенигсбергских мостах

2. Задачка о 3-х Сочетания без повторений. домах и 3-х колодцах. Имеется три дома и три колодца. Про­вести от каждого дома к каждому колодцу тропинку так, чтоб тропинки не пересекались (рис. 3.2). Эта задачка была решена Куратовским в 1930 году.

Рис. 3.2. Иллюстрация к задачке о 3-х домах и 3-х колодцах

Предметом первых задач теории графов были разные конфигурации Сочетания без повторений., состоящие из точек и соединяющих их линий. При всем этом несущественно: являются ли эти полосы прямыми либо кривыми, длинноватыми либо маленькими, тонкими либо толстыми; принципиально только то, какие точки они соединяют. Т.о. граф – это абстрактное математическое понятие.

Определения

Графом G(V,E) именуется совокупа 2-ух множеств - непустого огромного количества V (огромного Сочетания без повторений. количества вершин) и огромного количества Е неупорядоченных пар разных элемен­тов огромного количества V (Е - огромное количество ребер).

G(V,E): , E VxV.

Число вершин графа G обозначим р, а число ребер – q.

р(G) = |V| q(G) = |E|.

Нередко рассматриваются последующие схожие графам объекты.

1. Если элементами огромного количества Сочетания без повторений. Е являются упорядоченные пары, то граф назы­вается нацеленным (либо орграфом). В данном случае элементы огромного количества V именуются узлами, а элементы огромного количества - дугами (G(V, )).

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

3. Если Е является не обилием, а набором, содержащим несколько одинако­вых частей, то эти элементы именуются кратными ребрами, а граф назы­вается мультиграфом.

Дальше выражение: граф G(V,E) значит неориентированный граф без петель и кратных ребер.

Обычно граф изображают диаграммой: верхушки - точками (либо кружками), ребра - линиями.

Примеры.

1. . .


Т.о. это Сочетания без повторений. неориентированный граф с петлей и кратными ребрами.

Рис. 3.3. Неориентированный граф с петлей и кратными ребрами.

2. . .

Т.о. это направленный граф с петлей и кратными ребрами.


Рис. 3.4. Направленный граф с петлей и кратными ребрами.


3. . , т.о.

Рис. 3.5. Неориентированный граф с петлей.


sochineniya-na-svobodnuyu-temu-chelovek-i-priroda-po-tvorchestvu-v-astafeva-i-v-rasputina-sochinenie.html
sochineniya-na-svobodnuyu-temu-chestno-hochetsya-prozhit-7-sochinenie.html
sochineniya-na-svobodnuyu-temu-chto-znachit-bit-sovremennim-sochinenie.html