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

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

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

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

Для некоторого графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

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

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

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

Сколько ребер нужно добавить к наибольшему паросочетанию графа , чтобы получить наименьшее реберное покрытие этого графа?

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