Программирование на языке высокого уровня

Задание на курсовую работу. Вариант 8.

Игровая программа. Игра "Кейли".

Описание игры.

В игре участвуют два игрока. Полем для игры служит произвольный неориентированный граф , где V — множество вершин; E — множество ребер. Игроки поочередно выбирают по одной вершине из множества V, причем выбранная вершина и все ей смежные выбрасываются из графа. Выигрывает тот из игроков, кто удалит из графа последнюю вершину.

Задание на курсовую работу. Вариант 9.

Игровая программа. Игра "Максимальное взвешенное паросочетание".

Описание игры.

В игре участвуют два игрока. Полем для игры служит произвольный неориентированный граф (где V — множество вершин; E — множество ребер), ребра которого взвешены положительными целыми числами. Игроки поочередно выбирают по одному ребру из множества E так, чтобы выбираемое ребро не имело общих концевых вершин с ранее выбранными. Каждый игрок суммирует веса всех выбранных им ребер. Выигрывает тот игрок, суммарный вес ребер которого первым превысит заданную границу h.

Задание на курсовую работу. Вариант 10.

Игровая программа. Игра "Накрывающее множество".

Описание игры.

В игре участвуют два игрока. «Полем для игры» служит семейство подмножеств C некоторого (базисного) множества B. Игроки поочередно выбирают новые элементы из множества B до тех пор, пока для каждого подмножества из C не будет выбран хотя бы один элемент. Игрок, ход которого приводит к этой ситуации, проигрывает.

Задание на курсовую работу. Вариант 11.

Прикладная программа. Выделение вершинного покрытия графа.

Описание задачи.

Заданы граф , где V — множество вершин; E — множество ребер, и положительное целое число , — мощность множества V. Выделить в графе G вершинное покрытие мощности не более K. Если такого покрытия не существует, выдать соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение найденного покрытия.

Вершинным покрытием графа называется подмножество его вершин такое, что хотя бы один конец каждого ребра из множества E принадлежит .

Задание на курсовую работу. Вариант 12.

Прикладная программа. Выделение доминирующего множества графа.

Описание задачи.

Заданы граф , где V — множество вершин; E — множество ребер, и положительное целое число , где — мощность множества V. Выделить в графе G доминирующее множество мощности не более K. Если такого множества не существует, выдать соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение найденного множества.

Доминирующим множеством графа называется подмножество его вершин такое, что каждое ребро из множества E имеет один конец в подмножестве , а другой — в подмножестве .

Задание на курсовую работу. Вариант 13.

Прикладная программа. Выделение семейства
доминирующих подмножеств в графе.

Описание задачи.

Заданы граф , где V — множество вершин; E — множество ребер, и положительное целое число , где — мощность множества V. Выделить в графе G заданное число z доминирующих подмножеств мощности не более K. Если таких подмножеств не существует, выдать соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение полученных подмножеств.

Доминирующим подмножеством графа называется подмножество его вершин такое, что каждое ребро из множества E имеет один конец в подмножестве , а другой — в подмножестве .

Задание на курсовую работу. Вариант 14.

Прикладная программа. Раскраска графа.

Описание задачи.

Заданы граф , где V — множество вершин; E — множество ребер, и положительное целое число , где — мощность множества V. Раскрасить вершины графа K красками так, чтобы ни одно его ребро не имело соцветных концов. Если такая раскраска невозможна, выдать на экран соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение его вершин на экране.

Задание на курсовую работу. Вариант 15.

Прикладная программа. Разбиение графа.

Описание задачи.

Задан неориентированный граф , где V — множество вершин; E — множество ребер. Разбить множество ребер E графа G на два непересекающихся подмножества и так, чтобы ни один из графов или не содержал ни одного полного подграфа с множеством вершин мощности три и выше. Если подобное разбиение невозможно, вывести соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение графов и .

Полный (под)граф — граф, в котором все вершины попарно смежны.

Задание на курсовую работу. Вариант 16.

Прикладная программа. Множество вершин, разрезающих контуры.

Описание задачи.

Заданы ориентированный граф , где V — множество вершин; A — множество дуг, и положительное целое число , где — мощность множества V. Выделить в графе G подмножество вершин , содержащих хотя бы одну вершину каждого контура, такое, что . Если такого множества нет, вывести соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение вершин из .

Задание на курсовую работу. Вариант 17.

Прикладная программа. Разбиение графа на лес.

Описание задачи.

Заданы неориентированный граф , где V — множество вершин; E — множество ребер, и положительное целое число , где — мощность множества V. Разбить граф G на непересекающихся по вершинам ациклических подграфов. Если разбиение невозможно, выдать соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение найденных подграфов.

Задание на курсовую работу. Вариант 18.

Прикладная программа. Разбиение графа на клики.

Описание задачи.

Заданы неориентированный граф и положительное целое число , где — мощность множества V. Разбить граф G на непересекающихся по вершинам полных подграфов (клик). Если разбиение невозможно, выдать соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение всех клик.

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

Задание на курсовую работу. Вариант 19.

Прикладная программа. Выделение клики.

Описание задачи.

Заданы неориентированный граф , где V — множество вершин; E — множество ребер, и положительное целое число , где — мощность множества V. Выделить в исходном графе клику с числом вершин не менее K. Если такой клики в графе нет, выдать соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение найденной клики.

Под кликой неориентированного графа понимается всякий максимальный полный подграф.

Задание на курсовую работу. Вариант 20.

Прикладная программа. Выделение независимого множества графа.

Описание задачи.

Заданы неориентированный граф , где V — множество вершин; E — множество ребер, и положительное целое число , где — мощность множества V. Выделить в исходном графе независимое множество с числом вершин не менее K. Если такого множества в графе нет, выдать соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение найденного независимого множества.

Под независимым множеством неориентированного графа понимается всякое максимальное подмножество его множества вершин, в котором ни одна пара вершин не соединяется ребром.

Задание на курсовую работу. Вариант 21.

Прикладная программа. Выделение планарных подграфов.

Описание задачи.

Заданы неориентированный граф , где V — множество вершин; E — множество ребер, и положительное целое число , где — мощность множества E. Выделить в исходном графе подмножество ребер мощности не менее K, порождающее планарный подграф. Если такого подмножества в графе нет, выдать соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение ребер из .

Планарный граф — граф, который можно изобразить на плоскости без пересечения ребер.

Задание на курсовую работу. Вариант 22.

Прикладная программа. Кубический подграф.

Описание задачи.

Задан неориентированный граф , где V — множество вершин; E — множество ребер. Выделить в исходном графе подмножество ребер максимальной мощности, порождающее кубический подграф. Если такое подмножество выделить невозможно, выдать соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение ребер из .

Кубическим называется (под)граф, степени всех вершин которого равны либо 3 либо 0.

Задание на курсовую работу. Вариант 23.

Прикладная программа. Гамильтонов цикл.

Описание задачи.

Задан неориентированный граф , где V — множество вершин; E — множество ребер. Выделить в исходном графе гамильтонов цикл. Если граф не содержит такого цикла, вывести на экран соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение найденного цикла.

Гамильтоновым циклом называется цикл, проходящий через каждую вершину графа ровно один раз.

Задание на курсовую работу. Вариант 24.

Прикладная программа. Гамильтонов путь.

Описание задачи.

Задан ориентированный граф , где V — множество вершин; A — множество дуг. Выделить в графе гамильтонов путь. Если граф не содержит такого пути, вывести на экран соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение найденного пути.

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

Задание на курсовую работу. Вариант 25.

Прикладная программа. Стягиваемость графа.

Описание задачи.

Заданы два неориентированных графа и , где — множества вершин графов; — множества ребер. Проверить, можно ли последовательным стягиванием ребер графа получить граф, изоморфный . Предусмотреть графическое представление исходных графов и цветовое выделение стягиваемых ребер.

Операция стягивания ребра e заключается в его замене одной (общей) вершиной так, чтобы все вершины, смежные концам ребра e, остались смежны новой общей вершине.

Задание на курсовую работу. Вариант 26.

Прикладная программа. Остов ограниченной степени.

Описание задачи.

Заданы неориентированный граф , где V — множество вершин; E — множество ребер, и положительное целое число , где — мощность множества V. Построить для графа остов, не содержащий вершин степени выше K. При невозможности построить такой остов выдать на экран соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение остова.

Остовом графа называется его любой ациклический частичный граф.

Задание на курсовую работу. Вариант 27.

Прикладная программа. Самый длинный цикл.

Описание задачи.

Заданы неориентированный граф , где V — множество вершин; E — множество ребер, и положительное целое число K. Ребра графа взвешены положительными целыми числами. Выделить в графе хотя бы один цикл, имеющий длину не менее K. При отсутствии таких циклов в графе, выдать на экран сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение найденного цикла.

Задание на курсовую работу. Вариант 28.

Прикладная программа. Модель пересечения множеств.

Описание задачи.

Задана квадратная матрица , содержащая положительные целые числа. Найти набор множеств такой, что , . Если такой набор не существует, вывести на экран соответствующее сообщение. Предусмотреть графический вывод исходной матрицы на экран.

Задание на курсовую работу. Вариант 29.

Прикладная программа. Редактирование слова.

Описание задачи.

Заданы конечный алфавит , два слова и положительное целое число K, где — множество всевозможных слов в алфавите . Проверить, возможно ли получение слова y из слова x с использованием не более K операций вычеркивания символа и перестановки соседних символов.

Задание на курсовую работу. Вариант 30.

Прикладная программа. Покрытие битового образа прямоугольниками.

Описание задачи.

Заданы (0–1)-матрица M порядка и положительное целое число K. Проверить, возможно ли покрытие всех единичных элементов матрицы M не более чем K прямоугольниками. Исходную матрицу и вариант покрытия представить графически.

Задание на курсовую работу. Вариант 31.