If dop[y] then

begin x[k]:=y;

dop[y]:=False;

Lex(k+1);

dop[y]:=True;

end;

end;

begin for i:=1 to n do dop[i]:=True;

Lex(1);

end.

Задачи

26. На диске секретного замка 12 букв. Замок открывается после набора пароля из 5 букв. В пароле буквы могут повторяться. Сколько существует различных паролей?

27. В группе из 25 человек надо выбрать первую «десятку» для сдачи экзамена. Сколько существует различных вариантов выбора?

28. Вручную сгенерировать согласно алгоритмам

а) 2-размещения с повторениями из 3-элементов

б) 3-перестановки.

Отношения

Def. Пусть А₁, А₂, . . . , А_n – некоторые множества. Их прямым или декартовым произведением называется множество упорядоченных наборов из n элементов, т.е.

А₁А₂ . . . А_n = {(а₁, а₂, . . . , а_n) | a_iA_i }.

Если все множества A_i совпадают A = А₁ = А₂ = . . . = А_n, то прямое произведение А₁А₂ . . . А_n = Aⁿ называют прямой n-ой степенью множества А.

Отношением (n-арным отношением) между элементами множеств А₁, А₂, . . . , А_n называется любое подмножество R  А₁А₂ . . . А_n.

Бинарным отношением между элементами множеств А и В называется любое подмножество R  AB. Если множества A и B совпадают А = В, то R называют бинарным отношением на множестве А.

Если (x, y)R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R.

Примеры бинарных отношений

Пусть A = B = R – множество вещественных чисел. Пара (x, y) является точкой вещественной плоскости, т.е. АА – вещественная плоскость. Тогда бинарное отношение

R_А = { (x, y) | x² + y²  1 }

определяет замкнутый круг единичного радиуса с центром в точке (0, 0) на плоскости,

График бинарного отношения R_А

отношение R_Б = { (x, y) | x  y } – полуплоскость,

График бинарного отношения R_Б

а отношение R_В= { (x, y) |  |x – y|  1 } – полосу.

График бинарного отношения R_В

Бинарные отношения можно задавать, как было сказано, для множеств любой природы. Например, А = В – какое-то множество людей, например, в данном посёлке, а отношения R1 и R2 определяют различные степени родства между двумя людьми из его населения. Например, R1 = “быть мужем и женой”, R2 = “быть братом и сестрой”.

Основные понятия теории графов

Формально граф определяется так: граф – это пара объектов G = (V, E), где V – некоторое конечное множество, Е – бинарное отношение на V: E VV. V – множество вершин, E – множество ребер.

Ребро принято обозначать либо как элемент Е: e₁, …, e_m, e_j E, либо указанием его начальной и конечной вершины (v_i, v_j). Второе обозначение не всегда однозначно, например, в задаче о мостах обозначению (v₁, v₃) соответствуют два различных ребра.

Def. Графом без кратных ребер называется граф, в котором для любых i, j существует единственное ребро e_k = (v_i, v_j). Граф с кратными ребрами называется еще мультиграфом.

Def. Пусть u, v – вершины, е = (u, v) – соединяющее их ребро. Тогда вершина u и ребро e инцидентны друг другу (также как и v и е). Два ребра, инцидентные одной вершине называются смежными. Две вершины, инцидентные одному ребру также называются смежными.

Вершины, инцидентные одному ребру, могут быть равноправными, т.е. записи (u, v) и (v, u) эквивалентны, а могут быть неравноправными, т.е. важен порядок записи. Направленные ребра называются дугами, а содержащий их граф – ориентированным (орграфом). Направленные ребра на рисунке снабжаются стрелками – от начала к концу.

Пусть дан ориентированный граф и s – вершина графа. Обозначим Г ⁺ (s) и Г ^– (s) – множества вершин, смежных с s и таких, что

Иными словами, Г ⁺ (s) – это множество начальных вершин дуг, входящих в s, а Г ^– (s) – множество конечных вершин дуг, выходящих из s.

Граф, в котором все ребра не направлены, называется неориентированным. Ребро вида (v, v) называется петлей.

Def. Граф называется полным, если любые его две вершины смежны, E = V V. 0-граф – граф без ребер. Изолированная вершина – не смежная ни с одной другой вершиной.

Def. Пусть G = (V, E) – неориентированный граф. Маршрутом называется такая последовательность его ребер e₁, … e_k, что каждые два соседних ребра e_j, e_j+1 имеют общую вершину.

Пусть e₁ = (v₀, v₁), e_k = (v_k–1, v_k). Тогда v₀ – начальная, v_k – конечная вершины маршрута. Если v₀ = v_k, то такой маршрут называется циклическим маршрутом.

Для орграфа существуют аналогичные понятия: неориентированный маршрут, неориентированный циклический маршрут и т.д., в которых при прохождении ребер их ориентация не принимается во внимание. Также существуют ориентированный маршрут и ориентированный циклический маршрут в которых ребра проходятся в направлении их ориентации (по стрелке).