УДК 519.17
ПРЕДСТАВЛЕНИЕ ФРАГМЕНТАРНЫХ СТРУКТУР ОРИЕНТИРОВАННЫМИ ГРАФАМИ
Аннотация. Исследованы свойства фрагментарных структур и установлена связь между фрагментарными структурами и размеченными ациклическими ориентированными графами с одним источником, также установлено соответствие классов изоморфных фрагментарных структур неразмеченным ациклическим ориентированным графам определенного вида, которые называются допустимыми графами. Определено понятие размерности допустимого графа и соответствующих ему изоморфных фрагментарных структур. Получено выражение для нижней оценки размерности. Доказана теорема о свойствах допустимых графов. Подсчитано количество фрагментарных структур и классов изоморфных фрагментарных структур малых размерностей.
Ключевые слова: фрагментарная структура, частично упорядоченное множество, ациклический орграф, гиперкуб.
ПОЛНЫЙ ТЕКСТ
Кривцун Олена Володимирівна,
кандидат фіз.-мат. наук, доцент кафедри Запорізького національного технічного університету,
kryvtsun@ukr.net
СПИСОК ЛИТЕРАТУРЫ
- Whitney H. On the abstract properties of linear dependence. American Journal of Mathematics. 1935. Vol. 57, N 3. P. 509–533.
- Bjorner A., Ziegler G. M. Introduction to greedoids. Cambridge: Cambridge University Press: Matroid Applications, 1992. 180 р.
- Ильев В.П. Задачи на системах независимости, разрешимые жадным алгоритмом. Дискретная математика. 2009. Т. 21, вып. 4. С. 85–94.
- Козин И.В., Кривцун Е.В., Пинчук В.П. Эволюционно-фрагментарная модель задачи трассировки. Кибернетика и системный анализ. 2015. Т. 51, № 3. С. 125–131.
- Козин И.В., Кривцун Е.В., Полюга С.И. Фрагментарная структура и эволюционный алгоритм для задач прямоугольного раскроя. Вісник Запорізького національного університету. Сер. Фізико-математичні науки. 2014. № 2. С. 65–72.
- Козин И.В., Кривцун Е.В. Моделирование однослойных и двухслойных трассировок. Управляющие системы и машины. 2016. № 2. С. 58–64.
- Козін І.В., Борю С.Ю., Кривцун О.В. Математична модель пакування в контейнери різних типів. Вісник Запорізького національного університету. Сер. Економічні науки. 2016. № 2. С. 85–92.
- Кривцун Е.В. Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом. Управляющие системы и машины. 2016. № 5. С. 25–31.
- Козин И.В., Полюга С.И. О свойствах фрагментарных структур. Вісник Запорізького національного університету. Сер. Фізико-математичні науки. 2012. № 1. С. 99–106.
- Полюга С.І. Фрагментарні оптимізаційні моделі в задачах покриття графів типовими підграфами: дис. … канд. фіз.-мат. наук. Запоріжжя, 2015. 140 с. URL: http://phd.znu.edu.ua/page/dis/ 06_2016/Polyuga_dis.pdf.
- Берж К. Теория графов и ее применения. Москва: Изд-во иностранной лит., 1962. 320 с.
- Харари Ф., Палмер Э. Перечисление графов. Москва: Мир, 1977. 324 с.
