Задали тут дочке задачу:
"Волейбольная сетка — прямоугольник 50х600 клеток. Какое наибольшее число веревочек можно перерезать, чтобы сетка не распалась".
Прочитала я условие и непонятно мне изначально, вне зависимости от разбиения
сетки на квадратики, что подразумевается под понятием "не распалась".
На две части по вертикали? А если останется верхняя веревка, соединенная
с верхними растяжками, и две ( а может быть достаточно одной?)вертикальные боковые веревки, соединенные с нижними растяжками, то сетка считается
нераспавшейся? Или подразумевается, что нужно оставить внешний квадрат, перерезав все внутри? Меня всегда удивляют подобные некорректные условия.
Конференция "Ребенок от 10 до 13""Ребенок от 10 до 13"
Раздел: Домашние задания
Отвечать в конференциях и заводить новые темы может любой участник, независимо от наличия регистрации на сайте 7я.ру.
Задача на графы:
Кировская ЛМШ, 2000 г, 7 класс.
http://zaba.ru/cgi-bin/tasks.cgi?tour=books.sms700.grafy4
или кружок мм 9 класса, здесь есть подсказка
http://mmmf.math.msu.su/archive/20022003/z9a/z9030315.html
Решение:
Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а ребрами - веревочки. В этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. Будем убирать ребра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число ребер в нашем графе в этот момент. Количество вершин осталось тем же - 51 · 601 = 30651. Число ребер в дереве на 1 меньше числа вершин и, следовательно, в нашем дереве будет 30650 ребер. Сначала же их было 601 · 50 + 600 · 51 = 60650. Таким образом, можно удалить 30000 ребер, то есть у волейбольной сетки можно перерезать 30000 веревочек (но не более!) 30.11.2007 12:45:52, Viera
Большое спасибо! Распечатаю и дома проникнемся :-)
А как объяснить, что в Вашей ссылке на ММ дают для 9 класса, а в Кировской школе это проходят в 7 классе?
30.11.2007 12:56:32, Татьянчик
:-)) Мамины мозги тоже нуждаются в тренировке,может быть даже в большей степени.
Просто мы вчера вечером вместе задачи решали и условие этой обеим было не понятно. Эта задача дополнительная. Не хочешь - не решай. Моей интересно, да и мне тоже. 30.11.2007 15:47:37, Татьянчик
Так если она и правда на теорию графов, которую не объясняли (и правильно), то в ней мало смысла в отношении тренировки мозгов. Для мозгов бывают задачи, где ничего дополнительно знать не нужно, но нужно думать с тем что есть.
30.11.2007 16:01:43, пчела Майя
9 класс мат кружок - это может быть не хуже института, а вот 7 класс школы - это нет.
30.11.2007 17:06:09, пчела Майя
Кировская ЛМШ, 2000 г, 7 класс.
http://zaba.ru/cgi-bin/tasks.cgi?tour=books.sms700.grafy4
или кружок мм 9 класса, здесь есть подсказка
http://mmmf.math.msu.su/archive/20022003/z9a/z9030315.html
Решение:
Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а ребрами - веревочки. В этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. Будем убирать ребра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число ребер в нашем графе в этот момент. Количество вершин осталось тем же - 51 · 601 = 30651. Число ребер в дереве на 1 меньше числа вершин и, следовательно, в нашем дереве будет 30650 ребер. Сначала же их было 601 · 50 + 600 · 51 = 60650. Таким образом, можно удалить 30000 ребер, то есть у волейбольной сетки можно перерезать 30000 веревочек (но не более!) 30.11.2007 12:45:52, Viera
А как объяснить, что в Вашей ссылке на ММ дают для 9 класса, а в Кировской школе это проходят в 7 классе?
30.11.2007 12:56:32, Татьянчик
Теорию графов проходят на 2-м курсе на IT и матем. специализациях. По крайней мере так было у нас.
А на 3-м применяют в специальных курсах по специальности.
А зачем это в 7 классе и в 9 классе зачем? 30.11.2007 13:13:29, jii
А на 3-м применяют в специальных курсах по специальности.
А зачем это в 7 классе и в 9 классе зачем? 30.11.2007 13:13:29, jii
А я думаю, что в мозгах соответствующее место для теории графов появиться только к 18 годам, к окончанию полового развития.
30.11.2007 15:29:11, jii
Тем чем она в вашей реге занимается :)))).
Если серьезно, то если ей задали и ей это было бы понятно, то она решила бы сама, а не у мамы бы спрашивала. 30.11.2007 16:09:28, jii
Если серьезно, то если ей задали и ей это было бы понятно, то она решила бы сама, а не у мамы бы спрашивала. 30.11.2007 16:09:28, jii
Просто мы вчера вечером вместе задачи решали и условие этой обеим было не понятно. Эта задача дополнительная. Не хочешь - не решай. Моей интересно, да и мне тоже. 30.11.2007 15:47:37, Татьянчик
А в институте нам так все понятно объяснили. Красота. А мне моя мама тоже подсовывала книжку об этом классе в 7-м. Было непонятно абсолютно.
30.11.2007 16:15:18, jii
Может и 9-ый, но только без мамы, и в кружке.
30.11.2007 17:19:58, jii
