Компьютерная сеть пентагона представляет собой 1000 компьютеров

Компьютерная сеть пентагона представляет собой 1000 компьютеров

Компьютерная сеть Пентагона представляет собой 1000 компьютеров, некоторые пары из которых соединены проводами. Хакер Вася написал вирус, который каждую минуту заражает все компьютеры, напрямую соединённые проводом с уже заражёнными. Известно, что сеть устроена таким образом, что если Вася загрузит свой вирус на любой из компьютеров, то через некоторое время заражённой окажется вся сеть. Докажите, что хакер Вася может таким образом выбрать 90 компьютеров Пентагона, что если он загрузит на них вирус одновременно, то уже через 10 минут заражённой окажется вся сеть.

Каждый компьютер представим вершиной графа, а соединение проводами ребром между ними. Из условия следует, что граф связный. Последовательность вершин, в которой всякие две соседние вершины соединены ребром, а никакое ребро не присутствует дважды, называют цепью. Цепь, которая заканчивается в той же вершине, где она началась, называют замкнутой цепью или циклом. Связный граф, в котором нет циклов, называют деревом.

Если связный граф не является деревом, то можно разорвать одно из его рёбер, входящих в цикл, не нарушая связность графа. Таким образом, разорвав при необходимости часть рёбер, можно от любого связного графа перейти к его остовному дереву. (Остовное дерево определено неоднозначно, однако какое именно остовное дерево будем рассматривать, несущественно.)

Таким образом, перейдём к рассмотрению 1000-вершинного дерева, полученному из начального графа удалением всех циклов. Рассмотрим в этом графе цепь наибольшей длины Возможны два случая.

Если то достаточно заразить вершину A10 (или любую другую, если даже десятой нет), и через 10 минут вся сеть окажется заражённой. Действительно, так как мы выбрали цепь наибольшей длины, то в этом случае нет вершин на расстоянии больше 10 от A10 (иначе можно бы было продлить путь до этой вершины до X или до Y). Поэтому этот случай тривиален.

Если то отделим от графа вершины и всех, кто связан с ними не через A11 (их не меньше 11). Среди отделённых вершин нет вершин на расстоянии больше 10 от A10 (иначе, опять-таки, мы бы получили противоречие с максимальностью цепи). Значит, если мы заразим A10, то вся отделённая часть окажется через 10 минут заражённой.

Заметим, что после отделения останется всё ещё дерево, так как оставшийся граф, очевидно, связен. Повторим описанную процедуру 89 раз. На каждом шаге мы либо исчерпаем компьютеры, либо отделим по крайнем мере вершин, и останется не более 21 компьютера. Повторим для них те же самые рассуждения (но теперь заразим среднюю вершину в самом длинном пути), и получим, что мы как раз выбрали 90 компьютеров, и этого хватает.

Идея рассматривать самые длинные цепи — 2 балла.

Источник

Компьютерная сеть пентагона представляет собой 1000 компьютеров

№№ заданий Решения Ответы Ключ Критерии Инструкция Год Класс Классификатор Олимпиада Тур
Добавить инструкцию Печать Готово, можно копировать.

Читайте также:  Топология сети звезда расходы

Тип 0 № 7462

Компьютерная сеть Пентагона представляет собой 1000 компьютеров, некоторые пары из которых соединены проводами. Хакер Вася написал вирус, который каждую минуту заражает все компьютеры, напрямую соединённые проводом с уже заражёнными. Известно, что сеть устроена таким образом, что если Вася загрузит свой вирус на любой из компьютеров, то через некоторое время заражённой окажется вся сеть. Докажите, что хакер Вася может таким образом выбрать 90 компьютеров Пентагона, что если он загрузит на них вирус одновременно, то уже через 10 минут заражённой окажется вся сеть.

Решение . Каждый компьютер представим вершиной графа, а соединение проводами ребром между ними. Из условия следует, что граф связный. Последовательность вершин, в которой всякие две соседние вершины соединены ребром, а никакое ребро не присутствует дважды, называют цепью. Цепь, которая заканчивается в той же вершине, где она началась, называют замкнутой цепью или циклом. Связный граф, в котором нет циклов, называют деревом.

Если связный граф не является деревом, то можно разорвать одно из его рёбер, входящих в цикл, не нарушая связность графа. Таким образом, разорвав при необходимости часть рёбер, можно от любого связного графа перейти к его остовному дереву. (Остовное дерево определено неоднозначно, однако какое именно остовное дерево будем рассматривать, несущественно.)

X минус A_1 минус A_2 минус \ldots минус A_k минус Y.

Таким образом, перейдём к рассмотрению 1000-вершинного дерева, полученному из начального графа удалением всех циклов. Рассмотрим в этом графе цепь наибольшей длины Возможны два случая.

Если то достаточно заразить вершину A10 (или любую другую, если даже десятой нет), и через 10 минут вся сеть окажется заражённой. Действительно, так как мы выбрали цепь наибольшей длины, то в этом случае нет вершин на расстоянии больше 10 от A10 (иначе можно бы было продлить путь до этой вершины до X или до Y). Поэтому этот случай тривиален.

Если то отделим от графа вершины и всех, кто связан с ними не через A11 (их не меньше 11). Среди отделённых вершин нет вершин на расстоянии больше 10 от A10 (иначе, опять-таки, мы бы получили противоречие с максимальностью цепи). Значит, если мы заразим A10, то вся отделённая часть окажется через 10 минут заражённой.

Заметим, что после отделения останется всё ещё дерево, так как оставшийся граф, очевидно, связен. Повторим описанную процедуру 89 раз. На каждом шаге мы либо исчерпаем компьютеры, либо отделим по крайнем мере вершин, и останется не более 21 компьютера. Повторим для них те же самые рассуждения (но теперь заразим среднюю вершину в самом длинном пути), и получим, что мы как раз выбрали 90 компьютеров, и этого хватает.

Идея рассматривать самые длинные цепи — 2 балла.

Источник

Компьютерная сеть пентагона представляет собой 1000 компьютеров

№№ заданий Решения Ответы Ключ Критерии Инструкция Год Класс Классификатор Олимпиада Тур
Добавить инструкцию Печать Версия для копирования в MS Word
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем

Читайте также:  Компьютерная сеть представляет собой группу компьютеров

Тип 0 № 7462

Компьютерная сеть Пентагона представляет собой 1000 компьютеров, некоторые пары из которых соединены проводами. Хакер Вася написал вирус, который каждую минуту заражает все компьютеры, напрямую соединённые проводом с уже заражёнными. Известно, что сеть устроена таким образом, что если Вася загрузит свой вирус на любой из компьютеров, то через некоторое время заражённой окажется вся сеть. Докажите, что хакер Вася может таким образом выбрать 90 компьютеров Пентагона, что если он загрузит на них вирус одновременно, то уже через 10 минут заражённой окажется вся сеть.

Решение . Каждый компьютер представим вершиной графа, а соединение проводами ребром между ними. Из условия следует, что граф связный. Последовательность вершин, в которой всякие две соседние вершины соединены ребром, а никакое ребро не присутствует дважды, называют цепью. Цепь, которая заканчивается в той же вершине, где она началась, называют замкнутой цепью или циклом. Связный граф, в котором нет циклов, называют деревом.

Если связный граф не является деревом, то можно разорвать одно из его рёбер, входящих в цикл, не нарушая связность графа. Таким образом, разорвав при необходимости часть рёбер, можно от любого связного графа перейти к его остовному дереву. (Остовное дерево определено неоднозначно, однако какое именно остовное дерево будем рассматривать, несущественно.)

Таким образом, перейдём к рассмотрению 1000-вершинного дерева, полученному из начального графа удалением всех циклов. Рассмотрим в этом графе цепь наибольшей длины Возможны два случая.

Если то достаточно заразить вершину A10 (или любую другую, если даже десятой нет), и через 10 минут вся сеть окажется заражённой. Действительно, так как мы выбрали цепь наибольшей длины, то в этом случае нет вершин на расстоянии больше 10 от A10 (иначе можно бы было продлить путь до этой вершины до X или до Y). Поэтому этот случай тривиален.

Если то отделим от графа вершины и всех, кто связан с ними не через A11 (их не меньше 11). Среди отделённых вершин нет вершин на расстоянии больше 10 от A10 (иначе, опять-таки, мы бы получили противоречие с максимальностью цепи). Значит, если мы заразим A10, то вся отделённая часть окажется через 10 минут заражённой.

Заметим, что после отделения останется всё ещё дерево, так как оставшийся граф, очевидно, связен. Повторим описанную процедуру 89 раз. На каждом шаге мы либо исчерпаем компьютеры, либо отделим по крайнем мере вершин, и останется не более 21 компьютера. Повторим для них те же самые рассуждения (но теперь заразим среднюю вершину в самом длинном пути), и получим, что мы как раз выбрали 90 компьютеров, и этого хватает.

Идея рассматривать самые длинные цепи — 2 балла.

Источник

Компьютерная сеть пентагона представляет собой 1000 компьютеров

№№ заданий Решения Ответы Ключ Критерии Инструкция Год Класс Классификатор Олимпиада Тур
Добавить инструкцию Печать Версия для копирования в MS Word
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем

Читайте также:  Аппаратное обеспечение вычислительных сетей аппаратное обеспечение вычислительных сетей

Тип 0 № 7462

Компьютерная сеть Пентагона представляет собой 1000 компьютеров, некоторые пары из которых соединены проводами. Хакер Вася написал вирус, который каждую минуту заражает все компьютеры, напрямую соединённые проводом с уже заражёнными. Известно, что сеть устроена таким образом, что если Вася загрузит свой вирус на любой из компьютеров, то через некоторое время заражённой окажется вся сеть. Докажите, что хакер Вася может таким образом выбрать 90 компьютеров Пентагона, что если он загрузит на них вирус одновременно, то уже через 10 минут заражённой окажется вся сеть.

Решение . Каждый компьютер представим вершиной графа, а соединение проводами ребром между ними. Из условия следует, что граф связный. Последовательность вершин, в которой всякие две соседние вершины соединены ребром, а никакое ребро не присутствует дважды, называют цепью. Цепь, которая заканчивается в той же вершине, где она началась, называют замкнутой цепью или циклом. Связный граф, в котором нет циклов, называют деревом.

Если связный граф не является деревом, то можно разорвать одно из его рёбер, входящих в цикл, не нарушая связность графа. Таким образом, разорвав при необходимости часть рёбер, можно от любого связного графа перейти к его остовному дереву. (Остовное дерево определено неоднозначно, однако какое именно остовное дерево будем рассматривать, несущественно.)

Таким образом, перейдём к рассмотрению 1000-вершинного дерева, полученному из начального графа удалением всех циклов. Рассмотрим в этом графе цепь наибольшей длины Возможны два случая.

Если то достаточно заразить вершину A10 (или любую другую, если даже десятой нет), и через 10 минут вся сеть окажется заражённой. Действительно, так как мы выбрали цепь наибольшей длины, то в этом случае нет вершин на расстоянии больше 10 от A10 (иначе можно бы было продлить путь до этой вершины до X или до Y). Поэтому этот случай тривиален.

Если то отделим от графа вершины и всех, кто связан с ними не через A11 (их не меньше 11). Среди отделённых вершин нет вершин на расстоянии больше 10 от A10 (иначе, опять-таки, мы бы получили противоречие с максимальностью цепи). Значит, если мы заразим A10, то вся отделённая часть окажется через 10 минут заражённой.

Заметим, что после отделения останется всё ещё дерево, так как оставшийся граф, очевидно, связен. Повторим описанную процедуру 89 раз. На каждом шаге мы либо исчерпаем компьютеры, либо отделим по крайнем мере вершин, и останется не более 21 компьютера. Повторим для них те же самые рассуждения (но теперь заразим среднюю вершину в самом длинном пути), и получим, что мы как раз выбрали 90 компьютеров, и этого хватает.

Идея рассматривать самые длинные цепи — 2 балла.

Источник

Оцените статью
Adblock
detector