Задание
Для игры, заданной деревом (рис. 1), определить, кто из игроков имеет выигрышную стратегию, и указать ее.
Рис. 1
Решение
| № п/п | Алгоритмы | Конкретное соответствие задания заданному алгоритму |
| Определить длину игры | Из рис. 1 видно, что максимальная длина цепи, идущей из корня в концевую вершину, равна 4; поэтому все вершины 4-го яруса – концевые, соответствуют заключительным пози-циям игры и помечены одним из символов А или В, определяющим выигрыш определенного игрока | |
| Начиная с вершин нижнего яруса, помечать вершины предыдущего яруса символами А или В в зависимости от того, для какой из сторон подыгра, начинающаяся в этой вершине, является выигрышной. Попутно отмечать ребра, которые определят выбираемую стратегию | а) ребра, связывающие вершины 3-го и 4-го ярусов, изображают ходы игрока В (из нечетного яруса в четный). Каждую непомеченную вершину 3-го яруса a помечаем символом В, если среди подчиненных ей вершин 4-го яруса имеется хотя бы одна вершина с меткой В, отмечаем также ребро ( ); в противном случае (если все подчиненные вершины – с меткой А) помечаем вершину символом А и отмечаем любое ребро ( ). На рис. 1 ребра первого типа идут к вершинам 10 и 16, ребра второго типа – к вершинам 2 и 20;
б) ребра, связывающие вершины 2-го и 3-го ярусов, изображают ходы игрока А (из четного яруса в нечетный). Каждую непомеченную вершину 2-го яруса помечаем символом А, если среди подчиненных ей вершин 3-го яруса имеется вершина с меткой А; в противном случае (все подчиненные вершины – с меткой В) помечаем вершину символом В
в) вершины 1-го яруса и исходящие из них ребра помечаются так же, как описано в п. а; вершина (единственная) 0-го яру-са, т.е. корень дерева и исходящие из него ребра – как в п. б. На рис. 2 расставлены приписанные метки и выделены отмеченные ребра
Рис. 2
| |
| Определить выигрывающую сторону | Символ, приписанный в результате описанного процесса корню дерева, указывает, кто из игроков обладает выигрышной стратегией. Для данного примера выигрышная стратегия – у игрока В | |
| Указать выигрышную стратегию | Отмеченные ребра, исходящие из вершин, соответствующие ходам выигрывающей стороны, составляют выигрышную стратегию. На рис. 2 – это отмеченные ребра, идущие из вершин 1-го и 3-го ярусов |
Решите самостоятельно следующие задачи:
1. Определить, кто из игроков обладает выигрышной стратегией, и указать ее для игры, заданной деревом на рис. 1, если концевые вершины 1-21 помечены следующим образом:
| 1) | В | А | А | А | В | В | А | А | А | В | В | А | А | В | А | В | В | В | А | В | А |
| 2) | В | В | А | А | В | В | А | В | А | В | В | В | А | В | А | А | А | В | В | А | А |
| 3) | В | А | А | А | В | А | В | А | В | А | В | А | В | В | В | А | А | В | А | В | А |
2. То же задание для игры, заданной деревом на рис. 3 с концевыми вершинами 1-24.
| 4) | В | А | В | В | В | А | В | А | В | А | А | В | А | В | А | А | А | В | В | В | А | А | В | А |
| 5) | В | А | А | В | А | В | А | В | А | В | В | А | А | В | А | В | А | А | В | А | В | В | А | В |
Рис. 3
ПРИЛОЖЕНИЯ
Приложение 1
Примеры решения задач
Задача 1. Сколько 5-значных чисел, в десятичной записи которых участвуют цифры из множества {0, 1, 4, 6, 7}?
Решение. В записи числа первая цифра должна быть отличной от 0; остальные четыре цифры могут быть произвольными. По комбинаторному правилу произведения искомое число 5-значных чисел равно 4 • 5 • 5 • 5 • 5 = 2500.
Задача 2. Сколько 6-значных чисел, в десятичной записи которых участвуют цифры из множества {0, 1, 4, 6, 7} и таких, что четные цифры чередуются с нечетными?
Решение. Если в записи числа первая цифра четная, то она может быть равна 4 или 6, вторая, четвертая и шестая – 1 или 7, третья и пятая – 0, 4 или 6; таких чисел по правилу произведения:
2 • 2 • 3 • 2 • 3 • 2 = 144. Если же первая цифра нечетная, то она, а также третья и пятая могут быть равны 1 или 7, вторая, четвертая и шестая – 0, 4 или 6; таких чисел 2 • 3 • 2 • 3 • 2 • 3 = 216. Всего искомых чисел 144 + 216 = 360.
Задача 3. Сколько различных слов можно составить перестановками букв слова МАТЕМАТИКА?
Решение. Число перестановок из 10 букв равно 10!. Однако в слове МАТЕМАТИКА
есть одинаковые буквы: М – 2 раза, А – 3 раза, Т – 2 раза: перестановка одинаковых
букв не изменяет слова. Поэтому число различных 10-буквенных слов равно 
= 
=
= 1 • 2 • 3 • 5 • 7 • 8 • 9 • 10 = [в произведении отсутствуют множители 4 и 6] = 151200.
Задача 4. В формуле W = [(X A Y) B (Y C Z)] D (X E T) F (Z G T) каждый из символов A, B, C, D, E, F, G обозначает одну из арифметических операций: сложение, вычитание, умножение и деление. Сколько различных формул представляются таким образом?
Решение. Каждый из символов A, B, C, D, E, F, G может иметь 4 значения независимо от других. Тем самым, формула однозначно определяется (4, 7)-размещением с повторениями. Поэтому число различных формул равно 47 = 16384.
Задача 5. Сколько существует 7-значных десятичных чисел таких, что в их записи:
а) нет одинаковых цифр в соседних разрядах;
б) в любых трех последовательных разрядах все цифры различны?
Решение. а) Для первой цифры – 9 возможностей (любая цифра, кроме 0); для второй и последующих – любая цифра, кроме предыдущей, также 9 вариантов. Результат – по правилу произведения: 97.
б) Для первой и второй цифры – 9 возможностей, как в первом случае; для третьей и последующих – любая цифра, кроме двух предыдущих (они различны), т.е. 8 вариантов. По правилу произведения получаем: 92 • 85.
Задача 6. Каждое воскресенье каждый из четырех теннисистов команды А проводит с кем-либо из четырех теннисистов команды В по одной игре. Доказать, что в течение полугода найдутся два воскресенья с одним и тем же распределением противников по четырем парам.
Решение. Занумеруем игроков одной из команд. Распределение их противников есть перестановка из 4 элементов. Число n -перестановок P n равно n! Следовательно, составлять различные наборы из 4 пар можно не более, чем 4! = 1 • 2 • 3 • 4 = 24 способами. Полгода составляют 26 недель, поэтому повторение неизбежно.
Задача 7. Чтобы открыть входную дверь в пещеру, Али-Баба должен угадать шифр. Ему известно, что это некоторое число не длиннее 5 цифр, записываемое с использованием только цифр 2, 4, 8. Возможно не более одной попытки в день. Удастся ли Али-Бабе попасть в пещеру в течение года?
Решение. Указанные шифры – это слова в алфавите { 2, 4, 8 }. Число слов длины k в алфавите из трех букв равно 
= 3 k. Допустимые слова имеют длину от 1 до 5. Число всех таких слов равно сумме 3 + 9 + 27 + 81 + 243 = 363. Поэтому за год можно перебрать все возможные шифры. Не позже 363-го дня дверь откроется.
Задача 8. Книжный коллектор предлагает для комплектования библиотек книги
8 наименований по 1000 экземпляров каждая. Сколькими способами библиотека может составить заявку на 25 книг?
Решение. Заявка указывает, сколько требуется книг каждого наименования. Запасы коллектора позволяют библиотеке выбирать в пределах общего числа 25 книг любое количество книг каждого наименования Соответствующая комбинаторная конфигурация есть (8, 25) -сочетание с повторениями.
Число (n, k)-сочетаний с повторениями: 
= 
= 
. Для заданных параметров получаем: 
= 
= 
= (32 • 31 •... • 26) / (1 • 2 •...• 7) = 3365856.
Задача 9. Построить матрицу соседства вершин графа.
Решение. В графе 5 вершин, поэтому матрица соседства вершин – 5-го порядка. Элемент aij матрицы равен 1, если из вершины i идет дуга (ориентированное ребро) в вершину j. Неориентированным ребрам (1, 3) и (1, 5) соответствуют в матрице по две единицы: a 13 = a 31 = 1; a 15 = a 51 = 1. Петле соответствует диагональный элемент a 55.
Задача 10. По заданной матрице соседства вершин построить ориентированный граф. Выделить в этом графе какой-нибудь элементарный путь [1, 4] и какую-нибудь элементарную цепь [1, 4].
Решение. Порядок матрицы равен 4. Поэтому в графе 4 вершины. Каждая единица в матрице обозначает определенную дугу графа; число дуг равно 7. Обозначим их a, b, c, d, e, f, g.
Путь [1, 4] = [1, a, 3, f, 2, b, 4]. Поскольку в графе нет кратных дуг (e и f – кратные ребра, но имеют разные направления), можно опустить обозначения ребер: [1, 3, 2, 4]. В качестве цепи [1, 4] можно рассматривать тот же путь, а также цепи [1, d, 4], [1, a, 3, g, 4].
Задача 11. Найти число треугольников (полных трехвершинников) в полном графе K 8.
Треугольник полностью определяется выбором трех вершин из данных восьми. Число таких неупорядоченных троек равно числу (8, 3)-сочетаний без повторений
.
Задача 12. Сколько различных циклов длины 4 в полном двудольном графе K 5,8?
Решение. Множество вершин двудольного графа разбивается на две части А = { ai } и В = { bj }. Каждый цикл длины 4 в двудольном графе имеет вид а 1 b 1 a 2 b 2 a 1; в полном графе такой
цикл определяется выбором любых двух вершин а 1и a 2 из множества А и любых двух вершин
b 1, b 2 из множества В (см. чертеж). Неупорядоченную пару вершин { а 1, a 2} можно выбрать
С52 = (5 • 4) / (1 • 2) = 10 способами; неупорядоченную пару вершин { b 1, b 2} можно выбрать
С82 = (8 • 7) / (1 • 2) = 28 способами. По комбинаторному правилу произведения число рассматриваемых циклов равно С52 • С82 = 10 • 28 = 280.
Задача 13. Вершинами графа G являются все наборы длины 5 из нулей и единиц. Ребра связывают все пары вершин, различающихся ровно в 2 разрядах. Определить число ребер графа G и его цикломатическое число.
Решение. Число наборов длины k из нулей и единиц равно числу (2, k)-размещений с повторениями: 
= 2 k. Следовательно число вершин b графа G равно 32. Степень s каждой вершины равна числу наборов, разнящихся с данным в двух разрядах. Число пар таких разрядов равно числу (5, 2)-сочетаний без повторений: 
= 5 • 4 / 2 = 10. Для однородного графа степени s число ребер равно b · s / 2 = 32 • 5 = 160.
Цикломатическое число связного графа ν(G) = p - b + 1 = 160 – 32 + 1 = 145.
Задача 14. Построить остов графа
Решение. Выбираем произвольную вершину, например, а, включаем инцидентные ей ребра 1, 2, 3 и, следовательно, вершины b, e, i; далее соседние с ними вершины c, k, h, g и инцидентные им ребра 4, 5, 6, 7, и, наконец, вершины f, d и ребра 8, 9. Выбираемые ребра на каждом этапе подключают к уже построенному к этому моменту подграфу новую вершину, и поэтому циклов не возникает, а связность сохраняется. На чертеже выделенные ребра образуют остов графа. Схема показывает последовательность присоединения вершин в процессе построения остова.
Задача 15. Найти расстояние между вершинами А и В графа с заданными длинами ребер.
Решение. Длина цепи – сумма длин ее ребер. Расстояние между вершинами – длина кратчайшей цепи, связывающей эти вершины. Алгоритм нахождения искомого расстояния – на чертеже. Показана расстановка меток, выражающих длины цепей, связывающих данную вершину с входным полюсом А. По мере обнаружения более коротких цепей метки пересчитываются (уменьшаются); минимальные вычисленные значения определяют расстояние от А до данной вершины. Последняя метка выходного полюса В есть расстояние d (A, B). Для заданного графа d (A, B) = 17.
Приложение 2
Пример дерева игры
В п. 2.7 отмечалось, что в дереве игры «крестики-нолики» на доске 3´3 для 1-го хода начинающего игрока (назовем его +), если учитывать симметрию, число возможностей сводится до 3: «центр» - b2, «угол» - a1, «середина стороны» - b1. Для ответного хода игрока В (его естественно назвать 0) - выбор из 8 оставшихся полей, если учитывать симметрию, зависит от хода, выбранного начинающим и т.д.
На рис. фрагменты дерева игры: на первом ярусе 3 вершины: a 1, b 1, b 2;
продолжено изображение только ответов на ход b 2 (с учетом симметрии их 2): «угол» - a 1, «середина стороны» - b 1. На ход а 1 игрока 0 у игрока + есть 4 существенно различных ответа;
на ход с 1 – указана (не до конца) только форсированная ветвь, которая приводит к ничейному исходу. Если же на 2-м ярусе игроком 0 был выбранход b 1, у игрока + также есть 4 сущест-венно различных ответа: на рисунке указано только продолжение при выборе хода а 3: при всех ответах игрока 0 - форсированный выигрыш +.
ГЛОССАРИЙ
| № п/п | Новое понятие | Содержание |
| Выборка объема k из n элементов, или (n, k)-выборка | набор элементов (xi 1, xi 2,..., xik), составленный из элементов множества Х = { x 1, x 2,..., xn } | |
| (n, k)-размещение без повторений | упорядоченная (n, k)-выборка, в которой элементы не могут повторяться | |
| (n, k)-размещение с повторениями | упорядоченная (n, k)-выборка, в которой элементы могут повторяться; слово длины k в алфавите из n букв | |
| n -перестановка, или перестановка из n элементов | (n, n)-размещение без повторений | |
| (n, k)- сочетание без повторений | неупорядоченная (n, k)-выборка без повторений; k -элементное подмножество n -элементного множества | |
| (n, k)- сочетание с повторениями | неупорядоченная (n, k)-выборка с повторениями | |
Биномиальные коэффициенты 
| числа (n, k)-сочетаний без повторений, совпадающие с коэф-фициентами формулы бинома Ньютона для n -й степени двучлена (x + y): (x + y)n = 
| |
| Треугольник Паскаля | треугольная числовая таблица, n -я строка которой состоит из (n + 1) коэффициентов бинома (x + y)n:  , ,...,  . Каждое число строки, кроме крайних, равных единице, равно сумме двух ближайших чисел, находящихся над ним в предыдущем ряду
| |
| Полиномиальный коэффициент | коэффициент при произведении  •  •...•  в разложении полинома (x 1+ x 2+...+ xn) n по степеням переменных x 1, x 2,..., xn
| |
| Принцип Дирихле (принцип ящиков) | комбинаторное соотношение: если в m ящиках находятся (m+1) или больше камней, то хотя бы в одном из ящиков больше одного камня | |
| Граф | система G = (V, E), состоящая из множества элементов V = { v }, называемых вершинами графа и множества элементов E = { е }, называемых ребрами; каждому ребру е Î Е поставлена в соответствие упорядоченная или неупорядоченная пара элементов v 1, v 2Î V, называемых концами ребра е = (v 1, v 2) | |
| Инцидентность | отношение между вершиной v и ребром е графа, если вершина v является концом ребра е | |
| Соседние (смежные) вершины | две вершины, инцидентные одному и тому же ребру | |
| Смежные ребра | два ребра, инцидентные одной и той же вершине | |
| Матрица инциденций графа с b вершинами и p ребрами | прямоугольная матрица А = ║ aij ║ с b строками и p столбцами; строки соответствуют вершинам графа, столбцы – ребрам, причем для неориентированного графа элемент матрицы aij равен 1, если вершина vi и ребро ej инцидентны, и равен 0 в противном случае. Для ориентированного графа aij = -1, если vi является началом дуги ej; aij = +1, если vi - конец дуги ej; aij = 0, если вершина vi и ребро ej не инцидентны. Петле соответствует элемент, равный 2 | |
| Матрица соседства (смежности) вершин графа с b вершинами | квадратная матрица В = ║ aij ║ размерности b, строки и столбцы которой соответствуют вершинам графа; элемент bij равен числу ребер, идущих из вершины vi в вершину vj. | |
| Изоморфизм графов | графы G 1 = (V 1, E 1) и G 2 = (V 2, E 2) изоморфны, если существуют взаимно однозначные отображения f: V 1® V 2 и g: E 1® E 2, сохраняющие инцидентность | |
| Полный граф | граф без кратных ребер (и иногда без петель), в котором две любые вершины соединены ориентированным или неориентированным ребром. Полный неориентированный граф без петель Kb с b вершинами содержит  ребер
| |
| Двудольный граф | граф, множество вершин которого разбито на два непересекающихся класса: V =  È  , а ребра связывают вершины только из разных классов
| |
| Степень s(α) вершины α | для графа без петель – число ребер в звезде Zα. Сумма степеней всех вершин графа равна удвоенному числу ребер | |
| Подграф | часть графа, если она является графом, т.е. вместе с каждым ребром в подграф должны включаться оба конца ребра | |
| Путь [ α, β ] | последовательность ребер графа, образующая непрерывную траекторию по ребрам и вершинам графа, согласованную с ориентацией ребер; (α – начало, β – конец пути) | |
| Цепь [ α, β ] | последовательность ребер графа, образующая непрерывную траекторию, связывающую вершины α и β, если считать все ребра графа неориентированными; (α и β – концы цепи) | |
| Контур (соотв. цикл) | путь (соотв. цепь) с совпадающими концами | |
| Связный граф | граф, любые две вершины которого связаны цепью | |
| Расстояние d (v 1, v 2) между двумя вершинами неориентированного связного графа | число ребер (или сумма длин ребер, если ребрам приписаны длины), минимальное среди всех цепей, связывающих v 1и v 2 | |
| Дерево | связный граф без циклов, т.е. граф, все ребра которого ациклические. В любом конечном дереве число ребер на 1 меньше числа вершин | |
| Корневое дерево | дерево, в котором выбрана вершина (корень); множество вершин дерева разбивается на ярусы по величине расстояния до корня | |
| Остов графа G | подграф D, содержащий все вершины графа G и являющийся деревом. Относительно остова D все ребра подграфа G \ D называются хордами | |
| Четный (эйлеров) граф | граф, степени всех вершин которого - четные числа. | |
| Гамильтонов путь | элементарный путь, проходящий через все вершины графа по одному разу | |
| Цикломатическое число ν(G) графа G | размерность подпространства четных подграфов в линейном пространстве всех подграфов графа G. В графе с p ребрами, b вершинами и k компонентами: ν(G) = p - b + k; для связного графа ν(G) = p - b + 1 | |
| (k, l)-полюсник | сеть с (k + l) выделенными вершинами - полюсами, разбитыми на два класса: k входных и l выходных полюсов. (1, 1)-полюсник называется двухполюсной сетью | |
| Параллельно-последовательная сеть | сеть, полученная из однореберных сетей в результате конечного числа параллельных и последовательных соединений. Класс параллельно-последовательных сетей (сокращенно, Π-сетей) определяется индуктивно: (1) однореберная сеть есть Π-сеть; (2) если S 1и S 2- Π-сети, то S 1• S 2и S 1Ú S 2такжеΠ-сети | |
| Поток в сети с заданными пропускными способностями ребер | пара (f, w), где w – некоторая ориентация всех неориентированных ребер сети, а f (e) – заданная на множестве всех ребер сети функция с неотрицательными значениями, не превосходящими пропускных способностей ребер с (е), и такая, что в каждой внутренней вершине сумма значений потока по ребрам, входящим в вершину, равна сумме значений потока по ребрам, исходящим из вершины | |
| Сечение в сети | множество ребер, блокирующее все цепи из α S в β S. При его удалении сеть становится несвязной, причем полюсы α S и β S попадают в разные компоненты связности | |
| Теорема Форда-Фалкерсона о максимальном потоке | максимальная величина потока R maxчерез сеть S равна минимальной из пропускных способностей с minее простых сечений | |
| Дискретная игра | система, представляющая собой: дискретное множество ситуаций; правила игры, определяющие возможные переходы из одной ситуации в другую; подмножество заключительных ситуаций, в каждой из которых определен результат игры (выигрыш первого, выигрыш второго, ничья) | |
| Игра двух лиц с открытой информацией | игра с поочерёдными ходами игроков, в которой на каждом шаге обоим игрокам известна текущая ситуация | |
| Стратегия f игрока A | соответствие  , назначающее для каждой ситуации  , в которой может оказаться игрок A, один определенный ход  из множества допустимых 
| |
| Выигрышная стратегия | стратегия, выбор которой игроком приводит к ситуации его выигрыша при любом выборе стратегии противника | |
| Беспроигрышная стратегия | стратегия, выбор которой игроком приводит к ситуации его выигрыша или ничьей при любом выборе стратегии против-ника | |
| Хроматическое число графа | Минимальное число красок, которыми можно правильно раскрасить все вершины графа |