Что означает хроматическое число простого графа?
Раскраски, паросочетания и сетевое планирование
Хроматическое число, теорема Холла и критический путь.
Как будете решать?
Блок 1. Один верный вариант
Сколько цветов нужно для нечётного цикла ?
В графе конфликтов занятий что может означать цвет вершины?
Что называют паросочетанием?
На пути выбрано только ребро . Каково это паросочетание?
Какое паросочетание называется совершенным?
Каково условие Холла для покрытия всей левой доли ?
Какой граф зависимостей используется в базовой модели сетевого планирования?
Как определяется срок проекта при неограниченном числе исполнителей?
Блок 2. Краткий ответ
Найдите хроматическое число полного графа .
целое число
Каков размер наибольшего паросочетания в ?
целое число
В двудольном графе у трёх левых вершин всего два общих возможных соседа. Каков максимально возможный размер паросочетания на этих пяти вершинах?
целое число
Для работ длительности , зависимости , , , . Найдите минимальный срок проекта.
целое число
Чему равно хроматическое число цикла ?
целое число
Блок 3. Несколько верных вариантов
Какие утверждения о раскрасках простых графов верны?
Отметьте все верные варианты
Какие утверждения о паросочетаниях верны?
Отметьте все верные варианты
Что верно о теореме Холла?
Отметьте все верные варианты
Что правильно в модели расписания через раскраску?
Отметьте все верные варианты
Какие формулы верны для работ в вершинах DAG при неограниченных ресурсах?
Отметьте все верные варианты
Завершение теста
Все ответы сохраняются автоматически. Нажмите для отправки на проверку.