теория-графов

новыебез ответаценныетекущиеизбранныенепринятые
0
голосов
1
ответ
18 показов

Доказать, что число попарно неизоморфных деревьев на n вершинах не менее 2^n для больших n.
0
голосов
0
ответов
37 показов

Хотелось бы узнать применение этой теоремы в комбинаторике или Diamond lemma.
0
голосов
1
ответ
65 показов

Пусть дан ориентированный граф (достаточно общий, могут быть циклы и петли, например) и два пути в нем (последовательность вершин и ребер, их соединяю ...
2
голоса
1
ответ
81 показ

Есть 100 городов, часть из них соединенных авиалиниями. Доказать, что среди них есть 2 города, для которых существует не менее 50 городов, каждый из к ...
0
голосов
0
ответов
36 показов

Для каких чисел m, n граф G является эйлеровым:1) Кn – полный граф с n вершинами?2) Kmn – полный двудольный граф с n, m вершинами?3) Wn – колесо с n в ...
0
голосов
0
ответов
34 показа

Может ли в ориентированном графе полустепень захода каждой вершины быть равна 3, а полустепеньисхода – 4? Ответ обосновать.
1
голос
1
ответ
50 показов

Каково наименьшее число ребер в связном непланарном графе с 9 вершинами, имеющем эйлеров цикл?
0
голосов
0
ответов
46 показов

Какова будет суммарная длина фундаментальных циклов относительно каркаса,построенного с помощью поиска а)в ширину б)в глубину для графа K₃,₄?
0
голосов
0
ответов
58 показов

Алгоритм поиска в глубину применяется к графу Qₖ, заданному списками смежности. Какие оценки трудоёмкости справедливы в этом случае?1)O(k2ᵏ); 2)O(2ᵏ); ...
0
голосов
1
ответ
59 показов

Сколько существует абстрактных деревьев с 7 вершинами, у которых две центральныхвершины и радиус равен 2?Каково наименьшее число ребер в связном непла ...
1
голос
1
ответ
54 показа

Доказать, что если в простом графе (нет петель и кратных ребер) все вершины имеют степень не меньше чем 3, то в этом графе есть цикл длины не меньше ч ...
0
голосов
0
ответов
42 показа

Пусть G - простой граф (без петель и кратных ребер), в котором 6 вершин и 10 ребер. Доказать, что G содержит треугольник
1
голос
1
ответ
59 показов

В связном графе степени четырех вершин равны 3, а степени остальных вершин равны 4. В графе имеется ребро (мостик), после удаления которого граф распа ...
0
голосов
0
ответов
51 показ

Пусть R(m, n) — наименьшее число людей в группе, которое гарантируетналичие m попарно знакомых или n попарно незнакомых. Эти числа определеныпри целых ...
0
голосов
0
ответов
84 показа

Сколько автоморфизмов имеет граф http://priscree.ru/img/38f0df67d1da53.png и почему?
150 вопросов

Связанные метки

12345 ... 10следующий »

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