Цель индивидуального задания

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

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

2.2.1 Выполняется при самостоятельной работе.

Выполнить анализ своего индивидуального задания. В соответствии с результатами анализа выполнить поиск необходимого теоретического материала. Изучить теоретический материал, соответствующий варианту индивидуального задания. Разработать алгоритм или использовать найденный для решения индивидуального задания, при этом:

- определить все необходимые данные и их структуру;

- сформулировать математическую постановку задания;

- разработать структурную схему алгоритма решения задания;

- словесно описать работу алгоритма решения задания;

- определить вычислительную эффективность алгоритма.

Записать разработанный алгоритм на языке C# в виде windows-приложения. Разработать контрольные тесты для отладки приложения и определения временных параметров его работы и отладить приложение.

2.2.2 Выполняется совместно с преподавателем в компьютерном зале.

Набрать на компьютере код приложения индивидуального задания. Выполнить отладку приложения. Показать результаты работы приложения преподавателю. Копии экранов всех этапов работы приложения подготовить для отчета по индивидуальному заданию. Оформить отчет по индивидуальному заданию и включить его в отчет по вычислительной практике.

Варианты индивидуальных заданий

2.3.1 Задача определения Гамильтонова цикла.

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

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

Рисунок 2.1 – Гамильтонов цикл для графа из восьми вершин.

В задании использовать связанный граф, содержащий не менее 15 вершин.

2.3.2 Задача коммивояжера.

Задача коммивояжера звучит так: определить кратчайший путь по заданным n городам таким образом, чтобы каждый город посещался только один раз и конечным пунктом оказался город, с которого началось путешествие. Задачу можно смоделировать при помощи взвешенного графа, вершины которого представляют города, а веса ребер определяются расстояниями между городами. Значение n >=16.

2.3.3 Задача о рюкзаке.

Дано n предметов весом w₁, w₂,...,w_n и ценой v₁, v₂,..., v_n, а также рюкзак, выдерживающий вес W. Необходимо найти подмножество предметов, которое можно разместить в рюкзаке, и которое имеет максимальную стоимость. Значение n >=16.

2.3.4 Задача игры с участием двух игроков, например, крестики – нолики.

Назовем игрока, проставляющего на игровой доске крестики, игроком x, а игрока, проставляющего на игровой доске нолики - игроком 0. Состояние игры отражается соответствующей позицией на игровой доске.

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

2.3.5 Задача определения точек сочленения графа.

Точкой сочленения графа является вершина, при удалении которой граф разделяется на отдельные связные компоненты (см. рисунок 2.2).

Рисунок 2.2 – Пример точек сочленения простого графа.

Определить все точки сочленения графа. В задании использовать связанный граф, содержащий не менее 16 вершин.

2.3.6 Задача определения мостов графа.

Ребро графа является мостом, если после его удаления граф разбивается на два не связанных между собой подграфа, то есть, на две отдельные связные компоненты (см. рисунок 2.3).

Рисунок 2.3 – Пример моста простого графа.

Определить все мосты графа. В задании использовать связанный граф, содержащий не менее 16 вершин.

2.3.7 Задача определения двудольного графа.

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

Рисунок 2.4 –Примеры простых двудольных графов.

Определить является ли считанный из файла граф двудольным. В задании использовать связанные графы, содержащие не менее 10 вершин.

1.3.8 Трёхцветная раскраска графа Петерсена.

Граф называется t-раскрашиваемым, если он обладает t-раскраской, при этом каждое ребро графа соединять вершины, раскрашенные в разные цвета. Пример трехцветной раскраски графа изображен на рисунке 2.5.

Рисунок 2.5 – Пример трехцветной раскраски графа.

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

2.3.9 Для графа считанного из фала определить кратчайший путь между вершинами, заданными в режиме диалога. Изучить и использовать алгоритм Беллмана-Форда. В задании использовать связанные графы, содержащие не менее 16 вершин.

2.3.10 Для графа считанного из фала определить кратчайший путь между вершинами, заданными в режиме диалога. Изучить и использовать алгоритм Флойда-Варшалла (Floyd-Warshall). В задании использовать связанные графы, содержащие не менее 16 вершин.

2.3.11 Стягивающим деревом графа G называется связанное дерево, содержащее все вершины V графа G. «Стоимость» стягивающего дерева вычисляется как сумма стоимостей всех ребер, входящих в это дерево. Например, стоимость стягивающего дерева изображенного на рисунке 2.6 равна 37.

Рисунок 2.6 – Пример стягивающего дерева графа.

Для графа считанного из фала определить минимальное по стоимости ребер стягивающее дерево. Изучить и использовать алгоритм Крускала (Kruskal). В задании использовать связанные графы, содержащие не менее 18 вершин.

2.3.12 Для графа считанного из фала определить минимальное по стоимости ребер стягивающее дерево. Изучить и использовать алгоритм Прима (Prim). В задании использовать связанные графы, содержащие не менее 20 вершин Пример стягивающего дерева см. на рисунке 2.6.

2.3.13 Каждое ребро графа можно рассматривать как канал, по которому движется продукт. Каждый канал имеет заданную пропускную способность – весовую характеристику ребра, например, весовая характеристика ребра пятьдесят литров может означать перекачку 50 литров жидкости в минуту для трубопровода. Вершины являются точками пересечения каналов. Ч ерез вершины продукт проходит, не накапливаясь. Иными словами, скорость поступления продукта в вершину должна быть равна скорости его удаления из вершины.

Для графа считанного из фала определить минимальный поток между вершинами заданными в режиме диалога. Изучить и использовать метод Форда-Фалкерсона (Ford and Fulkerson). В задании использовать связанные графы, содержащие не менее 16 вершин.

2.3.14 Известно, что граф, считанный из файла не дерево. Проверить, можно ли удалить из него только одну вершину (вместе с инцидентными ей ребрами), чтобы в результате получилось связанное дерево. В задании использовать связанные графы, содержащие не менее 16 вершин.

2.3.15 Известно, что граф, считанный из файла, содержит циклы. Проверить, можно ли удалить из него только одно ребро, чтобы в результате получилось связанное дерево. В задании использовать связанные графы, содержащие не менее 16 вершин.

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

2.3.17 Для графа считанного из фала определить максимальное по стоимости ребер стягивающее дерево. В задании использовать связанные графы, содержащие не менее 20 вершин Пример стягивающего дерева см. на рисунке 2.6.

2.3.18 Каждое ребро графа можно рассматривать как канал, по которому движется продукт. Каждый канал имеет заданную пропускную способность – весовую характеристику ребра, например, весовая характеристика ребра пятьдесят литров может означать перекачку 50 литров жидкости в минуту для трубопровода. Вершины являются точками пересечения каналов. Ч ерез вершины продукт проходит, не накапливаясь. Иными словами, скорость поступления продукта в вершину должна быть равна скорости его удаления из вершины.

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

2.3.19 Если вершина графа инцидентна ребру, то считается, что она «накрывает» это ребро. Вершинным «покрытием» графа называется множество вершин, «накрывающих» все его ребра. Для графа считанного из фала определить минимальное по числу вершин вершинное «покрытие» графа. В задании использовать связанные графы, содержащие не менее 20 вершин

2.3.20 Обод – это граф, вершины которого V0,V1,…,Vn (n>=2) можно занумеровать так, что для всех i (1 <= i <= n-1) вершина Vi соединена с Vi-1 и Vi+1, вершина V0 с вершиной Vn и других ребер нет. Для графа считанного из фала найти все его подграфы, которые являются ободами. В задании использовать связанные графы, содержащие не менее 16 вершин.

Тема 3 ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ НА РЕФЕРАТ