Известия Саратовского университета. Новая серия.
ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


граф

О конкретной характеризации универсальных графовых полуавтоматов

Теория автоматов является одним из разделов математической кибернетики, в котором изучаются устройства преобразования информации, используемые во многих прикладных задачах. В данной работе мы изучаем автоматы без выходных сигналов и называем их полуавтоматами. В зависимости от исследуемых задач рассматриваются полуавтоматы, у которых множества состояний наделены дополнительной математической структурой, согласованной с функцией переходов полуавтомата.

Построение цветных графов без проверки на изоморфизм

В работе рассматриваются графы, вершины или ребра которых раскрашены в заданное количество цветов — вершинные и реберные раскраски. Изучение раскрасок графов началось с середины XIX в., однако основное внимание уделяется правильным раскраскам, в которых накладывается ограничение, что цвета смежных вершин или ребер должны быть различными. В данной работе рассматриваются раскраски графов без каких-либо ограничений. Исследуется задача генерации всех неизоморфных вершинных и реберных k-раскрасок заданного графа без непосредственной проверки на изоморфизм.

Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1-расширения

: Граф G∗ называется вершинным 1-расширением графа G, если граф G можно вложить в каждый граф, получающийся из графа G∗ удалением любой его вершины вместе с инцидентными ребрами. Вершинное 1-расширение G∗графа G называется минимальным, если граф G∗ имеет на одну вершину больше, чем граф G, а среди всех вершинных 1-расширений графа G с тем же числом вершин граф G∗ имеет минимальное число ребер.

Т-неприводимое расширение для объединения цепей и циклов

Расширением n-вершинного графа G называется граф H с n+1 вершинами такой, что граф G вкладывается в каждый максимальный подграф графа H. Тривиальное расширение графа G – соединение графа G с одноэлементным графом (т.е. к графу G добавляется вершина, которая соединяется ребром с каждой вершиной графа G).

Об использовании матрицы потоков при решении краевых задач на графе

В работе дан конструктивный метод решения основныхкраевых задач для системы неоднородных дифференциальных уравнений на графе, удобный для использования ЭВМ. Система уравнений и условия согласования в вершинах выбраны, имея в виду приложение метода к теории переноса и другим проблемам неравновесной термодинамики.  

Т-неприводимые расширения для сверхстройных деревьев

Рассматривается один из способов построения оптимального расширения графа — Т-неприводимое расширение (ТНР). До сих пор остается нерешенной следующая задача: построить одно из ТНР для произвольного сверхстройного дерева. Данная задача была решена С. Г. Курносовой для подкласса сверхстройных деревьев –- пальм. Для несложных сверхстройных деревьев данная задача была решена М. Б. Абросимовым.

О реконструируемости малых турниров

В работе рассматриваются вопросы, связанные с реконструируемостью турниров. Приводятся известные результаты по реконструируемости ориентированных графов и описывается схема построения семейств Стокмейера нереконструируемых направленных графов. Рассматривается техника компьютерного поиска нереконструируемых турниров и соответствующие алгоритмы. Приводятся все нереконструируемые турниры с числом вершин до 12.  

Об определяемости универсальных графических автоматов своими полугруппами входных сигналов

Универсальный графический автомат Atm(G, G′ ) — это универсально притягивающий объект в категории автоматов, у которых множество состояний наделено структурой графа G и множество выходных сигналов — структурой графа G′ , сохраняющимися функциями переходов и выходов автоматов. Полугруппа входных сигналов такого автомата имеет вид S(G, G′ ) = End G × Hom(G, G′ ). Она может рассматриваться как производная алгебраическая система математического объекта Atm(G, G′ ), которая содержит полезную информацию об исходном объекте.

Исследование статистических характеристик текста на основе графовой модели лингвистического корпуса

Статья посвящена исследованию статистических характеристик текста, которые вычисляются на базе графовой модели представления текста из лингвистического корпуса. Во введении излагается актуальность статистического анализа текстов и приводятся некоторые задачи, решаемые с помощью такого анализа. Предлагаемая в статье графовая модель текста строится как граф, в вершинах которого расположены слова текста, а ребра графа отражают факт попадания двух слов в какую-либо часть текста, например в предложение.