← Все тренажёры Раскраски, паросочетания и сетевое планирование

Раскраски, паросочетания и сетевое планирование

Хроматическое число, теорема Холла и критический путь.

19 заданий · Теория графов

Как будете решать?

Режим
Режим

Блок 1. Один верный вариант

1

Что означает хроматическое число простого графа?

2

Сколько цветов нужно для нечётного цикла C5C_5?

3

В графе конфликтов занятий что может означать цвет вершины?

4

Что называют паросочетанием?

5

На пути 1−2−3−41-2-3-4 выбрано только ребро 2−32-3. Каково это паросочетание?

6

Какое паросочетание называется совершенным?

7

Каково условие Холла для покрытия всей левой доли LL?

8

Какой граф зависимостей используется в базовой модели сетевого планирования?

9

Как определяется срок проекта при неограниченном числе исполнителей?

Блок 2. Краткий ответ

10

Найдите хроматическое число полного графа K4K_4.

целое число

11

Каков размер наибольшего паросочетания в K3,5K_{3,5}?

целое число

12

В двудольном графе у трёх левых вершин всего два общих возможных соседа. Каков максимально возможный размер паросочетания на этих пяти вершинах?

целое число

13

Для работ A,B,C,DA,B,C,D длительности 2,3,4,12,3,4,1, зависимости A→BA\to B, A→CA\to C, B→DB\to D, C→DC\to D. Найдите минимальный срок проекта.

целое число

14

Чему равно хроматическое число цикла C6C_6?

целое число

Блок 3. Несколько верных вариантов

15

Какие утверждения о раскрасках простых графов верны?

Отметьте все верные варианты

16

Какие утверждения о паросочетаниях верны?

Отметьте все верные варианты

17

Что верно о теореме Холла?

Отметьте все верные варианты

18

Что правильно в модели расписания через раскраску?

Отметьте все верные варианты

19

Какие формулы верны для работ в вершинах DAG при неограниченных ресурсах?

Отметьте все верные варианты

Завершение теста

Все ответы сохраняются автоматически. Нажмите для отправки на проверку.

Карта заданий (19)

Вход на платформу

Обратная связь

Сообщите об ошибке, задайте вопрос или предложите, что добавить.