Конкатенація та мультиплікація орієнтованих графів спеціального класу

Анотація

На множині орієнтованих графів із рівно одним стоком та рівно одним джерелом розглядаються дві бінарні операції. Конкатенація ототожнює стік першого орграфа з джерелом другого, а мультиплікація замінює всі дуги першого орграфа на другий орграф, ототожнюючи джерело з початком дуги, а стік – із кінцем. Множина досліджуваних графів замкнена відносно цих двох операцій, а сукупність орієнтованих ланцюгів із операціями конкатенації та мультиплікації утворює напівкільце, ізоморфне напівкільцю натуральних чисел. У роботі проаналізовані попередні роботи в галузі орієнтованих графів, і зокрема, результатів, пов’язаних із прикладним застосуванням досліджуваного класу графів як моделей транспортних мереж. Отримані теоретичні результати про властивості нових операцій та описи королів отриманих орграфів дають можливість працювати з цими операціями для подальших досліджень, побудови узагальнень та моделювання більш складних систем для прикладних задач.