Cтраница 1
Минимальный граф может быть получен и без применения довольно громоздкой операции возведения в степень. Алгоритм, который мы сейчас приведем, позволяет находить минимальный граф вручную, если исходный граф нильпотентен. [1]
Если минимальный граф содержит зацепляющиеся циклы, то соответствующая мономиальная алгебра не будет представимой. Таким образом, ядро представления может содержать не слова, а только их линейные комбинации. Получение информации об этом ядре ( в частности, в каком Т - идеале оно содержится) представляется интересным. Интересно также знать, когда каноническое представление графа дает точное представление его полугруппы слов. [2]
Если минимальный граф С, содержит минимальный подграф Cn. Доказательство для случаев / 33, 34 проводится аналогично. [3]
Структура минимального графа не изменилась ( см. табл. 13), лишь две вершины ( 13 и 14) оказались вычеркнутыми вместе с инцидентными им дугами. Автомат ( вершинаШ минимального графа) состоит из 4, 8 и 9 вершин. [4]
Прежде чем отыскивать минимальный граф, стянем все вершины, принадлежащие автомату, в одну. [5]
Нетрудно выяснить, для каких n - минимальных графов здесь выполняется равенство. [6]
Но тогда Я не может быть подграфом такого n - минимального графа G, для которого G Я, так как для каждой компоненты С графа G - Е ( Н) множество вершин N ( C G) содержит по меньшей мере две вершины степени п в Я. [7]
Чтобы определить S ( г, Q), необходимо представить i - ю цепь в виде помеченного графа ( из физических соображений следует, что это будет полный граф), принимая за вершины контакты этой цепи, и решить задачу выделения минимального графа, связывающего все вершины дерева-остова. Каждому ребру полного графа ставится в соответствие расстояние ( на плате) между инцидентными ему вершинами при данном размещении. Задача эта с учетом числа вершин искомого остова и ограничений на их локальные степени не имеет эффективного алгоритма точного решения. Обсуждение этой проблемы не входит в нашу задачу. [8]
Структура минимального графа не изменилась ( см. табл. 13), лишь две вершины ( 13 и 14) оказались вычеркнутыми вместе с инцидентными им дугами. Автомат ( вершинаШ минимального графа) состоит из 4, 8 и 9 вершин. [9]
Минимальный граф может быть получен и без применения довольно громоздкой операции возведения в степень. Алгоритм, который мы сейчас приведем, позволяет находить минимальный граф вручную, если исходный граф нильпотентен. [10]
Множество вершин, не входящих ни в один автомат, образуют прямые структуры. В случае если граф связей содержит автоматы, для получения минимального графа в исходном графе к каждому автомату применяется операция стягивания всех вершин в одну. [11]
Алгоритм проверки, является ли элемент делителем нуля. Обозначим deg у - щ в дальнейших рассуждениях п будет фиксировано. Пусть минимальный граф Г ( Л) алгебры А имеет т вершин. [12]
Данная глава посвящена представлениям мономиальных алгебр. Мы рассматриваем ручные и дикие мономиальные алгебры, т.е. алгебры, все представления которых поддаются или не поддаются описанию. Ручными мономиальными алгебрами оказываются только 1-порожденные алгебры и 2-порожденные алгебры с нулевым умножением. Если же минимальный граф алгебры содержит зацепляющиеся циклы ( что то же самое, алгебра имеет экспоненциальный рост), то задача описания неприводимых представлений является дикой. [13]
Если мы хотим доказать, что некий двудольный граф является элементарным, то, очевидно, это достаточно установить для его остов-ного минимального элементарного подграфа. Приводимые ниже результаты показывают, что минимальный элементарный двудольный граф должен быть малым в разных смыслах графом. Одна из мер малости отражает тот факт, что минимальный граф не может содержать подграфы определенного вида. Мы представим один такой результат. [14]
Сложность для нас может оказаться гораздо более высокой: мы обычно не умеем построить граф с минимальным числом вершин. Если мы испробовали все графы с числом внутренних вершин, меньшим чем т и ни один из них не соответствует заданной функции и если соответствующий граф с т вершинами найдется, он и будет минимальным графом, а число т - сложностью функции. [15]