1
голос
0
ответов
15 показов
Какое наименьшее количество дорог может быть в стране?
В стране некоторые пары городов соединены дорогами. Оказалось, что есть круговые маршруты (без повторяющихся городов) из 3, 4, 5, 6, 7, 8, 9 и 10 доро ...
0
голосов
0
ответов
13 показов
Покрытие графа заданным количеством ребер
Пусть даны множества вершин графов, содержащие n/2, n/2+1, ..., n = 2k вершин (для четного n), и (n+1)/2, (n+1)/2+1, ..., n = 2k+1 вершин (для нечетно ...
1
голос
0
ответов
40 показов
Шестиуличный (или шестиулочный?) город
Пешеход обошёл шесть улиц одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь раз. Могло ли это быть, если известно, ...
0
голосов
0
ответов
36 показов
Построить граф.
Построить граф.По построенному графу построить:граф, дополнительный данному.граф, изоморфный данному.
3
голоса
1
ответ
108 показов
Какое наименьшее значение может принимать сумма всех этих чисел?
А) В вершинах квадрата расставлены натуральные числа. Известно, что из двух чисел, стоящих в концах любой стороны, одно делится на другое, а из двух ч ...
1
голос
0
ответов
65 показов
Какое наибольшее число городов может быть в районе? [закрыт]
В районе автобусное сообщение устроено так, что любой город соединен автолинией не более, чем с тремя другими городами, и из любого города можно попас ...
1
голос
1
ответ
67 показов
Числа на дереве
Дано дерево G, в вершинах которого расставили неотрицательные числа ссуммой 1, после чего для каждого ребра посчитали произведение чисел в егоконцах и ...
1
голос
0
ответов
89 показов
Можно ли из верхней доски получить нижнюю?
Попробуйте из верхней доски получить нижнюю!Или докажите, что это невозможно.(Разрешаются только обычные (буквой Г) ходы конём, выходить за пределы до ...
0
голосов
0
ответов
230 показов
Докажите, что если степень каждой вершины графа не превосходит d
Докажите, что если степень каждой вершины графа не превосходит d, то его можноправильно раскрасить в d + 1 цвет.
0
голосов
0
ответов
196 показов
Пусть G — связный граф, который не является графом-путём
Пусть G — связный граф, который не является графом-путём. Докажите, что в G естьтри вершины v1, v2, v3, в результате удаления которых вместе со всеми ...
0
голосов
1
ответ
111 показов
Комбинаторная головоломка
В большую коробку положили k коробок поменьше. В некоторые из них положили k коробок ещё поменьше. В некоторые из этих последних коробок положили k ко ...
0
голосов
0
ответов
86 показов
Как представить грамматику типа 0 или 1 в виде графа?
Как это сделать? Типа 2 и 3 легко представляются в виде графа, где вершина - Нетерминал, а ребро - Терминал.Если нельзя - то какие есть другие способы ...
1
голос
1
ответ
137 показов
Доказать тождество из теории графов
Здравствуйте! Помогите, пожалуйста, доказать тождество, будьте добры$$\sum_{i=1}^{n-1}\binom{n}{i}i^{n-i-1} (n-i)^{i-1} = 2 n^{n-2}$$
1
голос
0
ответов
137 показов
Минимальное число ребер в пути
Пусть задан ориентированный граф G(V, E) и s, t ∈ V . Покажите, чтоминимальное число ребер в пути из s в t совпадает с максимальным значением φ(t) − φ ...
2
голоса
0
ответов
147 показов
Число путей между вершинами графа
Пусть задан простой ориентированный граф G(V, E) и s, t ∈ V . Обозначим через α длину минимального пути из s в t. Покажите, что максимальное число пут ...
166 вопросов
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.