graph

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

Авторы: Григорьева Е. Г., Клячин В. А.

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

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

Авторы: Фарахутдинов Р. А., Молчанов В. А.

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

О РЕКОНСТРУИРУЕМОСТИ МАЛЫХ ТУРНИРОВ

Авторы: Абросимов М. Б., Долгов А. А.

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

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

Авторы: Осипов Д. Ю.

Рассматривается один из способов построения оптимального расширения графа — Т-неприводимое расширение (ТНР). До сих пор остается нерешенной следующая задача: построить одно из ТНР для произвольного сверхстройного дерева. Данная задача была решена С. Г. Курносовой для подкласса сверхстройных деревьев –- пальм. Для несложных сверхстройных деревьев данная задача была решена М. Б. Абросимовым. Приводится контрпример для схемы из статьи Харари и Хурума «One node fault tolerance for caterpillars and starlike trees», которая описывает построение одного ТНР для произвольного сверхстройного дерева.

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

Авторы: Осипов Д. Ю.

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