Графы. Вершины, рёбра, направления и весовая матрица

Читать и строить небольшой граф, различать направленные и ненаправленные связи, составлять весовую матрицу по прямым рёбрам и вычислять вес заданного пути.

Все сети и веса вымышленные, единицы веса условные. В задачах простые графы без петель и параллельных рёбер, все существующие рёбра имеют строго положительные веса. Для нашей весовой матрицы 0 означает отсутствие прямого ребра/дуги, диагональ 0. Это явно выбранное соглашение для данного набора задач: оно не кодирует веса 0 и не сообщает автоматически об отсутствии пути через другие вершины. Все обозначения вершин — латинские буквы.

Для работы достаточно бумаги, ручки и памятки. Сохраняй первую попытку; исправления отмечай другим знаком.

Безопасное начало

Сухие руки, без напитков у техники. Провода и разъёмы не трогай, о неисправности сообщи учителю. Работай по правилам кабинета. Две полные минуты в середине урока — без экрана и заданий. Внешний ИИ, личные аккаунты и личные данные не требуются.

Что уже нужно знать

Модель и её цель из 007, строки/столбцы таблицы из 008, сложение положительных чисел. SQL, списки Python и алгоритмы поиска оптимального пути ещё не требуются.

S0. В модели кабинетов перечислены только их названия. Можно ли по одному перечню узнать, между какими кабинетами есть прямой проход? Какой вид сведений нужен дополнительно?

Устная проба без отметки.

Граф представляет связи

Вершина представляет объект, ребро — непосредственную связь пары объектов. В неориентированном графе ребро не задаёт направление; в ориентированном его задаёт стрелка — дуга. Вес записывают у связи, это условная стоимость, время или другая величина по объявленной модели; геометрическая длина линии не заменяет вес. Путь задают последовательностью допустимых переходов; для ориентированного графа соблюдают стрелки. В наших взвешенных графах вес заданного пути — сумма весов его рёбер, количество рёбер считают отдельно. Весовая матрица хранит прямые связи: строка — откуда, столбец — куда. Существующее ребро имеет положительный вес, 0 означает отсутствие прямого ребра; петель нет, диагональ 0. Для неориентированного графа пары симметричных клеток равны, одно ребро записано дважды. В ориентированном симметрия не обязательна. Ноль клетки не запрещает путь через другие вершины. Эти условия — соглашение нашего урока, не универсальное кодирование нулевых весов.

Все графы вымышленные, без петель/параллельных рёбер; существующие веса строго положительные. Вершины подписаны латиницей. Пересечение линий само по себе не создаёт новую вершину. Положение точек и длина нарисованных линий не являются измерительными данными. Оптимальный путь и количество всех путей будут далее.

Концептуальная иллюстрация. Точные данные определены условиями, таблицами и схемами; предметы на рисунке не являются входными данными.

Личная проба

C1. Неориентированный граф: вершины A, B, C, D; рёбра AB с весом 2, AC с весом 5, BC с весом 1, CD с весом 3. Других рёбер нет. Схема показывает те же данные. Назови число вершин и число рёбер, всех соседей C и наличие прямого ребра AD. Измерять длины линий линейкой не нужно.

Те же связи, что в условии C1; геометрия рисунка не задаёт веса.

Две минуты самому по списку/схеме, затем две на сверку связей. Памятка разрешена.

Сначала направление, затем клетка

Образец на других вершинах: если есть только M→N веса 4, то [M,N]=4, а [N,M]=0. Не добавляем неуказанную обратную дугу. Для неориентированного MN=4 обе клетки были бы равны 4: вид графа — часть условия.

A1. Ориентированный граф имеет только дуги A→B (2), B→C (3), A→C (7), C→D (4). В весовой матрице строка — откуда, столбец — куда; 0 — нет прямой дуги, веса положительные. Укажи клетки [A,B], [B,A], [B,C], [C,B]. Затем проверь последовательность A→B→C→D и вычисли её вес. Нужно ли автоматически переносить вес в обратную клетку?

Сначала своя запись и основание, затем сверка.

Полная пауза

Две минуты без проекции, чтения, вычислений и обсуждения. Отведи взгляд и смени позу.

Прямое ребро и последовательность рёбер

Образец: неориентированные M–N=4 и N–R=2 дают путь M→N→R веса 6. При этом [M,R]=0, если прямого MR нет. Две подписи 4 и 2 складывают; длины линий на бумаге не измеряют.

A2. Дана весовая матрица в порядке P, Q, R, S. Строки: P — 0,4,2,0; Q — 4,0,1,5; R — 2,1,0,3; S — 0,5,3,0. Диагональ 0, остальные нули означают отсутствие прямого ребра, существующие веса положительные. Соответствует ли матрица неориентированному графу по симметрии? Назови вес прямого QP и наличие прямого PS. Проверь путь P→R→Q→S и его вес. Доказывает ли ноль [P,S], что из P вообще нельзя попасть в S?

Три минуты по матрице, две на проверку симметрии, отсутствующего прямого ребра и веса данного пути.

Концептуальная иллюстрация. Точные данные определены условиями, таблицами и схемами; предметы на рисунке не являются входными данными.

Два представления одной сети

Образец порядка проверки: подписать все вершины, внести каждую данную стрелку и вес, задать тот же порядок строк/столбцов. Внести положительные клетки только по прямым дугам, остальные заполнить нулями. Сверить каждую дугу с клеткой, затем прочитать заданный путь по нескольким клеткам. Не добавлять обратные связи ради красивой симметрии.

B1. Построй свою модель вымышленной сети W, X, Y, Z. Заданы только дуги W→X (3), W→Y (6), X→Y (2), Y→Z (4), X→Z (8). Все веса положительные, петель нет. Сначала нарисуй ориентированный граф с четырьмя подписями, пятью стрелками и их весами. Затем заполни всю матрицу в порядке W,X,Y,Z: строка — откуда, столбец — куда, 0 — нет прямой дуги. Проверь путь W→X→Y→Z, вычисли вес и объясни, почему [W,Z]=0 не опровергает этот путь. Сверь две представленные модели по каждой дуге; расположение вершин на бумаге можно выбрать своё. Сначала собственная запись, затем исправления другим знаком.

Заготовка для своей записи:

Шесть минут: 3 на свою схему/матрицу, 2 на проверки, 1 на сверку. Матрица с подписями готова, значения и стрелки ученик вносит сам.

Проверка вымышленного ответа ИИ

AI1. Вымышленный ИИ говорит о B1: «Матрицу всегда отражают симметрично: раз есть X→Y, надо добавить Y→X. Клетка [W,Z]=0 доказывает, что никакого пути W→Z нет». Найди и исправь две ошибки по заданным дугам.

Это заранее составленный учебный пример. Самостоятельно проверь конкретный шаг; обращение к сервису не требуется.

Помощь и резерв

• Меняет строку и столбец местами. Произнеси «из … в …» до чтения клетки.
• Зеркалит любой граф. Проверь, заданы ли обратные дуги.
• Считает 0 запретом любого пути. Раздели прямое ребро и промежуточные вершины.
• Вместо веса считает рёбра. Запиши все слагаемые весов пути.

D1. Резерв. Перерисуй граф C1, поменяв расположение A и D на листе, но сохранив все четыре подписи, пары концов и веса. Станет ли это другой моделью связей только из-за положения точек? Что нужно сверить?

D1 — необязательный резерв на 3–4 минуты после основных попыток. При нехватке времени перенести. H1 и весь тест автоматически вместе не назначаются.

Индивидуальный итог

Четыре полные минуты лично. Условия заранее на бумаге. Памятка и разобранные модели разрешены; ключи и веб-разбор закрыты. Учитель не даёт учебных подсказок. Сбор после четырёх минут.

E1. В весовой матрице строка — откуда, столбец — куда. Клетка [K,L]=5. Какой прямой переход и какой вес она задаёт? Можно ли только по ней объявить [L,K]=5?

E2. В графе только положительные веса. [U,V]=0, но существуют U→T с весом 2 и T→V с весом 3. Нет прямой дуги или вообще нет пути U→V? Обоснуй.

E3. Допустимый путь проходит три ребра с весами 2, 4 и 1. Назови число рёбер и общий вес; почему это разные результаты?

Разбор после своей попытки

Показать ответ после выполнения

После исправления выбери один новый пример из самопроверки.

Файлы для собственной практики

• Точная схема C1

Схема C1 совпадает с полным списком рёбер в условии. Она нужна для чтения графа; компьютер для обязательной практики не требуется. Собственную схему B1 и матрицу строят на бумаге.

Материалы и самопроверка

Презентация, самостоятельный план учителя, рабочий лист, выходной билет и бумажная самопроверка открываются отдельными карточками. DOCX можно смотреть на сайте и скачать. PDF для печати:

• Рабочий лист
• Выходной билет — два на А4
• Самопроверка на бумаге

Самопроверка на сайте: шесть вопросов с пояснениями, отдельно 6–8 минут. Бумажная версия с письменными основаниями и разбором — 8–12 минут. Все шесть новых письменных случаев — ещё 8–10 минут; выбирай прежде всего случай к своей ошибке. Эти модули не прибавляют к основным 45 минутам и не задаются целиком вместе с H1 автоматически. Пояснения и новые случаи для бумажного разбора есть в плане учителя.

Домашний перенос

H1. Дома 5–7 минут на бумаге. Неориентированный граф A,B,C,D имеет только AB=2, BC=4, AD=6. Нарисуй свою схему, запиши строку A весовой матрицы в порядке A,B,C,D и вычисли вес пути A→B→C. Объясни, что означает ноль в клетке [A,C]. Все веса положительные, петель нет.

Полное условие и памятка есть на листе. Решение запиши в тетради. Достаточно 5–7 минут с сохранённой опорой.

Источники

ФРП информатики 7–9 классов, базовый уровень, содержание 9 класса на печатных с. 10–12, результаты с. 19–20 и тематическое планирование с. 40–41. Соответствующий час авторского КТП 2026/2027. Содержание не расширяется до углублённого курса и не подменяется подготовкой к экзамену. Учебник школы не указан; номера параграфов не назначены.

• Федеральная рабочая программа информатики 7–9 классов, базовый уровень
• Информационно-методическое письмо по информатике на 2026/2027 год
• NIST DADS — граф
• NIST DADS — ориентированный граф
• NIST DADS — матричное представление графа
• OpenStax 12.1 — вершины, рёбра и представление связей