Список индивидуальных данных

Общая постановка задачи

1. Сформулировать задачи, согласно вариантам, на языке теории множеств или теории графов.

2. Определить, что для данных задач является траекториями, функционалами и оптимальными значениями функционалов.

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

4. Реализовать алгоритм решения задачи.

1. Подмножество V вершин графа G называется независимым (или внутренне устойчивым), если никакие две вершины из V не смежны. Найти наибольшее по мощности независимое множество вершин заданного графа.

2. Подмножество V вершин графа G называется доминирующим (или внешне устойчивым), если каждая вершина из VG \ V смежна с некоторой вершиной из V. Найти наименьшее по мощности доминирующее множество вершин заданного графа.

3. Требуется расставить на шахматной доске наибольшее число ферзей так, чтобы они не атаковали друг друга. Указание: сведите задачу к задаче поиска независимого множества вершин графа наибольшей мощности (задача №1).

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

5. Задан граф G, все веса ребер равны 1. Найти наименьшее подмножество вершин V Í VG, такое, что каждая вершина графа должна находиться на расстоянии не более 1 от какой-либо вершины из V. Установите связь между данной задачей и задачей № 2.

6. Подмножество V Í VG называется покрытием (вершинным покрытием, опорой) графа G, если каждое ребро из ЕG инцидентно хотя бы одной вершине из V. Найти покрытие минимальной мощности заданного графа. Установите связь между данной задачей и задачей поиска независимого множества вершин графа наибольшей мощности (задача №1).

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

8. Подмножество ребер Е Í ЕG называется реберным покрытием графа G, если каждая вершина из VG инцидентна хотя бы одному ребру из Е. Найти все реберные покрытия заданного графа G.

9. Подмножество попарно несмежных ребер графа называется паросочетанием (или независимым множеством ребер). Найти все паросочетания заданного графа.

10. Паросочетание (см. задачу №9) называется совершенным (или 1-фактором), если оно одновременно является реберным покрытием (см. задачу №8). Найти все совершенные паросочетания заданного графа.

11. Имеется конечное множество исполнителей { х ₁,..., х_n }, каждый из которых может выполнять некоторые из работ { у ₁,..., у_n }. Для каждого исполнителя задан список работ, которые он может выполнять. Нужно распределить исполнителей по работам, т.е. назначить по одному исполнителю на каждую работу, так, чтобы выполнить все работы. Найти все возможные распределения исполнителей по работам. Указание: свести задачу к задаче №10.

12. То же, что и задача №11, только задана стоимость выполнения работы у_i исполнителем х_i, и требуется распределить исполнителей по работам, минимизируя затраты.

13. Два графа G ₁ и G ₂ называются изоморфными, если существует взаимно однозначное соответствие f: VG ₁® VG ₂, такое, что (v, w)Î EG ₂, тогда и только тогда, когда (f (v), f (w))Î EG, т.е. существует соответствие между вершинами графа G ₁ и вершинами графа G ₂, сохраняющее отношение смежности (графы G ₁ и G ₂ отличаются только нумерацией вершин). Определить, являются ли два заданных графа изоморфными.

14. Заданы два графа G ₁ и G ₂. Требуется определить, существует ли в G ₂ порожденный подграф, изоморфный графу G ₁.

15. Заданы множество А и множество В, причем элементами последнего служат некоторые подмножества из первого, и В является покрытием множества А, что означает следующее: объединение всех элементов из В, т.е. соответствующих подмножеств из А, равно множеству А. Требуется найти все покрытия множества А, составленные из элементов множества В.

16. Есть n станков. Каждый из станков делает различные операции (какие задано). При обработке детали необходимо выполнить k заданных операций. Найти минимальное множество станков, требуемых для обработки детали.

17. Определить, имеет ли заданный неориентированный граф гамильтонов цикл.

18. Всего n рабочих. В выездной бригаде должны находиться рабочие, которые все вместе владеют не менее чем k заданными специальностями. Для каждого рабочего задан список его специальностей. Сформировать бригаду из минимального числа рабочих.

19. Существует ли решение в (0,1) – числах следующего уравнения: , и b заданы.

20. Необходимо перевести n тонн груза. Имеется k самолетов грузоподъемностью s ₁, s ₂,…, s_k тонн, . Стоимость рейса c ₁, c ₂,…, c_k тыс. руб. не зависит от массы груза, перевозимого самолетом. Найти оптимальное множество самолетов для перевозки груза.

21. Получить все возможные бинарные отношения между элементами конечного n -элементного множества, удовлетворяющие условиям симметричности и антирефлексивности.

22. Получить все возможные бинарные отношения между элементами конечного n -элементного множества, удовлетворяющие условиям антисимметричности.

23. Задано бинарное отношение между элементами конечного множества мощности n. Проверить является ли данное отношение транзитивным.

24.

Найти все матрицы размера n ´ n с элементами из множества {0,1}, удовлетворяющие следующим условиям:

25. Найти все способы расстановки n ладей на "шахматной" доске размера n ´ n так, чтобы никакие две из них не стояли на одной вертикали или горизонтали.

Дата добавления: 2014-12-27