Граф является гамильтоновым тогда и только тогда, когда его замыкание представляет собой
Формальный язык, для которого существует машина Тьюринга, которая останавливается на любой входной цепочке и допускает ее тогда и только тогда, когда она принадлежит языку, является
Поток максимален тогда и только тогда, когда в остаточной сети нет
Граф с n вершинами имеет вершинное покрытие размера k тогда и только тогда, когда данный граф имеет независимый набор размера
Число входящих в вершинное покрытие вершин является его
Глубина вершин двоичного дерева, у которых непосредственным предком является корень, составляет
Пусть p - число вершин в данном графе. Если степень каждой вершины не меньше, чем p/2, то граф является
Если в графе степени любых двух несмежных вершин не меньше общего числа вершин в графе, то такой граф считается
Подмножество вершин графа, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством, носит название
Множество вершин S графа такое, что у каждого ребра графа хотя бы один из концов входит в S, носит название
