27) Элементы комбинаторики: перестановки, размещения, сочетания.

В разделе комбинаторики решаются задачи связанные с разложением множеств и состава различных комбинаций этих элементов.

Если взять 10 различных цифр и составить из них комбинацию, то получим различные числа: 345,1036,51. Некоторые из этих комбинаций отличаются только порядком цифр другие входящие в них цифр 3 количиства, следовательно, получаем комбинацию, удовлетворяющую различные условия.

В зависимости от правил соотношения можно выделить 3 типа комбинаций: перестановки, размещение, сочетание.

ПРЕРЕСТАНОВКА

Пусти даны 3 буквы ABC составим всевозможные комбинации: ABC, ACB, BCA, CAB, BAC. Все эти комбинации отличаются друг от друга только порядком расположения букв.

Комбинации из n-элементов которые отличаются друг от друга только порядком называется перестановкой. P_n=n!

РАЗМЕЩЕНИЕ

Пусть даны 4 буквы ABCD составим все комбинации только из 2 букв: AB, AC, AD,BA,BC,BD,CA,CB,CD,DA,DC,DB.

Комбинации из m элементов по n которые отличаются друг от друга самими элементами или порядком элементов называется размещением. A^m_n = m!__

(m-n)!

СОЧЕТАНИЕ

Сочетанием называется все возможные комбинации из m по n которые отличаются друг от друга хоть одним элементом: AB,BA,AC,AD,BC,BD,CD. C_mⁿ=m!___

(m-n)!n!

28) Понятие графа, простейшее свойство. Способы задания графов. Маршрутов графах. Связность. Ориентированные графы. Обходы в графах.

Первое упоминание Леонардом Эйлером (1736 году).

Граф это схема составленная из точек и соединений этих точек отрезков или кривых.

Простым графом называется конечное множество элементов вершинами (узлами, точками и конечно множеством непорядочных пар различных элементов называется рёбрами.

Рассмотрим граф:

T,P,Q,S,R- вершины, а линии соединяющие ребра.

Степенью вершины называется число рёбер концом которого является эта вершина. Данный граф аналогичен.

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

Графы изоморфны (одинаковы) если существует взаимно однозначное соответствие между их вершинами обладает тем свойством, что 2 вершины соединенные ребром в одном графе тогда и только тогда когда соответственные им вершины соединены ребром в другом графе.

Ребра соединяющие вершины T и S, Q и S называются кратными. Рёбра идущие из P в Q называются чётной. Графы не содержащие кратных рёбер и называются простыми 3.

Графы на которых указано стрелками на рёбрами называется ориентированными .

Свойства.

Если полный граф имеет n вершин то количество вершин будет равно: n(n-1)

2

Степень вершины:

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

Вершина называется нечётной если степень этой вершины нечётная, и чётной если степень чётная.

Некоторые закономерности присущие графам

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

2. Сумма степенной вершины графа число чётное ровно удвоенное числу графов.

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

Путь в графе. Цикл.

Много внимания в теории уделяется при изучении теории графа различных рода целей.

Под целью понимается последние идущие друг за другом рёбер.

Путём в графе от одной вершины к другой называется такая последовательность рёбер по которой можно проложить маршрут между этими вершинами(ни какое ребро не должно встретится более 1 раза.

1. ADGH

2. AEH

3. AEFCEH

4. ABCEH

маршруты CFEC, ADGHECBA циклы. CFEC- элементарный цикл.

Циклом называется путь в котором совпадает начало с концом .

Если все вершины цикла разные то такой цикл называется простым.

Если же цикл включает в себя все рёбра графа по одному разу называется Эйлеровой линией.

Две вершины графа называется связанными, если в графе существует путь с концами в этих вершинах.

Граф называется связь, если любая пара вершин связана.