Что такое граф
Граф состоит из точек и линий, которые их соединяют. Точки называют вершинами, линии — рёбрами. Положение точек на рисунке и длина линий не важны, важно только, какие вершины соединены между собой.
Граф рисуют, когда нужно показать связи:
- города и дороги между ними;
- ученики класса и дружба между ними;
- участники турнира и сыгранные партии.
В задачах граф часто не нарисован, и его нужно построить самому. Вершинами станут люди или пункты, рёбрами — дружба, дорога или сыгранная партия. После этого задача обычно решается проще.
Степень вершины: чётные и нечётные вершины
Степень вершины (в школьных задачах её ещё называют валентностью) — число рёбер, которые выходят из этой вершины. Если у человека в классе трое друзей, его вершина имеет степень 3. Вершину называют чётной или нечётной по её степени.
Главное правило: сумма степеней всех вершин равна удвоенному числу рёбер. Каждое ребро имеет два конца, поэтому при подсчёте степеней оно учитывается дважды. Из этого следует, что нечётных вершин в графе всегда чётное количество: 0, 2, 4 и так далее.
С помощью этого правила решают задачи вида «может ли быть так, что…». Пример: в классе 30 человек, у 9 по 3 друга, у 11 по 4, у 10 по 5. Сумма степеней: 9×3 + 11×4 + 10×5 = 27 + 44 + 50 = 121. Число нечётное, а должно быть чётным, поэтому так быть не может. К тому же нечётных вершин здесь 9 + 10 = 19, а их число должно быть чётным.
То же правило помогает, когда нужно нарисовать граф, у которого все вершины нечётные. Вершин должно быть чётное число, например шесть. Три отдельных ребра дадут шесть вершин степени 1.
Цепь, цикл и связный граф
Цепь — путь по рёбрам, в котором ни одна вершина не повторяется. Длина цепи равна числу рёбер в ней. Цикл — путь, который заканчивается в той вершине, с которой начался. В простом цикле другие вершины тоже не повторяются.
Граф связный, если из любой вершины можно добраться до любой другой по рёбрам. Если граф распадается на отдельные куски, он несвязный.
На этих понятиях построены многие задания на построение. Нужен связный граф с девятью вершинами, у которого самая длинная цепь состоит из двух рёбер. Возьми одну центральную вершину и соедини её с остальными восемью. Любая цепь в таком графе проходит через центр и состоит не больше чем из двух рёбер.
У простого цикла длина равна числу его вершин. Поэтому простой цикл длиной 5 нельзя нарисовать меньше чем на пяти вершинах. Это полезно проверять, если задание кажется невыполнимым. Подобные рассуждения встречаются и в комбинаторике.
Как найти кратчайший путь в графе: разбор задания
Задание: между пунктами A, B, C, D, E проложены дороги. Длины в километрах: A–B = 2, A–C = 5, B–C = 1, B–D = 4, C–D = 2, D–E = 3. Найди кратчайший путь от A до E.
Шаг 1. Нарисуй пять точек и соедини их по условию. Если дороги даны таблицей, ребро есть там, где в клетке стоит число. Пустая клетка означает, что прямой дороги нет. Подробнее о таблицах можно прочитать в теме представление данных.
Шаг 2. Выпиши все пути из A в E. До E можно добраться только через D, поэтому нужно сравнить пути до D.
Шаг 3. Посчитай длины:
- A–B–C–D–E: 2 + 1 + 2 + 3 = 8;
- A–B–D–E: 2 + 4 + 3 = 9;
- A–C–D–E: 5 + 2 + 3 = 10.
Шаг 4. Выбери наименьшее. Ответ: 8 км, маршрут A–B–C–D–E.
Короткий путь по числу рёбер не всегда самый короткий по километрам. Здесь путь через B и C длиннее по числу дорог, но выигрывает по расстоянию.
Где ошибаются чаще всего
- Считают только прямые дороги. Если в таблице между A и F стоит 15, это не значит, что путь длиной 15 — самый короткий. Объезд через другие пункты может оказаться короче, поэтому проверяй все пути.
- Забывают про общее число рёбер в задачах про дружбу. Если каждый мальчик дружит с 2 девочками, а каждая девочка с 3 мальчиками, то число дружб считают двумя способами: 2 × (число мальчиков) = 3 × (число девочек). Если мальчиков m, а девочек d, то m = 3k, d = 2k, и в классе 5k человек. Для класса от 20 до 30 человек получается k = 5: 15 мальчиков и 10 девочек. Проверка: 15 × 2 = 30 и 10 × 3 = 30.
- Путают цепь и цикл. В цепи начало и конец разные, в цикле путь замыкается.
- Думают, что рисунок графа должен выглядеть определённым образом. Правильным считается любой рисунок с теми же вершинами и соединениями, даже если линии изогнуты или пересекаются.
Какие задания по графам присылают ученики и как пользоваться страницей
Чаще всего присылают задания седьмого класса. Нужно построить граф с заданными свойствами: связный, с девятью вершинами, с циклом определённой длины или со всеми нечётными вершинами. Ещё встречаются кратчайший путь по схеме или таблице, задачи про дружбу в классе и турнире, а также головоломки про дороги на островах.
Найди похожее задание в списке выше: у каждого есть полный ход решения. Если своего не нашлось, сфотографируй условие и отправь на сайт, чтобы получить решение с пояснениями. Для задач на циклы заранее проверь определение простого цикла в своём учебнике. Это подскажет, можно ли в нём повторять вершины, а от этого зависит рисунок. Для задач, где графом описывают набор вариантов, пригодятся темы множества и логика и комбинаторика.