Считать количество путей в ориентированном графе и анализировать таблицы смежности/расписания.
Графы и подсчёт путей
Как считать пути в ориентированном графе
Граф можно задать рисунком (вершины и стрелки-рёбра) или таблицей смежности: в строке i и столбце j стоит 1, если есть ребро из вершины i в вершину j, и 0 — если нет. В задачах ЕГЭ чаще всего требуется найти количество различных простых путей (без повторений вершин) из одной вершины в другую.
Основной метод — расстановка чисел по вершинам (динамическое программирование по топологическому порядку). Алгоритм: в начальную вершину записываем 1. Для каждой следующей вершины (в порядке топологической сортировки) суммируем числа всех вершин, из которых в неё ведут рёбра. Итоговое число в конечной вершине — это и есть количество путей.
Пример: граф A → B, A → C, B → D, C → D. Ищем число путей из A в D. Записываем: A=1. B получает 1 (от A). C получает 1 (от A). D получает 1+1=2 (от B и C). Ответ: 2 пути.
Следующее упражнение опирается на конкретный граф с рёбрами A→B, B→C, C→D, D→E (и согласованными с ними A→C, A→D, B→D). Цепочка A→B→C→D→E делает топологический порядок однозначным: A, B, C, D, E. Обратите внимание: порядок обработки вершин важен — каждую вершину обрабатываем только после того, как обработаны все вершины, из которых в неё ведут рёбра. Если бы рёбер не было, любой порядок был бы равноправен — именно рёбра диктуют последовательность.
Lesson notes
Как считать пути в ориентированном графе
Граф можно задать рисунком (вершины и стрелки-рёбра) или таблицей смежности: в строке i и столбце j стоит 1, если есть ребро из вершины i в вершину j, и 0 — если нет. В задачах ЕГЭ чаще всего требуется найти количество различных простых путей (без повторений вершин) из одной вершины в другую.
Основной метод — расстановка чисел по вершинам (динамическое программирование по топологическому порядку). Алгоритм: в начальную вершину записываем 1. Для каждой следующей вершины (в порядке топологической сортировки) суммируем числа всех вершин, из которых в неё ведут рёбра. Итоговое число в конечной вершине — это и есть количество путей.
Пример: граф A → B, A → C, B → D, C → D. Ищем число путей из A в D. Записываем: A=1. B получает 1 (от A). C получает 1 (от A). D получает 1+1=2 (от B и C). Ответ: 2 пути.
Следующее упражнение опирается на конкретный граф с рёбрами A→B, B→C, C→D, D→E (и согласованными с ними A→C, A→D, B→D). Цепочка A→B→C→D→E делает топологический порядок однозначным: A, B, C, D, E. Обратите внимание: порядок обработки вершин важен — каждую вершину обрабатываем только после того, как обработаны все вершины, из которых в неё ведут рёбра. Если бы рёбер не было, любой порядок был бы равноправен — именно рёбра диктуют последовательность.