1
голос
1
ответ
89 показов

Дан связный граф на 2016 вершин. За одну операцию можно выбрать две вершины на максимальном (по количеству ребер) расстоянии и соединить ребром. Может ...
0
голосов
0
ответов
55 показов

Дан связный граф на n вершинах, у которого степень любой вершины равна 1010.Доказать, что при удалении меньше чем 1010 ребер, граф не потеряет связнос ...
0
голосов
1
ответ
34 показа

Какой хроматический многочлен у графа квадратик?
0
голосов
0
ответов
41 показ

Рассмотрим простой ориентированный граф G = (V, E). Пусть длина кратчайшего пути между вершинами v и u равна L. Докажите, что количество реберно непер ...
1
голос
1
ответ
71 показ

Есть подграф H графа G(n,n,1/2). И из подграфа H (выбор осуществляется равновероятно) удаляется 90% всех его ребер. С какой предельной вероятностью по ...
1
голос
0
ответов
72 показа

Пусть задан ориентированный граф G(V, E) и s, t ∈ V . Покажите, чтоминимальное число ребер в пути из s в t совпадает с максимальным значением φ(t) − φ ...
1
голос
1
ответ
73 показа

Пусть {1,...,n} - фиксированное множество натуральных чисел, а G(n,1/2) - случайный граф на этом множестве вершин. Пусть Xk - число треугольников, сре ...
0
голосов
0
ответов
56 показов

Найдите вероятность того, что жадное хроматическое число графа на 4 вершинах и 3 ребрах равно 2.Жадный алгоритм раскраски графа заключается в следующе ...
0
голосов
1
ответ
53 показа

Найдите дисперсию изолированных вершин в случайном графе G(n,p)G(n,p) - граф на n вершинах с вероятностью проведения ребра p.
0
голосов
1
ответ
59 показов

Сколько существует способов построить две древесные компоненты на 6 вершинах?Мы знаем формулу Кэли, что на n вершинах можно построить n^(n-2) различны ...
1
голос
1
ответ
59 показов

Докажите, что при любой раскраске рёбер полного графа в два цвета в нём найдётся гамильтонов цикл, состоящий из двух одноцветных путей (цвета путей мо ...
0
голосов
1
ответ
55 показов

Триангуляция - это граф, в укладке которого на плоскость каждая грань ограничена треугольником.Есть теорема, что любая триангуляция (на более чем трех ...
0
голосов
0
ответов
58 показов

Сколько всего простых циклов длины 5 в полном графе на 10 вершинах?
0
голосов
0
ответов
33 показа

Докажите, что списочное хроматическое число цикла на чётном числе вершин равно двум.Правильная раскраска графа - это раскраска вершин графа таким обра ...
1
голос
1
ответ
75 показов

Правильная раскраска графа - это раскраска вершин графа таким образом, чтобы концы любого ребра были раскрашены в разные цвета.Список - сопоставление ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru