ИГРА НА ГРАФЕ
— игра, представленная в следующем виде. Дан Бержа граф

с выделенным подмн-вом

с X «начальных» вершин. Один из игроков (какой именно — обычно определяется жребием) в качестве своего хода выбирает некоторую вершину

затем делает ход 2-й игрок, выбирая вершину

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