0
голосов
1
ответ
36 показов
Комбинаторная головоломка
В большую коробку положили k коробок поменьше. В некоторые из них положили k коробок ещё поменьше. В некоторые из этих последних коробок положили k ко ...
0
голосов
0
ответов
40 показов
Как представить грамматику типа 0 или 1 в виде графа?
Как это сделать? Типа 2 и 3 легко представляются в виде графа, где вершина - Нетерминал, а ребро - Терминал.Если нельзя - то какие есть другие способы ...
1
голос
1
ответ
89 показов
Доказать тождество из теории графов
Здравствуйте! Помогите, пожалуйста, доказать тождество, будьте добры$$\sum_{i=1}^{n-1}\binom{n}{i}i^{n-i-1} (n-i)^{i-1} = 2 n^{n-2}$$
1
голос
0
ответов
72 показа
Минимальное число ребер в пути
Пусть задан ориентированный граф G(V, E) и s, t ∈ V . Покажите, чтоминимальное число ребер в пути из s в t совпадает с максимальным значением φ(t) − φ ...
2
голоса
0
ответов
72 показа
Число путей между вершинами графа
Пусть задан простой ориентированный граф G(V, E) и s, t ∈ V . Обозначим через α длину минимального пути из s в t. Покажите, что максимальное число пут ...
1
голос
1
ответ
242 показа
"Хроматическое число"
Есть двудольный граф с долями по 300 и 500 вершин. Нужно найти минимальное число цветов, в которые можно покрасить ребра и вершины таким образом, чтоб ...
1
голос
1
ответ
86 показов
Число неизоморфных деревьев
Доказать, что число попарно неизоморфных деревьев на n вершинах не менее 2^n для больших n.
0
голосов
0
ответов
76 показов
Теорема Ньюмана
Хотелось бы узнать применение этой теоремы в комбинаторике или Diamond lemma.
0
голосов
1
ответ
130 показов
Расстояние между путями в ориентированном графе
Пусть дан ориентированный граф (достаточно общий, могут быть циклы и петли, например) и два пути в нем (последовательность вершин и ребер, их соединяю ...
3
голоса
1
ответ
166 показов
Задача на графы
Есть 100 городов, часть из них соединенных авиалиниями. Доказать, что среди них есть 2 города, для которых существует не менее 50 городов, каждый из к ...
0
голосов
0
ответов
78 показов
Эйлеровы и гамильтоновы графы
Для каких чисел m, n граф G является эйлеровым:1) Кn – полный граф с n вершинами?2) Kmn – полный двудольный граф с n, m вершинами?3) Wn – колесо с n в ...
0
голосов
0
ответов
68 показов
Теория графов
Может ли в ориентированном графе полустепень захода каждой вершины быть равна 3, а полустепеньисхода – 4? Ответ обосновать.
1
голос
1
ответ
77 показов
Каково наименьшее число ребер в связном непланарном графе?
Каково наименьшее число ребер в связном непланарном графе с 9 вершинами, имеющем эйлеров цикл?
0
голосов
0
ответов
58 показов
Суммарная длина фундаментальных циклов относительно каркаса.
Какова будет суммарная длина фундаментальных циклов относительно каркаса,построенного с помощью поиска а)в ширину б)в глубину для графа K₃,₄?
0
голосов
0
ответов
97 показов
Теория графов. Оценка трудоёмкости алгоритмов
Алгоритм поиска в глубину применяется к графу Qₖ, заданному списками смежности. Какие оценки трудоёмкости справедливы в этом случае?1)O(k2ᵏ); 2)O(2ᵏ); ...
156 вопросов
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.