Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 2 |
[ Сообщений: 14 ] | На страницу 1, 2 След. |
|
Автор | Сообщение | |
---|---|---|
Tanj |
|
|
|
||
Вернуться к началу | ||
Andy |
|
|
Tanj, нужно оставить верёвочки, которые образуют периметр прямоугольника сетки, т. е. две горизонтальные и две вертикальные верёвочки. Остальные можно перерезать. Вам остаётся только посчитать.
|
||
Вернуться к началу | ||
swan |
|
|
Andy, к сожалению это не подходит. Внутренность то упадет.
Задачу можно переформулировать так - найти связный граф с минимальным количеством ребер, у которого вершины расположены в целочисленных точках прямоугольника 50х600. Upd. Даже не так, у нас же есть изначальный граф. Ну, надеюсь, понятно... |
||
Вернуться к началу | ||
ALEXIN |
|
|
Волейбольная сетка имеет вид прямоугольника размером 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 |
||
Вернуться к началу | ||
swan |
|
|
Да, примерно такое решение я и имел ввиду. Надо еще только привести пример такого графа, но это просто.
|
||
Вернуться к началу | ||
Andy |
|
|
swan писал(а): Andy, к сожалению это не подходит. Внутренность то упадет. Задачу можно переформулировать так - найти связный граф с минимальным количеством ребер, у которого вершины расположены в целочисленных точках прямоугольника 50х600. Upd. Даже не так, у нас же есть изначальный граф. Ну, надеюсь, понятно... swan, по-моему, ещё одна задача с "нехорошей" формулировкой... Мне бы и в голову не пришло рассматривать граф как модель волейбольной сетки. Что значит "внутренность ... упадёт"? Волейбольная сетка привязывается к стойкам в четырёх углах. |
||
Вернуться к началу | ||
swan |
|
|
Тут стойки вообще не рассматриваются. Здесь имеется ввиду сетка как самостоятельный объект. А волейбольная говорит лишь о ее виде.
|
||
Вернуться к началу | ||
Andy |
|
|
swan, тогда и надо говорить о графе в виде сетки, а не о волейбольной сетке. Впрочем, ладно. Главное, чтобы автор вопроса поняла суть задачи.
|
||
Вернуться к началу | ||
ALEXIN |
|
|
Там мысль такая: если из полного графа на n вершинах удалить (n – 2) рёбер, то граф останется связным.
|
||
Вернуться к началу | ||
swan |
|
|
Мысль совсем другая, ну да ладно
|
||
Вернуться к началу | ||
На страницу 1, 2 След. | [ Сообщений: 14 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 19 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |