Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 14 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 09:16 
Не в сети
Начинающий
Зарегистрирован:
30 янв 2015, 09:05
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число веревочек можно перерезать так чтобы сетка не распалась на куски?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 09:20 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 17742
Откуда: Беларусь, Минск
Cпасибо сказано: 1240
Спасибо получено:
3796 раз в 3515 сообщениях
Очков репутации: 714

Добавить очки репутацииУменьшить очки репутации
Tanj, нужно оставить верёвочки, которые образуют периметр прямоугольника сетки, т. е. две горизонтальные и две вертикальные верёвочки. Остальные можно перерезать. Вам остаётся только посчитать. :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 10:39 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 4198
Cпасибо сказано: 70
Спасибо получено:
899 раз в 817 сообщениях
Очков репутации: 209

Добавить очки репутацииУменьшить очки репутации
Andy, к сожалению это не подходит. Внутренность то упадет.
Задачу можно переформулировать так - найти связный граф с минимальным количеством ребер, у которого вершины расположены в целочисленных точках прямоугольника 50х600.

Upd. Даже не так, у нас же есть изначальный граф. Ну, надеюсь, понятно...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 11:07 
Не в сети
Light & Truth
Зарегистрирован:
28 фев 2012, 18:40
Сообщений: 2209
Cпасибо сказано: 433
Спасибо получено:
1044 раз в 768 сообщениях
Очков репутации: 9

Добавить очки репутацииУменьшить очки репутации
Волейбольная сетка имеет вид прямоугольника размером 50 × 600 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?
Решение:
Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а ребрами – веревочки. В этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. Будем убирать ребра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число ребер в нашем графе в этот момент. Количество вершин осталось тем же – 51 • 601 = 30651. Число ребер в дереве на 1 меньше числа вершин и, следовательно, в нашем дереве будет 30650 ребер. Сначала же их было 601 • 50 + 600 • 51 = 60650. Таким образом, можно удалить 30000 ребер, то есть у волейбольной сетки можно перерезать 30000 веревочек (но не более!). http://zaba.ru/cgi-bin/tasks.cgi?tour=b ... solution=1

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 11:12 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 4198
Cпасибо сказано: 70
Спасибо получено:
899 раз в 817 сообщениях
Очков репутации: 209

Добавить очки репутацииУменьшить очки репутации
Да, примерно такое решение я и имел ввиду. Надо еще только привести пример такого графа, но это просто.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 11:13 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 17742
Откуда: Беларусь, Минск
Cпасибо сказано: 1240
Спасибо получено:
3796 раз в 3515 сообщениях
Очков репутации: 714

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Andy, к сожалению это не подходит. Внутренность то упадет.
Задачу можно переформулировать так - найти связный граф с минимальным количеством ребер, у которого вершины расположены в целочисленных точках прямоугольника 50х600.

Upd. Даже не так, у нас же есть изначальный граф. Ну, надеюсь, понятно...

swan, по-моему, ещё одна задача с "нехорошей" формулировкой... Мне бы и в голову не пришло рассматривать граф как модель волейбольной сетки. :o

Что значит "внутренность ... упадёт"? Волейбольная сетка привязывается к стойкам в четырёх углах.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 11:38 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 4198
Cпасибо сказано: 70
Спасибо получено:
899 раз в 817 сообщениях
Очков репутации: 209

Добавить очки репутацииУменьшить очки репутации
Тут стойки вообще не рассматриваются. Здесь имеется ввиду сетка как самостоятельный объект. А волейбольная говорит лишь о ее виде.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 11:41 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 17742
Откуда: Беларусь, Минск
Cпасибо сказано: 1240
Спасибо получено:
3796 раз в 3515 сообщениях
Очков репутации: 714

Добавить очки репутацииУменьшить очки репутации
swan, тогда и надо говорить о графе в виде сетки, а не о волейбольной сетке. Впрочем, ладно. Главное, чтобы автор вопроса поняла суть задачи.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 11:55 
Не в сети
Light & Truth
Зарегистрирован:
28 фев 2012, 18:40
Сообщений: 2209
Cпасибо сказано: 433
Спасибо получено:
1044 раз в 768 сообщениях
Очков репутации: 9

Добавить очки репутацииУменьшить очки репутации
Там мысль такая: если из полного графа на n вершинах удалить (n – 2) рёбер, то граф останется связным.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 12:17 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 4198
Cпасибо сказано: 70
Спасибо получено:
899 раз в 817 сообщениях
Очков репутации: 209

Добавить очки репутацииУменьшить очки репутации
Мысль совсем другая, ну да ладно

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ]  На страницу 1, 2  След.

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Какое наибольшее число точек сочленения может быть в графе

в форуме Дискретная математика, Теория множеств и Логика

TI_ProJecT

0

704

19 дек 2011, 07:01

Какое максимальное число банок краски можно купить

в форуме Алгебра

Yulashka

4

627

23 мар 2012, 20:29

На какое число можно было бы разрезать моток верёвки?

в форуме Алгебра

ilonka

1

407

11 апр 2014, 17:58

Какое наибольшее количество равнобедренных треугольников

в форуме Задачи со школьных и студенческих олимпиад

Anchikov

3

850

22 дек 2013, 10:39

Какое наибольшее значение может принимать сумма a + b + c?

в форуме Дифференциальное исчисление

MishaVN

4

92

09 дек 2018, 13:22

Какое число зашифровано?

в форуме Алгебра

roman4rever

17

751

16 сен 2013, 17:38

Какое число больше

в форуме Алгебра

Pavel_Kotoff

1

86

14 янв 2019, 15:06

Какое число больше?

в форуме Алгебра

Talanov

12

688

29 дек 2013, 04:43

Какое наибольшее количество гостей могло прийти к Иринке?

в форуме Алгебра

WildSpirit

2

509

16 май 2012, 22:25

Вот по этой программе какое можно составить задание?

в форуме Информатика и Компьютерные науки

Su-34

0

372

13 сен 2012, 15:56


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved