2014 УДК 510.8 О МУЛЬТИОРГРАФАХ С
ИДЕНТИЧНЫМИ АВТОМОРФИЗМАМИ И ОБЛАСТЯМИ ДОСТИЖИМОСТИ А.Г.
Пинус Новосибирский государственный технический университет Работа посвящена
вопросам взаимосвязи графов с
идентичными производными
объектами: автоморфизмами,
эндоморфизмами, областями достижимости. <...> Но
основе результатов автора в
теории моделей и
универсальной алгебре, в том числе доказанного им аналога (для
позитивных формул) теоремы Скотта о
категоричности теорий счетных моделей в
языке логики со
счетными конъюнкциями и дизъюнкциями, на
языке логики с бесконечно
длинными формулами и
языке узкого исчисления предикатов, дается описание пар мультиорграфов с
раскрашенными дугами и общим
множеством вершин, имеющих одни и те же автоморфизмы и области достижимости (одни и те же
эндоморфизмы на себя и области достижимости). <...> Введение Изучение
автоморфизмов математических объектов – одно из основных эффективных средств изучения строения этих объектов и их классификаций. <...> В связи с этим представляется вполне естественным
вопрос о
взаимосвязи графов (мультиорграфов) с общим
множеством вершин, имеющих
идентичные совокупности
автоморфизмов. <...> Подобные вопросы для
универсальных алгебр рассматривались автором в работах [1] [2]− . <...> Под мультиорграфом традиционно будем иметь в виду тройку
множеств<>, V ,ES , где непустое
множество V (вершин графа) и
множество E (его дуг) дизъюнктны, а S – некоторое подмножество
множества VE eE 2 Ч со свойством: для любого дит из вершины a в вершину b ). <...> Мультиорграф ,,V E S abe c ,, 1 ,, 2 ∈ существуют единственные ,ab V∈ такие, что ,,<abe S>∈ (
дуга e исхо<> имеет
раскраску дуг без
кратных равно раскрашенных
дуг, если для некоторого множества C (цвета
дуг графа) существует отображение g (
функция раскраски) из E в C и при этом для любых ,ab V∈ , если<>, <abe S>∈ , то 12ge ge≠() ( ) . <...> Стандартным образом по любому мультиорграфу с раскрашенными дугами без =< ,, ,, строится
модель M = < ∈>
сигнатуры состоящей из двухместных
предикатов <...>