bilety TG

____________________________________________________________________________
1.Сколько имеется абстрактных деревьев с 7 вершинами, у которых одна центральная вершина, а радиус не больше 2? (9 или 6)
2.Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа К7 ? (45)
3.В полном графе с 13 вершинами существует гамильтонов цикл, все ребра которого имеют вес 2. Имеется ещё клика из четырёх вершин, все ребра между которыми имеют вес 1. Все остальные ребра графа имеют вес 3. Каков будет вес оптимального каркаса для этого графа? (21)
4.Сколько наименьших вершинных покрытий имеется у графа Р10? (3)
5.Алгоритм поиска в глубину применяется к лесу, заданному матрицей смежности. Какие оценки трудоёмкости справедливы в этом случае? (4)
6. Какие из следующих утверждений верны?
1)При удалении любого ребра диаметр графа не увеличивается?
2)При удалении любого ребра диаметр графа не уменьшается?
3)При удалении любой вершины диаметр графа не увеличивается?
4)При удалении любой вершины диаметр графа не уменьшается?
1.В графе 7 вершин. Сколько в нем имеется абстрактных деревьев с диаметром=4? (5)
2.Какова суммарная длина фундаментальных циклов К3,5 при поиске в ширину? (32)
3.В графе К7 есть гамильтонов цикл, вес его ребер равен 2. Вес всех остальных ребёр равен 5. Найти степень корня геодезического дерева? (4)
4.Есть цикл С20 нумерованный(неабстрактный). Сколько в нём наименьших вершинных покрытий? (2)
5.BFS поиск. Лес. Список смежности.
(правильные все 3)
6. Какие из следующих равенств выполняются для любых графов G, H и F с одним и тем же множеством вершин
<<<
<<<
<<



1.Сколько абстрактных деревьев с 7 вершинами с радиусом=2? (8 или 7 как мы решили)
2.В связном графе с 11 вершинами есть гамильтонов цикл с ребрами веса 2, есть два ребра с весом=1, остальные ребра весом=3. Найти вес оптимального каркаса. (18)
3.Найти наибольшее число клик графа дополнительного к С7 ? (7)
4. Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?



<<<
5.Есть K3,3 нумерованный. Сколько в нем DFS-деревьев? (72)
6. Граф планарный. Поиск. Матрица смежности. О(nІ)
1. Сколько существует абстрактных деревьев с 7 вершинами, у которых радиус не превосходит 2? (8)
2. Сколько различных DFS деревьев можно построить для графа С10 ? (20)
3. В полном графе с 10 вершинами вес каждого ребра равен 2 или 3, причем ребра веса 2 образует остовный подграф с четырьмя компонентами связности. Чему равен вес оптимального каркаса для этого графа? (21)
4. Чему равно хроматическое число графа дополнительного к С7 ? (4)
5. Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
1)O(n) 2)O(m)
3)О(m+n) 4)O(mn)
6. Для некоторого графа построено DFS-дерево Т с корнем а. Ребро графа(x,y)дереву не принадлежит. Какие из следующих утверждений могут выполняться (d обозначает расстояние между вершинами в дереве Т)?
1)d(a,x)=d(a,y) 2)|d(a,x)-d(a,y)|=1 3)|d(a,x)-d(a,y)|=2 4)|d(a,x)-d(a,y)|=3
1.Найти число абстрактных деревьев с 7 вершинами, у которых 2 центральных вершины?(4)
2. Граф К3,4 поиском в глубину строится каркас, найти суммарную длину фундаментальных циклов?(28)
3. Граф К5. Найти радиус геодезического дерева, полученного с помощью алгоритма Дейкстра. (1)
4. Найти число максимальных независимых множеств в графе дополнительном к С9?(9)
5. Какие из этих оценок применимы при поиске в ширину для дерева, заданного списком смежности?
1)O(n) 2)O(m) 3)(m+n) 4)O(n2)
6. какие из этих утверждений верны?
1)
·(G1+G2)=
·(G1)+
·(G2) 2)
·(G1+G2)= max(
·(G1),
·(G2))
3)
·(G1oG2)=
·(G1)+
·(G2)
4)
·(G1oG2)= max(
·(G1),
·(G2))
1.граф 7 вершин сколько графов диаметра 3 и диаметра 5? (4)
2. Сколько DFS деревьев можно построить в графе К2,3? (18)
3. В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро (i,j) i 1)5 2)10 3)15 4)20
4.Граф дополнительный к P7, найти хроматичекое число? (4)
5.Т дерево поиском в ширину задана матрицей смежности, найти трудоемкость.
1)O(n) 2)O(m) 3)О(m+n) 4)O(n2)
6. найти верные утверждения:
если Н остовный подграф, то diam(G)<=diam(H)
1.Найти число абстрактных деревьев с 7 вершинами, у которых одна центральная вершина и diam>=4.(6)
2.Сколько BFS деревьев существует для графа С8? (16)
3. У графа К8 некий гамильтонов цикл состоит из ребер веса 2, все остальные ребра имеют вес 5. каков будет вес геодезического дерева построенного по алгоритму Дейкстра?(23)
4.Сколько наибольших паросочетаний в графе P9?(5)
5.оценка трудоемкости для полного графа заданного матрицей смежности
1)O(n) 2)O(m) 3)О(m+n) 4)O(n2)
6. Для двудольного графа построено BFS-дерево с корнем a . Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?
1)d(a,x)=d(a,y) 2)|d(a,x)-d(a,y)|=1 3)|d(a,x)-d(a,y)|=2 4)|d(a,x)-d(a,y)|=3

15

Приложенные файлы

  • doc 24055024
    Размер файла: 56 kB Загрузок: 0

Добавить комментарий