Подсчёт путей в ориентированном графе по таблице смежности
Условие
Ориентированный граф дорог задан таблицей смежности: единица на пересечении строки X и столбца Y означает, что есть дорога из X в Y (только в эту сторону), ноль — дороги нет. Строка П1: 0 1 1 0 0 0 0; строка П2: 0 0 0 1 1 0 0; строка П3: 0 0 0 1 0 0 0; строка П4: 0 0 0 0 0 1 1; строка П5: 0 0 0 0 0 1 0; строка П6: 0 0 0 0 0 0 1; строка П7: 0 0 0 0 0 0 0. Сколько различных путей ведёт из пункта П1 в пункт П7?
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Шаг 1. Как читать таблицу ориентированного графа
П1 П2 П3 П4 П5 П6 П7 П1 0 1 1 0 0 0 0 П2 0 0 0 1 1 0 0 П3 0 0 0 1 0 0 0 П4 0 0 0 0 0 1 1 П5 0 0 0 0 0 1 0 П6 0 0 0 0 0 0 1 П7 0 0 0 0 0 0 0 Главное: строка — откуда, столбец — куда. Таблица несимметрична, и это нормально: движение одностороннее. Чтобы узнать, откуда можно въехать в пункт, надо смотреть его столбец, а не строку.
Шаг 2. Переводим таблицу в список дорог
Выпишем все единицы построчно:
П1→П2, П1→П3, П2→П4, П2→П5, П3→П4, П4→П6, П4→П7, П5→П6, П6→П7.
Всего 9 дорог. Заметим, что каждая дорога ведёт от пункта с меньшим номером к пункту с большим, значит нумерация уже годится как порядок подсчёта: обрабатывая П1, П2, …, П7 подряд, мы каждый раз знаем всё о предшественниках.
Осталось ещё 3 шага
Шаг 3. Считаем пути до середины графа
Шаг 4. Доводим до П7
Шаг 5. Проверка перечислением
Бесплатно · займёт минуту
Частые ошибки
- ✗
Читают таблицу как симметричную и добавляют несуществующие обратные дороги.
- ✗
Путают строку и столбец: чтобы узнать, кто ведёт в П4, смотрят строку П4 вместо столбца П4.
- ✗
Считают количество единиц (их 9) и выдают это как число путей.
- ✗
Не замечают короткую дорогу П4→П7 и учитывают въезд в П7 только через П6 — получают 3.
- ✗
По инерции дают П5 те же два пути, что и П4, хотя в П5 ведёт только одна дорога — из П2.