1
голос
0
ответов
27 показов
Какое наибольшее число городов может быть в районе? [закрыт]
В районе автобусное сообщение устроено так, что любой город соединен автолинией не более, чем с тремя другими городами, и из любого города можно попас ...
1
голос
1
ответ
39 показов
Числа на дереве
Дано дерево G, в вершинах которого расставили неотрицательные числа ссуммой 1, после чего для каждого ребра посчитали произведение чисел в егоконцах и ...
1
голос
0
ответов
65 показов
Можно ли из верхней доски получить нижнюю?
Попробуйте из верхней доски получить нижнюю!Или докажите, что это невозможно.(Разрешаются только обычные (буквой Г) ходы конём, выходить за пределы до ...
0
голосов
0
ответов
175 показов
Докажите, что если степень каждой вершины графа не превосходит d
Докажите, что если степень каждой вершины графа не превосходит d, то его можноправильно раскрасить в d + 1 цвет.
0
голосов
0
ответов
147 показов
Пусть G — связный граф, который не является графом-путём
Пусть G — связный граф, который не является графом-путём. Докажите, что в G естьтри вершины v1, v2, v3, в результате удаления которых вместе со всеми ...
0
голосов
1
ответ
94 показа
Комбинаторная головоломка
В большую коробку положили k коробок поменьше. В некоторые из них положили k коробок ещё поменьше. В некоторые из этих последних коробок положили k ко ...
0
голосов
0
ответов
68 показов
Как представить грамматику типа 0 или 1 в виде графа?
Как это сделать? Типа 2 и 3 легко представляются в виде графа, где вершина - Нетерминал, а ребро - Терминал.Если нельзя - то какие есть другие способы ...
1
голос
1
ответ
121 показ
Доказать тождество из теории графов
Здравствуйте! Помогите, пожалуйста, доказать тождество, будьте добры$$\sum_{i=1}^{n-1}\binom{n}{i}i^{n-i-1} (n-i)^{i-1} = 2 n^{n-2}$$
1
голос
0
ответов
121 показ
Минимальное число ребер в пути
Пусть задан ориентированный граф G(V, E) и s, t ∈ V . Покажите, чтоминимальное число ребер в пути из s в t совпадает с максимальным значением φ(t) − φ ...
2
голоса
0
ответов
118 показов
Число путей между вершинами графа
Пусть задан простой ориентированный граф G(V, E) и s, t ∈ V . Обозначим через α длину минимального пути из s в t. Покажите, что максимальное число пут ...
1
голос
1
ответ
298 показов
"Хроматическое число"
Есть двудольный граф с долями по 300 и 500 вершин. Нужно найти минимальное число цветов, в которые можно покрасить ребра и вершины таким образом, чтоб ...
1
голос
1
ответ
176 показов
Число неизоморфных деревьев
Доказать, что число попарно неизоморфных деревьев на n вершинах не менее 2^n для больших n.
0
голосов
0
ответов
121 показ
Теорема Ньюмана
Хотелось бы узнать применение этой теоремы в комбинаторике или Diamond lemma.
0
голосов
1
ответ
197 показов
Расстояние между путями в ориентированном графе
Пусть дан ориентированный граф (достаточно общий, могут быть циклы и петли, например) и два пути в нем (последовательность вершин и ребер, их соединяю ...
3
голоса
1
ответ
207 показов
Задача на графы
Есть 100 городов, часть из них соединенных авиалиниями. Доказать, что среди них есть 2 города, для которых существует не менее 50 городов, каждый из к ...
161 вопрос
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.