Связный граф, в котором n вершин и n-1 ребро, носит название
Подмножество вершин графа, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством, носит название
Каково количество компонент связности в остовном дереве графа, если в графе их n?
Пусть p - число вершин в данном графе. Если степень каждой вершины не меньше, чем p/2, то граф является
Если d - максимальная высота дерева леса, n - количество вершин, то общие затраты многопроцессорного алгоритма определения корня для вершины двоичного леса составляют
Необходимым и достаточным условием для существования клики размера k является наличие независимого множества в дополнении графа, размера не менее
Путь, содержащий каждую вершину графа ровно один раз, носит название
Если классы P и NP равны, то любую задачу из класса NP можно будет решить
Ациклический подграф данного графа, в который входят все вершины данного графа, носит название
Если задача П1 сводится по Тьюрингу к задаче П2 из класса NP, то задача П1 является