Составители:
Рубрика:
36
Приложение 2
Примерный список индивидуальных задач
1. Составление программы решения задачи о назначениях.
2. Программа обхода конем шахматной доски произвольных размеров.
3. Программа превращения связного неориентированного графа в связный
смешанный граф с максимальным количеством ориентированных ребер.
4. Программа нахождения эйлерова цикла в связном ориентированном графе,
заданном матрицей смежности вершин.
5. Программа нахождения эйлерова цикла в связном
неориентированном графе,
заданном матрицей смежности.
6. Проверка условия разнообразия для задачи о назначениях, где двудольный граф
задан матрицей смежности вершин.
7. Граф задан перечнем ребер с указанием весов. Написать программу построения
остовного дерева с помощью алгоритма Краскала.
8. Граф задан матрицей весов. Написать программу построения остовного дерева с
помощью алгоритма Прима
.
9. Построение остовного графа с помощью «жадного» алгоритма (вершины графа
заданы своими координатами на плоскости).
10. Определение изоморфности двух графов по их матрицам смежности (вершин).
11. Определение изоморфности двух графов по их матрицам инцидентности.
12. Определение системы ребер, которые надо удалить из графа, заданного матрицей
смежности вершин, чтобы осталось дерево.
13. Программа нахождения максимального количества ребер в связном
неориентированном графе, которые можно сделать ориентированными с
сохранением связности графа.
14. На плоскости собрали некий механизм, состоящий из шестеренок с одинаковым
шагом (т.е. расстоянием между соседними зубьями). Все шестеренки
пронумерованы и для каждой из них известны номера шестеренок, с которыми
она зацеплена
. Составить программу, определяющую, можно ли привести весь
механизм в движение, вращая какую-нибудь из шестеренок.
15. Определение двудольности графа по его матрице смежности вершин.
16. Построение максимального разреза в графе.
17. Нахождение цикла в графе, заданном матрицей смежности вершин.
18. Даны три пробирки по 100 мл. На двух из них имеются
одинаковые метки,
помечающие некоторые целые количества мл. Первоначально непомеченная
пробирка заполнена жидкостью, а две другие – пустые. Составить программу,
которая по количеству меток и их расположению определяет, можно ли отмерить
с помощью переливаний 1 мл жидкости в одной из пробирок, и если да, то
привести пример минимальной цепочки переливаний. Например. для 1 метки 33
цепочка
состоит из 4 переливаний.
19. Нахождение кратчайшего пути в графе, заданном матрицей смежности вершин.
20. Определить по матрице смежности вершин графа, является ли он деревом.
21. Построение гамильтонова пути на полном ориентированном графе.
22. Определение возможности построения гамильтонова цикла на полном ор. графе.
23. Построение гамильтонова цикла на полном ориентированном графе.
