ИГРА НА ГРАФЕ

— игра, представленная в следующем виде. Дан Бержа граф с выделенным подмн-вом с X «начальных» вершин. Один из игроков (какой именно — обычно определяется жребием) в качестве своего хода выбирает некоторую вершину затем делает ход 2-й игрок, выбирая вершину после этого 1-й игрок

выбирает вершину и т. д. Во многих играх победителем считается тот, кто первый выберет тупиковую вершину — такую z, что (т. е., что противник лишен возможности сделать очередной ход). Игрок, выбравший в какой-то момент игры вершину в ядре — таком для которого имеет возможность, независимо от ответа противника, следующим своим ходом опять выбрать вершину в S и т. д., т. е. застраховать себя от проигрыша. Мотут существовать и другие стратегии беспроигрышной игры (даже на графе, не имеющем ни одного ядра). В более сложных играх элементы графа L снабжаются весами, и тогда после остановки игры победитель определяется, напр., по сумме весов выбранных им вершин. См. также Игр теория. А. А. Зыков.