цикл, и, соответственно, такой граф именуется эйлеровым.... Если в составе графа существует цепь, которая содержит каждую вершину один раз, то эта цепь считается... эйлеровойцепью, а граф называется полуэйлеровым.... эйлеровыми графами.... Цепью Гамильтона в графе считается простая цепь, проходящая через каждую вершину графа строго по одному
В статье рассматриваются оценки количества цепей в эйлеровом ОЕ-покрытии плоского графа цепями. Под эйлеровым ОЕ-покрытием понимается такое минимальное по мощности упорядоченное множество реберно-непересекающихся цепей, для которых выполнено условие отсутствия пересечения внутренности цикла из ребер пройденной части маршрута с ребрами непройденной части.В соответствии с теоремой Листинга-Люка минимальная мощность покрытия графа реберно-непересекающимися цепями равна k, где 2 k число вершин нечетной степени. Ранее автором показано, что мощность эйлерова OE-покрытия плоского графа без мостов равна k, если хотя бы одна вершина нечетной степени инцидентна внешней грани и k +1, в противном случае. В данной работе показано, что точная верхняя оценка мощности эйлерова ОЕ-покрытия равна 2 k.
В статье рассматривается рекурсивный алгоритм построения эйлеровой цепи в плоском эйлеровом графе, удовлетворяющей глобальному ограничению на порядок обхода ребер. Такой граф и соответствующий ему маршрут могут быть рассмотрены как математическая модель некоторого раскройного плана. Наложенное ограничение на порядок обхода ребер означает, что отрезанная от листа часть не требует дополнительных разрезаний.
способ определения множества, при котором задаются некоторые элементы определяемого множества и некоторые правила, позволяющие из имеющихся получать другие элементы этого множества; в частном случае определение понятия P (n), зависящего от натурального параметра n, протекает по следующей схеме: задаются P (0) и правило получения P (n + 1) от n и P (n); напр., факториал n! определяется так: 0! = 1, (n + 1)! = (n + 1) · n!