Ответы к контрольной работе: Графы и алгоритмы

Что происходит с диаметром графа при удалении вершины?

Сколько имеется неориентированных графов, в которых допускаются петли, но не кратные ребра, с множеством вершин {1, 2, 3}?

Сколько существует абстрактных связных графов с 5 вершинами, имеющих ровно два блока?

Корневое дерево имеет радиус 4, а у каждой его вершины не более двух сыновей. Каково наибольшее число вершин в таком дереве?

Сколько имеется связных абстрактных графов с 5 вершинами, в которых существует эйлеров цикл?

В графе с 10 вершинами вес каждого ребра равен 1 или 2, причем ребра веса 2 порождают остовный подграф с тремя компонентами связности. Чему равен вес оптимального каркаса для этого графа?

Сколько имеется абстрактных графов с 4 вершинами, у которых центр состоит ровно из 2 вершин?

Сколько максимальных независимых множеств имеется у графа P5?

Сколько имеется абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?

Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?

В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?

Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?

Какие из следующих операций сохраняют свойство хордальности, т. е. при применении операции к хордальному графу всегда получается хордальный граф?

Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?

Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K3,5?

Сколько имеется абстрактных графов с 4 вершинами диаметра 2?

В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?

Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?

Сколько имеется абстрактных обыкновенных графов с набором степеней (2, 2, 4, 4, 5, 5)?

Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?

Сколько имеется абстрактных двусвязных графов с 4 вершинами?

Что происходит с диаметром графа при удалении ребра?

Сколько имеется абстрактных графов с 5 вершинами, не являющихся хордальными?

Как может измениться цикломатическое число при добавлении к графу нового ребра?

Сколько имеется абстрактных деревьев с 6 вершинами?

В каких из следующих случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?

Сколько ребер имеет граф пересечений граней трехмерного куба?

Чему равно число независимости графа Q3?

Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?

Что происходит с хроматическим числом графа при удалении ребра?

В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?

В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?

Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?

В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?

Чему равны хроматические индексы графов K3,3 и C7 ?

К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?

Сколько листьев будет в дереве путей, построенном для графа K4,4?

Какое наименьшее число ребер нужно добавить к графу K3,5, чтобы получился граф, в котором есть эйлеров цикл?

Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K3?

Чему равно кликовое число графа C9?

Какие из следующих утверждений справедливы для любого двусвязного графа?

Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа K7 ?

Какие из следующих утверждений верны для системы фундаментальных циклов, построенной относительно некоторого каркаса?

В планарном графе семь вершин, из которых три имеют степень 4, остальные степень 5. Сколько граней будет в плоском изображении этого графа?

В двудольном графе одна доля состоит из пяти вершин степени 2, а другая из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?

Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?

Сколько имеется абстрактных двудольных графов с 4 вершинами?

Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого дерева?

Что происходит с радиусом графа при добавлении нового ребра?

Сколько имеется абстрактных графов с 4 вершинами радиуса 1?

Сколько имеется абстрактных обыкновенных графов с 5 вершинами и 3 ребрами?

Сколько имеется ориентированных графов без петель и кратных ребер с множеством вершин {1, 2, 3}?

Какое наименьшее количество новых ребер нужно добавить к графу C6, чтобы получился непланарный граф?

Какие из следующих утверждений верны для любого взвешенного графа?

Какое наименьшее число ребер нужно добавить к графу K3,3, чтобы превратить его в хордальный?

Какое наименьшее число ребер нужно удалить из графа K8 , чтобы получился граф, в котором есть эйлеров цикл?

Что произойдет, если алгоритм СПО применить к матроиду, на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса).

BC-дерево некоторого графа имеет радиус 2 и содержит 8 вершин, 4 из которых являются листьями. Сколько шарниров у этого графа?

Какое из следующих утверждений верно?

Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?

В связном взвешенном графе для каждой вершины выбрано одно инцидентное ей ребро наибольшего веса. Какие из следующих утверждений верны?

Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 4, 4, 5, 5)?

Сколько имеется связных абстрактных графов с 4 вершинами?

Какие из следующих утверждений верны?

В графе K5 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?

В процессе выполнения процедуры поиска в ширину вершины графа делятся на новые, открытые и закрытые. Может ли в графе существовать ребро, соединяющее