В неориентированном графе $G=(V; E)$, заданном множеством вершин $V=\{1; 2; 3; 4; 5; 6\}$ и множеством рёбер $$E=\{(1, 5); (1, 6); (2, 3); (2, 4); (2, 5); (2, 6); (3, 4); (3, 5); (3, 6); (4, 5); (4, 6)\},$$найти эйлеров цикл.
Ответ:
Решение:
В неориентированном графе $G=(V; E)$, заданном множеством вершин $V=\{1; 2; 3; 4; 5\}$ и множеством рёбер $$E=\{(1, 2); (1, 4); (2, 3); (2, 4); (2, 5); (3, 4); (4, 5)\},$$найти эйлеров цикл.
Ответ:
Решение:
Руководство компании пригласило на празднование Нового Года шесть иностранных гостей. Их нужно рассадить за двухместные столики так, чтобы сидящие за одним столиком могли разговаривать на языке, известном обоим. По-французски говорят Арман, Вивьен и Жером, по-английски — Базилио, Гарри и Жером, по-испански — Базилио, Вивьен и Дамиан. Других языков никто из них не знает. Как рассадить этих шестерых? Придумайте хотя бы один способ.
Ответ:
Решение:
Руководство компании пригласило на празднование Нового Года шесть иностранных гостей. Их нужно рассадить за круглым шестиместным столом так, чтобы любые двое, сидящие рядом, могли разговаривать на языке, известном обоим. По-французски говорят Арман, Вивьен и Жером, по-английски — Базилио, Гарри и Жером, по-испански — Базилио, Вивьен и Дамиан. Других языков никто из них не знает. Как рассадить этих шестерых? Придумайте хотя бы один способ.
Ответ:
Решение:
Однажды где-то на дорожке в городском парке Рассеянный Ученый обронил очки. Он попытался их найти, но стало только хуже, — во-первых, он не помнит, где он потерял очки, а во-вторых, он уже не знает, где он сейчас. Но тут ему повстречались его юные друзья Валя и Коля.
— Ерунда, — сказал Коля. Мы сейчас быстро обежим парк и вернемся сюда же к вам. Валя пройдет ровно по разу по некоторым дорожкам, а я — ровно по разу по всем остальным. И мы обязательно найдем ваши очки. Только никуда не уходите!
— Ах, друзья мои! Как жаль, что у вас ничего не выйдет! — воскликнул Ученый.
— Как не выйдет? Мы обязательно их найдем!
— Очки вы, может, и найдете. Но вы не сможете по разу пройти по всем дорожкам и при этом вернуться сюда.
Прав ли Ученый? Если да, объясните почему. Если не прав, то покажите, как можно обойти парк двумя разными путями из какой-нибудь точки, пройдя по всем дорожкам ровно по разу и вернувшись в исходную точку.
— Ерунда, — сказал Коля. Мы сейчас быстро обежим парк и вернемся сюда же к вам. Валя пройдет ровно по разу по некоторым дорожкам, а я — ровно по разу по всем остальным. И мы обязательно найдем ваши очки. Только никуда не уходите!
— Ах, друзья мои! Как жаль, что у вас ничего не выйдет! — воскликнул Ученый.
— Как не выйдет? Мы обязательно их найдем!
— Очки вы, может, и найдете. Но вы не сможете по разу пройти по всем дорожкам и при этом вернуться сюда.
Прав ли Ученый? Если да, объясните почему. Если не прав, то покажите, как можно обойти парк двумя разными путями из какой-нибудь точки, пройдя по всем дорожкам ровно по разу и вернувшись в исходную точку.
Ответ:
Решение:
Однажды где-то на дорожке в городском парке Рассеянный Ученый обронил очки. Он попытался их найти, но стало только хуже, — во-первых, он не помнит, где он потерял очки, а во-вторых, он уже не знает, где он сейчас. Но тут ему повстречались его юные друзья Валя и Коля.
— Ерунда, — сказал Коля. Мы сейчас быстро обежим парк и вернемся сюда же к вам. Валя пройдет ровно по разу по некоторым дорожкам, а я — ровно по разу по всем остальным. И мы обязательно найдем ваши очки. Только никуда не уходите!
— Ах, друзья мои! Как жаль, что у вас ничего не выйдет! — воскликнул Ученый.
— Как не выйдет? Мы обязательно их найдем!
— Очки вы, может, и найдете. Но вы не сможете по разу пройти по всем дорожкам и при этом вернуться сюда.
Прав ли Ученый? Если да, объясните почему. Если не прав, то покажите, как можно обойти парк двумя разными путями из какой-нибудь точки, пройдя по всем дорожкам ровно по разу и вернувшись в исходную точку.
— Ерунда, — сказал Коля. Мы сейчас быстро обежим парк и вернемся сюда же к вам. Валя пройдет ровно по разу по некоторым дорожкам, а я — ровно по разу по всем остальным. И мы обязательно найдем ваши очки. Только никуда не уходите!
— Ах, друзья мои! Как жаль, что у вас ничего не выйдет! — воскликнул Ученый.
— Как не выйдет? Мы обязательно их найдем!
— Очки вы, может, и найдете. Но вы не сможете по разу пройти по всем дорожкам и при этом вернуться сюда.
Прав ли Ученый? Если да, объясните почему. Если не прав, то покажите, как можно обойти парк двумя разными путями из какой-нибудь точки, пройдя по всем дорожкам ровно по разу и вернувшись в исходную точку.
Ответ:
Решение:
На плоскости 20 точек были попарно связаны между собой отрезками (рёбрами) — каждая точка с каждой другой. Затем случайным образом выбрали 35 рёбер и удалили их. Найдите вероятность того, что получившийся граф связен (то есть из любой точки можно дойти до любой другой по рёбрам).
Такую конструкцию, состоящую из точек и отрезков (прямых или кривых линий), связывающих некоторые из точек, в математике называют графом. Точки называют вершинами, а отрезки — рёбрами графа.
Такую конструкцию, состоящую из точек и отрезков (прямых или кривых линий), связывающих некоторые из точек, в математике называют графом. Точки называют вершинами, а отрезки — рёбрами графа.
Ответ:
Решение:
Вдоль южного берега бескрайнего моря цепочкой раскинулся архипелаг из бесконечного количества островов. Острова соединены бесконечной цепочкой мостов, и каждый остров соединён мостом с берегом. В случае сильного землетрясения каждый мост независимо от других с вероятностью $p=0{,}5$ разрушается. Какова вероятность того, что после сильного землетрясения с первого острова можно будет перебраться по сохранившимся мостам на берег?
Ответ:
Решение:
На межплеменную конференцию прибыли делегации трех племен: Мумба, Юмба и Джумба. В делегации Мумба шесть членов, каждый из них знает всех своих соплеменников, а на конференции познакомился с семью членами других делегаций. В делегации Юмба 11 членов, каждый из них знает всех своих соплеменников и на конференции познакомился с двумя членами других делегаций. В делегации Джумба каждый знает всех своих соплеменников и познакомился с четырьмя членами других делегаций. Какое наименьшее количество членов может быть в делегации племени Джумба?
Ответ:
Решение:
В графе 8 вершин, нет петель, и две любые вершины были связаны единственным ребром (такой граф называется полным). Выбрали 11 случайных рёбер и удалили их. Найдите вероятность того, что получившийся граф по-прежнему связный (то есть найдется путь между любыми двумя вершинами). Результат округлите до тысячных.
Ответ:
Решение:
На столе из одинаковых спичек выложили 16 маленьких шестиугольников, как показано на рисунке.
В самой левой вершине получившегося графа сидит муравей М, а в точке Г снаружи сидит гусеница. Муравей умеет ползать только по спичкам, а гусеница не умеет переползать через спички. Сколько спичек нужно убрать, чтобы гусеница могла проползти в центр любого шестиугольника, а муравей мог доползти до любой вершины любого шестиугольника?
В самой левой вершине получившегося графа сидит муравей М, а в точке Г снаружи сидит гусеница. Муравей умеет ползать только по спичкам, а гусеница не умеет переползать через спички. Сколько спичек нужно убрать, чтобы гусеница могла проползти в центр любого шестиугольника, а муравей мог доползти до любой вершины любого шестиугольника?
Ответ:
Решение:
В графе нет петель и кратных ребер, а вершин на 10 меньше, чем ребер. Какое наименьшее количество циклов может быть в таком графе?
Ответ:
Решение:
Города и дороги в Анчурии образуют граф, показанный на рисунке.
Когда в Анчурию приходит сезон дождей, ливни размывают часть дорог, причем каждая дорога размывается с вероятностью $p=0{,}5$ независимо от других дорог. Какова вероятность того, что из любого города в любой другой по-прежнему можно будет проехать по неразмытым дорогам?
Когда в Анчурию приходит сезон дождей, ливни размывают часть дорог, причем каждая дорога размывается с вероятностью $p=0{,}5$ независимо от других дорог. Какова вероятность того, что из любого города в любой другой по-прежнему можно будет проехать по неразмытым дорогам?
Ответ:
Решение:
Города и дороги в Анчурии образуют граф, показанный на рисунке.
Когда в Анчурию приходит сезон дождей, ливни размывают часть дорог, причем каждая дорога размывается с вероятностью $p=0{,}5$ независимо от других дорог. Какова вероятность того, что из города $A$ в город $B$ по-прежнему можно будет проехать по неразмытым дорогам?
Когда в Анчурию приходит сезон дождей, ливни размывают часть дорог, причем каждая дорога размывается с вероятностью $p=0{,}5$ независимо от других дорог. Какова вероятность того, что из города $A$ в город $B$ по-прежнему можно будет проехать по неразмытым дорогам?
Ответ:
Решение:
В Долине Пяти Озер есть пять одинаковых озер, некоторые из которых соединены ручьями. Маленькие караси появляются на свет только в озере $S$. Пока карась взрослеет, он ровно четыре раза переходит из одного озера в другое по какому-нибудь ручью (карась выбирает ручей наудачу), а затем остается жить в том озере, в котором оказался. Из каждой тысячи карасей в среднем 375 остается жить в озере $S$, а остальные остаются жить в озере $B$, в других озерах не остается жить никто. Определите, сколько ручьев в Долине Пяти Озер.
Ответ:
Решение: