ориентированный граф, для любых двух различных вершин a и b которого найдутся как путь из a в b, так и путь из b в a; ориентированный граф, для любых двух различных вершин a и b которого найдется или путь из a в b, или путь из b в a
Для n-вершинного сильносвязного орграфа оценена длина кратчайшего полного пути и, при наличии петли в графе, экспонент матрицы смежности вершин. Получена полиномиальная оценка субэкспонента системы матриц смежности вершин n-вершинных графов Гй,..., Гс, объединение которых сильно связно. Полученные результаты могут использоваться для исследования существенных переменных координатных функций, определяющих композиции преобразований множества конечных слов.
Сильносвязный орграф называется допустимым, если исходящие степени всех вершин в нём одинаковы и длины циклов взаимно просты в совокупности. Раскраской допустимого графа G назовем произвольный автомат A, граф которого совпадает с G. Слово называется синхронизирующим автомат A, если оно переводит его в одно и то же состояние вне зависимости от исходного состояния автомата A. Оптимальная раскраска допустимого графа -это раскраска с кратчайшим синхронизирующим словом среди всех синхронизирующих раскрасок. Длину соответствующего синхронизирующего слова назовем значением оптимальной раскраски. Доказано, что любой приближенный полиномиальный алгоритм для вычисления оптимальной раскраски или ее значения имеет относительную погрешность не меньше 2 в случае трехбуквенного алфавита при предположении P = NP. Также показано, как результат можно перенести на случай двухбуквенного алфавита.
способ определения множества, при котором задаются некоторые элементы определяемого множества и некоторые правила, позволяющие из имеющихся получать другие элементы этого множества; в частном случае определение понятия P (n), зависящего от натурального параметра n, протекает по следующей схеме: задаются P (0) и правило получения P (n + 1) от n и P (n); напр., факториал n! определяется так: 0! = 1, (n + 1)! = (n + 1) · n!
для любого набора попарно простых чисел m1, m2, ... , mn найдется целое число x, дающее заданные остатки a1, a2, ... , an при делении на m1, m2, ... , mn, т. е. при каждом k x ≡ ak (mod mk)
максимальное число касательных, которые можно провести к данной алгебраической кривой из произвольной точки P плоскости, не лежащей на этой кривой
