Приветствую Вас!
Сейчас в школьные контрольные старших классов, по типу ВПР и МЦКО, стали добавлять задания с графами. Вроде бы тема не новая, маячила где-то там в 5-6 классе, в учебниках о ней почти ничего, и учителя как-то обходят ее стороной. Итог — попадаешь на контрольную и абсолютно не в курсе событий, что это, как решить и при чем здесь Эйлер.
Итак, давайте разбираться что такое граф, что за Эйлеров путь и цикл, и как не растеряться на контрольной.
Что такое граф?
Граф — это обычный рисунок из точек и линий.
- Точки называют вершинами,
- Линии — рёбрами.
Никаких формул. Просто точки и линии, которые их соединяют. Например, в задаче может быть 6 кружочков и 7 линий между ними. И спрашивают: можно ли пройти по всем линиям ровно один раз, не проходя по одной и той же дважды?
Кто такой этот Эйлер и при чём здесь он?
Леонард Эйлер — учёный, который жил ещё в XVIII веке. Когда-то в немецком городе Кёнигсберге (ныне Калининград) стояла задача: можно ли пройти по всем мостам города один раз, не проходя дважды по одному и тому же?
Мостов было семь, они соединяли берега и острова.
Эйлер решил: неважно, как именно выглядят улицы и дома — главное, сколько дорог соединяет каждую точку. И придумал совершенно новый подход — теорию графов. Так родилась целая наука.
Эйлеров путь и цикл: простыми словами
- Эйлеров путь — это такой маршрут, где вы проходите по каждой линии (ребру) один раз. Начать и закончить можно в разных точках.
- Эйлеров цикл — это то же самое, но вы возвращаетесь в ту же точку, откуда начали.
А вот и задание из МЦКО 10 класс:
Вам предлагают несколько изображений графов и предлагают выбрать верные варианты, причем, не один, так что "пальцем в небо" сложно будет попасть, как это многие любят делать:
Ну, здесь хотя бы так сяк описано что это такое, но графы бывают и посложнее, поэтому сидеть и "ходить-бродить" по этим зигзагам - тратить уйму времени. Есть простое правило, которое помогает всё это быстро и безошибочно просчитать.
Как понять, есть ли Эйлеров путь?
- Если в графе ровно две вершины, от которых выходит нечётное количество рёбер — путь существует.
- Если все вершины с чётным количеством рёбер — будет ещё и Эйлеров цикл.
- Если нечётных вершин больше двух — увы, никак.
Как решать такие задания?
- Посчитайте, сколько рёбер выходит из каждой вершины.
- Определите, сколько вершин с нечётным количеством рёбер.
Примените правило:
0 нечётных — будет путь и цикл,
2 нечётных — только путь,
больше 2 нечетных— ничего не выйдет.
Теперь вернитесь и посмотрите на те картинки графов из МЦКО. Какие правильные ответы?
А зачем это вообще?
По факту — графы используются в программировании, логистике, интернете, городском планировании, и даже при проектировании микросхем.
Так что, если вы научитесь понимать графы — это не только оценка в школе, но и хороший шаг в сторону профессий будущего.
Благодарю за внимание..