RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика // Архив

Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 2006, том 6, выпуск 1-2, страницы 91–95 (Mi isu666)

Эта публикация цитируется в 2 статьях

Информатика

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

М. Р. Мирзаянов

Саратовский государственный университет, кафедра теоретических основ компьютерной безопасности и криптографиии

Аннотация: Пусть $G = (V, \alpha)$ — ориентированный граф. Эквивалентность $\theta\subseteq V\times V$ называется его сильно связной конгруэнцией, если факторграф $G/\theta$ — сильно связный. Описываются минимальные по включению сильно связные конгруэнции ориентированной цепи и подсчитывается их количество: $2^{n-3}$, если цепь имеет $n$ вершин.

УДК: 512.5

DOI: 10.18500/1816-9791-2006-6-1-2-91-95



© МИАН, 2024