УмбликМатематика
К маршруту 7 класса
Математика7 классБазовый курс 3 подробных конспектовНагрузка предмета в 7 классе: 204 ч, 6 ч/нед.: алгебра 102, геометрия 68, вероятность и статистика 346 заданий и разборов

Графы

Первый год трёх параллельных математических курсов.

Модуль школьной программы

Результат модуля

Что вы научитесь делать

  • Объяснять тему «вершины и рёбра», выбирать подходящий метод и проверять полученный ответ
  • Объяснять тему «пути и циклы», выбирать подходящий метод и проверять полученный ответ
  • Объяснять тему «связность и эйлеров путь», выбирать подходящий метод и проверять полученный ответ

Модуль рассчитан не на беглое чтение, а на несколько занятий. Сначала разберите теорию и примеры, затем решите задания без подсказки и только после этого отметьте модуль изученным.

Подробная теория

Конспекты, формулы и разобранные задачи

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

1

Вероятность и статистика · конспект

Графы

Как описывать сеть связей, считать степени и проверять число рёбер.

Простыми словами

Граф изображает объекты вершинами, а связи — рёбрами. Рисунок можно менять без изменения графа: важны соединения, а не расстояния и углы на картинке.

Опорные записи

Формулы и условия применения

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v\in V}\deg(v)=2|E|

Для конечного неориентированного графа; петля вносит в степень вершины 2.

Алгоритм

Как перейти от условия к ответу

  1. Определите вершины и рёбра, уточните направление связей и последовательно отслеживайте путь, не полагаясь на внешний вид схемы.
  2. Запишите промежуточные величины и выполните вычисления по шагам, не меняя смысл события или статистического показателя.
  3. Пересчитайте степени вершин и убедитесь, что каждое ребро учтено у обоих концов.

Разобранный пример

У треугольного графа рёбра AB, BC, CA. Найдите степень вершины A.

Простой уровень

Подсказка: Посчитайте рёбра, имеющие конец A.

  1. К A примыкают AB и CA.
  2. Степень равна 2.

Ответ: 2

Что проверить перед ответом

  • Не начинайте вычисления, пока не определили смысл величин в теме «Граф, вершина и ребро».
  • Не применяйте формулу без проверки её условий: Определите вершины и рёбра, уточните направление связей и последовательно отслеживайте путь, не полагаясь на внешний вид схемы.
  • После вычисления выполните смысловую проверку: Пересчитайте степени вершин и убедитесь, что каждое ребро учтено у обоих концов.
Попробуйте самостоятельно

В неориентированном графе сумма степеней равна 18. Сколько рёбер?

Сначала решите без подсказки. После этого раскройте пошаговый разбор и сопоставьте переходы со своей записью.

Показать подсказку и решение

Каждое ребро учтено двумя концами.

  1. 2|E|=18.
  2. |E|=9.

Ответ: 9

Полная статья и три уровня задач

2

Вероятность и статистика · конспект

Пути в графах

Как договориться о терминах обхода графа и находить кратчайшее расстояние.

Простыми словами

Граф изображает объекты вершинами, а связи — рёбрами. Рисунок можно менять без изменения графа: важны соединения, а не расстояния и углы на картинке.

Опорные записи

Формулы и условия применения

d(u,v)=min⁡{число рёбер пути из u в v}d(u,v)=\min\{\text{число рёбер пути из }u\text{ в }v\}

Расстояние в невзвешенном графе; при отсутствии пути расстояние считают бесконечным.

Алгоритм

Как перейти от условия к ответу

  1. Определите вершины и рёбра, уточните направление связей и последовательно отслеживайте путь, не полагаясь на внешний вид схемы.
  2. Запишите промежуточные величины и выполните вычисления по шагам, не меняя смысл события или статистического показателя.
  3. Пересчитайте степени вершин и убедитесь, что каждое ребро учтено у обоих концов.

Разобранный пример

Маршрут A−B−C−D−E проходит по четырём последовательным рёбрам. Какова его длина в невзвешенном графе?

Простой уровень

Подсказка: Считайте переходы, не вершины.

  1. Переходы AB, BC, CD, DE.
  2. Длина 4.

Ответ: 4

Что проверить перед ответом

  • Не начинайте вычисления, пока не определили смысл величин в теме «Связность, путь, цепь и цикл».
  • Не применяйте формулу без проверки её условий: Определите вершины и рёбра, уточните направление связей и последовательно отслеживайте путь, не полагаясь на внешний вид схемы.
  • После вычисления выполните смысловую проверку: Пересчитайте степени вершин и убедитесь, что каждое ребро учтено у обоих концов.
Попробуйте самостоятельно

Граф имеет вершины A,B,C,D,E и только рёбра AB,BC. Сколько компонент связности?

Сначала решите без подсказки. После этого раскройте пошаговый разбор и сопоставьте переходы со своей записью.

Показать подсказку и решение

Изолированные вершины считаются отдельными компонентами.

  1. A,B,C образуют одну компоненту.
  2. D и E дают ещё две; всего 3.

Ответ: 3

Полная статья и три уровня задач

3

Вероятность и статистика · конспект

Эйлеров путь

Когда можно пройти каждое ребро ровно один раз и как степени задают начало и конец.

Простыми словами

Граф изображает объекты вершинами, а связи — рёбрами. Рисунок можно менять без изменения графа: важны соединения, а не расстояния и углы на картинке.

Опорные записи

Формулы и условия применения

#{v:deg⁡(v) нечётна}∈{0,2}\#\{v:\deg(v)\text{ нечётна}\}\in\{0,2\}

Критерий эйлеровой цепи в неориентированном графе при связности всех вершин ненулевой степени.

Алгоритм

Как перейти от условия к ответу

  1. Определите вершины и рёбра, уточните направление связей и последовательно отслеживайте путь, не полагаясь на внешний вид схемы.
  2. Запишите промежуточные величины и выполните вычисления по шагам, не меняя смысл события или статистического показателя.
  3. Пересчитайте степени вершин и убедитесь, что каждое ребро учтено у обоих концов.

Разобранный пример

У связного неориентированного графа все степени чётные. Сколько нечётных вершин в нём?

Простой уровень

Подсказка: Используйте буквальное условие чётности всех степеней.

  1. Ни одна вершина не имеет нечётной степени.
  2. Количество равно 0.

Ответ: 0

Что проверить перед ответом

  • Не начинайте вычисления, пока не определили смысл величин в теме «Эйлеров обход».
  • Не применяйте формулу без проверки её условий: Определите вершины и рёбра, уточните направление связей и последовательно отслеживайте путь, не полагаясь на внешний вид схемы.
  • После вычисления выполните смысловую проверку: Пересчитайте степени вершин и убедитесь, что каждое ребро учтено у обоих концов.
Попробуйте самостоятельно

Связный граф имеет степени 1,2,2,3. Сколько возможных начальных вершин у незамкнутой эйлеровой цепи?

Сначала решите без подсказки. После этого раскройте пошаговый разбор и сопоставьте переходы со своей записью.

Показать подсказку и решение

Начало должно быть одной из двух нечётных вершин.

  1. Нечётные степени 1 и 3 принадлежат двум вершинам.
  2. Обе могут быть началом при обратном порядке обхода: 2.

Ответ: 2

Полная статья и три уровня задач

Учебный маршрут

Все материалы по порядку

Используйте этот список как маршрут повторения: отдельная страница каждого урока содержит дополнительные задания, тренажёры или связи с соседними темами.

Шаг 1 · УрокГрафыШаг 2 · УрокПути в графахШаг 3 · УрокЭйлеров путь

Первоисточники

Откуда взяты границы модуля

Уроки написаны Умбликом, а состав и последовательность тем сверены с федеральной рабочей программой. Порядок прохождения в конкретной школе может отличаться.