УДК 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 с.
