Разбираем задачу на графы из ВПР за 7 класс. Узнаем, как связаны количество кусков проволоки и чётность вершин, и почему ответ — 2.
Условие
Из декоративной проволоки нужно спаять плоское украшение в виде листка заданных размеров (см. рисунок), затратив наименьшее возможное количество проволоки. Проволоку можно гнуть под любым углом и спаивать в точках соединения. Какое наименьшее количество кусков проволоки нужно, чтобы изготовить модель, показанную на рисунке?
Что важно знать
Украшение — это граф:
– Вершины — точки соединения проволоки.
– Рёбра — отрезки проволоки между ними.
– Степень вершины — количество рёбер, исходящих из неё.
Например, если из вершины (точки) выходят 3 отрезка, её степень равна 3.
Связный граф
Это граф, в котором от любой вершины можно добраться до любой другой по рёбрам.
Другими словами, фигура не распадается на отдельные части — всё соединено в одно целое.
В нашей задаче украшение (листок) — это связный граф.
Данные по рисунку
– 7 вершин степени 2
– 1 вершина степени 8
– 4 вершины степени 3
Всего вершин: 7 + 1 + 4 = 12.
Идея решения
Каждый кусок проволоки — это непрерывная линия. У него есть два конца.
Эти концы могут находиться только в вершинах с нечётной степенью (1, 3, 5, …). Почему?
Потому что если в вершине сходится чётное количество отрезков, проволока может «пройти сквозь» неё (войти и выйти), не оставляя конца.
А если количество отрезков нечётное, то один из них обязательно будет началом или концом куска.
Правило (из теории графов)
Чтобы «пройти» все рёбра графа (сделать украшение) наименьшим количеством непрерывных кусков, нужно:
– Посчитать количество вершин нечётной степени.
– Разделить это число на 2.
Почему?
У каждого куска ровно два конца, и каждый конец находится в вершине нечётной степени.
Для связного графа этого количества кусков достаточно, чтобы покрыть все рёбра.
Считаем нечётные вершины
– Степень 2 — чётная
– Степень 8 — чётная
– Степень 3 — нечётная
По условию:
– 4 вершины степени 3 → это нечётные.
– Остальные (7 + 1 = 8 вершин) — чётные.
Количество вершин нечётной степени = 4.
Находим количество кусков
4 : 2 = 2
Значит, чтобы собрать всё украшение, потребуется ровно 2 куска проволоки.
(Меньше — невозможно, а двух достаточно, так как украшение — связный граф.)
Ответ: 2.
Почему нельзя одним куском?
Если бы в украшении было 0 или 2 вершины нечётной степени — можно было бы обойтись одним куском (это был бы так называемый эйлеров путь).
Но здесь 4 нечётные вершины, поэтому минимально нужно 2 куска.
Что запомнить
– Задача на графы решается через чётность степеней вершин.
– В вершинах нечётной степени обязательно будут концы кусков проволоки.
– Для связного графа минимальное количество кусков = (количество вершин нечётной степени) / 2.
Полезно? Сохраните в закладки и поделитесь с теми, кто готовится к ВПР по математике.
#ВПР #ВПР7класс #Математика #Графы #Задание11 #Проволока #ПодготовкаКВПР #РазборЗадач