Построить орграф (не менее 10 вершин, 20 дуг), являющийся моделью, некоторой прикладной задачи. Провести анализ данного графа (определить сильные компоненты, базы, антибазы; построить иерархию) и интерпретировать полученные результаты.
Крупный интернет-магазин ювелирных изделий для привлечения и удержания клиентов принял решение внедрить рекомендательную систему в своей системе электронного бизнеса. Рекомендательные системы строятся на основе технологии анализа клиентских сред. Профиль пользователя – это структура, выражающая предпочтения пользователя или группы пользователей на основе примеров. Если созданы профили пользователей, то в момент обращения какого-то клиента система подбирает похожие профили и, учитывая степень схожести, составляет рекомендации для клиента. Пусть создается профиль сегмента VIP-клиентов интернет-магазина SerenaGold на основе предложений от «Бриллиантов Якутии», и построен граф предпочтений, представленный на рисунке. Вершины соответствуют предложениям, причем если предложение
Пусть задана последовательность целых чисел (5,4,4,4,3,3,3,2). Является ли данная последовательность графической и для какого графа (связный, гамильтонов, дерево)? Если ответ положительный, то на основе приведенных в лекции критериев с помощью d-процедуры построить соответствующий граф. 4. Алгоритм нахождения максимальных независимых множеств приведен в книге Теория графов. Алгоритмический подход (Н. Кристофидес, стр. 46-49). Используя данный алгоритм, найдите максимальные независимые множества для графа, изображенного на рис. 3.1 (стр. 44). Проверьте правильность работы критерия останова.
Найти ядро графа, представленного матрицей смежности.
Предположим, что имеется квадратная таблица, состоящая из 16 ячеек. Ячейка контролирует себя и соседние, граничащие с ней ячейки. Определите наименьшее возможное число контролирующих ячеек и места их расположения в таблице, чтобы был обеспечен контроль всех ячеек таблицы.
На графе представлена схема, в которой вершины соответствуют клеммам, а ребра – прямым металлическим полоскам проводников. Для физически осуществимых соединений проводники не должны пересекаться, поэтому их нужно распределить по нескольким параллельным платам, учитывая, что клеммы «доступны» на всех платах. Определите минимальное число плат для реализации этих соединений.
На рисунке представлен граф, отражающий каналы связи между членами некоторой группы (каждой передаче сообщения от
IT-компания получила заказы на реализацию нескольких проектов, причем каждый проект может быть реализован за одно и то же время с привлечением некоторого подмножества ресурсов из множества ресурсов, имеющихся в наличии. Понятие ресурса понимается в широком смысле (разработчики, обладающие теми или иными компетенциями; компьютеры определенной мощности; некоторые приложения и программные среды и т.п.). В таблице представлены проекты и список ресурсов. Для каждого проекта символом «+» отмечены те ресурсы, которые используются при его реализации. Укажите те проекты, которые можно выполнять одновременно за отведенный промежуток времени в предположении, что все проекты начинаются в один и тот же момент времени.
Предположим, что вычислительная система включает n вычислительных устройств разной производительности для решения n типов задач. Временные затраты на решение задачи
Для «задачи о свадьбах» четко сформулируйте алгоритм, придумайте иллюстративный пример для двудольного графа 5,5K, подробно распишите шаги алгоритма.
В период прохождения обучения в летней IT-школе, организованной компанией «PaRus», за каждым слушателем закрепляется наставник. В результате собеседования каждый из трех обучающихся указал наиболее предпочтительные кандидатуры наставников. На рисунке представлен граф, который отражает эти предпочтения. Каждое ребро определяет назначение слушателю одного из наставников, но у каждого слушателя должен быть только один наставник. Укажите наставника для каждого слушателя с учетом его предпочтений.
Найти максимальное паросочетание в чередующемся дереве.
Модифицировать алгоритм Прима для нахождения остова максимального суммарного веса и привести иллюстративный пример. 15. Тематика предстоящей летней школы включает разделы передовых технологий программирования. Всего предполагается прочитать 10 лекций, причем в определенной последовательности Л1-Л10. С учетом занятости сотрудников, читающих лекции, предполагается следующее распределение: Иванов А.А. – Л1, Л4, Л6, Л10; Сергеев А.Д. – Л2, Л3, Л7, Л9; Петров В.С. – Л5, Л8. Предполагается, что продолжительность лекции составляет 1.5 часа, и в день планируется не более трех лекций. Для составления расписания предложено построить математическую модель в виде неориентированного графа, в котором вершины соответствуют лекциям, и две вершины соединяются ребром, когда они не могут быть прочитаны одновременно (например, их должен читать один и тот же сотрудник, возможны и другие причины). Соответствующий граф представлен на следующем рисунке. Предложите такое расписание для чтения лекций, чтобы был соблюден их порядок, и на это было затрачено минимальное количество часов.
Решить задачу о максимальном потоке для двунаправленной сети, представленной на рисунке. Матрица весов P задана в следующей таблице (заполнить пропуски произвольными числами).
Предложите матричную реализацию алгоритма Форда-Фалкерсона, основанную на матричном алгоритме для двунаправленного графа и приведите иллюстративный пример.
Специалисты научно-исследовательского центра по борьбе с вредителями пришли к выводу, что в этом году снова ожидается массированная миграция кукурузного мотылька. Необходимы решительные меры, иначе сельское хозяйство понесет значительные убытки. Специалисты решили определить дешевый способ обработки полей, при котором каждый мотылек наверняка подвергнется действию ядохимикатов. Считается, что стоимость опрыскивания любого пути миграции прямо пропорциональна максимальному числу мотыльков, которые могут им воспользоваться. Поэтому для решения проблемы была использована карта-схема путей миграции, представленная на рисунке. Здесь пропускная способность дуг равна числу мотыльков (в тысячах), которые, по мнению специалистов, будут мигрировать по данному пути. Определить пути миграции для интенсивной обработки ядохимикатами с воздуха с помощью специальных самолетов (пропускные способности дуг (7,6), (7,8) задайте самостоятельно).
Российская компания «Программные системы» занимается разработкой программного обеспечения на заказ в различных областях. В таблице представлена исходная информация о проекте, который посвящен разработке базы данных для медицинской страховой компании. На основе этой информации построена сетевая модель проекта. Проведите временной анализ проекта и составьте календарный план его реализации. Какие работы влияют на время реализации проекта?
Рассмотрим задачу снабжения ряда магазинов крупной торговой сети 777 товарами, поступающими с одного склада. На рисунке представлен граф, который изображает карту одного из районов мегаполиса. Здесь изображены магазины торговой сети и перекрестки дорог. Необходимо принять решение о размещении на одном их перекрестков склада непродовольственной продукции. Основным критерием является минимизация суммы всех расстояний от вершин-магазинов до склада. Матрица кратчайших расстояний представлена в таблице.
Для некоторой пьесы или фильма постройте модель взаимодействия героев в виде знакового неорграфа и проанализируйте сбалансированность на различных этапах развития сюжета.