https___authedu.mosreg.ru_ej_attachments_files_061_949_228_original_%D0%A0%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5%20%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%20%D0%BD%D0%B0%20%D1%82%D0%B5%D0%BC%D1%83%20%D0%93%D1%80%D

1.

Чтобы уметь решать задачи на графы,
внимательно прочитайте, запомните, примените.
Рассмотрим задачу №2 из 11-ти предложенных для
решения.

2.

Из декоративной проволоки нужно спаять плоское украшение
в виде листка заданных размеров ( см. рисунок), затратив
наименьшее возможное количество проволоки.
Проволоку можно гнуть под любым углом и спаивать в точках
соединения. Какое наименьшее количество кусков проволоки
нужно, чтобы изготовить модель, указанную на рисунке?
Ответ: 2.

3.

Выясним, как связаны количество кусков проволоки и четность вершин,
и почему ответ 2?
1) Что нужно знать:
украшение – это граф;
вершины – точки соединения проволоки;
ребра – отрезки проволоки между ними;
степень вершины – количество ребер, исходящих из нее.
2) Связный граф – это граф, в котором от любой вершины
можно добраться до любой другой по ребрам,
т. е. фигура не распадается на отдельные части – все
соединено в одно целое.
В данной задаче украшение (листок) – это связный граф.

4.

Посчитаем в «украшении» количество вершин и их четность:
7 вершин степени 2,
4 вершины степени 3,
1 вершина степени 8.
Всего вершин: 7 + 1 + 8 = 12.
Каждый кусок проволоки – это непрерывная линия.
У куска проволоки есть два конца, которые могут находиться
только в вершинах с нечетной степенью (1; 3; 5; 7; …).
Потому что, если в вершине сходится четное количество
отрезков, то проволока может пройти сквозь нее – войти и
выйти (можно сказать - сгиб), не оставляя конца.
А если количество отрезков нечетное, то один из кусков
обязательно будет началом или концом куска.

5.

Правило: чтобы пройти все ребра графа (сделать
украшение)
наименьшим количеством непрерывных кусков надо:
а) посчитать количество вершин нечетной степени;
б) разделить это число на 2, т.к. у каждого куска ровно два
конца
и каждый конец находится в вершине нечетной степени.
Для связного графа этого количества кусков достаточно,
чтобы покрыть все ребра.
Считаем вершины: степень 2 – четная; степень 8 – четная;.
степень 3 – нечетная. Количество вершин нечетной степени
равно 4.
Находим количество кусков: 4 : 2 = 2.
Значит, чтобы собрать все украшение, потребуется ровно
два куска проволоки, (меньше – невозможно, а двух
достаточно).
Ответ: 2.

6.

Итак, еще раз:
у каждого куска проволоки есть два конца.
В вершинах нечетной степени он либо начинается, либо заканчивается.
Значит, один кусок проволоки всегда берет на себя ровно две нечетные вершины.
Отсюда вытекает простейшее правило: количество кусков проволоки N/2,
где N-общее количество вершин с нечетной степенью.
Важно знать и помнить: если в фигуре все вершины оказались четными,
это значит, что всю фигуру можно обернуть одним куском проволоки и вернуться
в ту же точку, откуда начали. В этом случае ответ всегда будет – 1.
Если все четные, а две нечетные, то тоже 1 кусок проволоки.
Теперь, какой бы сложной ни была каркасная модель в заданиях ВПР,
вы сможете решить ее за считанные минуты:
просто посчитайте вершины с нечетной степенью
и делите их количество пополам.
Успехов в решении задач на графы.

7.

Для разминки: какую из пяти фигур можно обойти,
не отрывая карандаш от бумаги? Эти задачи тоже из ВПР.
1.
4.
3.
5.
2.