On exact extensions of tournaments.pdf Ориентированным графом называется пара G = (V, а), где V - конечное непустоемножество, называемое множеством вершин, а а - отношение на множествевершин V , называемое отношением смежности.Граф с антисимметричным отношением смежности называется направленным графом,или диграфом. Полный диграф без петель называется турниром.Граф H называется точным k -расширением графа G, если G изоморфен каждомуподграфу H , получающемуся путем удаления любых его k вершин.Первое из известных семейств точных расширений турниров - семейство транзитивныхтурниров - было описано в работе [1]. Транзитивный турнир - это турнир,у которого из существования дуг (u,v) и (v,w) вытекает существование дуги (u,w).В работе показано, что точным k-расширением турнира Tn при n > 2 является транзитивныйтурнир Tn+fc.В работе [2] рассматривается схема построения семейства вершинно-симметрическихтурниров. Оказывается, что графы этого семейства обладают циклической симметрией.Удалось показать, что любой циклически-симметричный граф является точным1-расширением. Семейство, описанное в [2], не является единственным семействомтурниров с циклической симметрией. В докладе представляется схема, позволяющаяпостроить все графы с заданным числом вершин, обладающие циклической симметрией.Также указывается необходимая модификация алгоритма, позволяющая получитьс его помощью только циклически-симметричные турниры.Рассмотрим операцию над парой графов G1 и G2, назовем ее операцией вершиннойподстановки графа G1 в граф G2.Результатом вершинной подстановки графа G1 = (У1,а 1) в G2 = ( ^ , а 2), где|V1| = n1, |V2| = n2, будет граф G = (V, а), такой, что:1) V = {vj|i = 1,n1, j = 1, П2}, |V| = П1 х П2;2) (vj,k, Vj,t) Е а, если k = t и (v, vj) Е а 1 или если k = t и (vk, vt) Е а 2.Удалось доказать, что граф, получающийся в результате вершинной подстановкитранзитивного турнира в циклически-симметричный турнир, является точным1-расширением, отличным от графов, принадлежащих описанным семействам.

Скачать электронную версию публикации