The sperner property for polygonal graphs.pdf Пусть (A, - конечное упорядоченное множество. Высота h(a) элемента а в (A, определяется как максимальная из длин убывающих цепей, начинающихся с а. Антицепь в упорядоченном множестве - это такое его подмножество, в котором любые два элемента несравнимы. Под длиной антицепи понимается количество элементов в ней. Антицепи максимальной длины будем называть главными. Антицепь в конечном упорядоченном множестве называется правильной, если все её элементы имеют одинаковую высоту. Так, в упорядоченном множестве (Ng, |) (первые 8 натуральных чисел с отношением делимости) среди главных антицепей {2, 3, 5, 7}, {3, 4, 5, 7}, {3,5, 7, 8} правильной является только первая. В (P({а,Ь,с}), С) (совокупность всех подмножеств трёхэлементного множества с отношением включения) главных антицепей две: {а,Ь,с} и {аЬ, ас, Ьс}, и обе они - правильные. Конечное упорядоченное множество назовём шпернеровым, если среди его главных антицепей есть по крайней мере одна правильная. Упорядоченные множества (Ng, |) и (P({a, b, с}), С) являются шпернеровыми. Один из минимальных примеров упорядоченного множества, не обладающего свойством шпернеровости, образуют по включению пять подмножеств множества S = {а, Ь, с, d}, а именно {а}, {Ь}, {Ь,с}, {b,d}, {а,Ь,с}. В нём всего одна главная антицепь - {а, Ьс, bd}, и она не является правильной. В 1928 г. Шпернер [1] доказал, что все конечные упорядоченные множества вида (P(S), С) обладают обнаруженным им свойством. Свойство шпернеровости для конечных упорядоченных множеств находит содержательные интерпретации в различных разделах математики (см., например, [2-4]), в том числе и в теории графов [5,6]. Под (ориентированным) графом понимается пара G = (V, а), где V - конечное непустое множество и а С V х V - отношение на нём. Элементы множества V называются вершинами графа, а пары, входящие в а, - его дугами. Вершины u и v, по определению, связаны, если существуют v1, v2,... , Vk £ V, такие, что (u, v1) £ a U а-1, (v1, v2) £ а U а-1, ..., (vk, v) £ а U а-1, т. е. если u и v можно соединить последовательностью дуг без учёта их направлений. Граф, в котором любые две вершины связаны, называется связным. Граф H = (U, в) называется частью графа G = (V, а), если U С V и в С а, т. е. H состоит из некоторых вершин графа G и некоторых дуг, соединяющих в G эти вершины. Контур длины k ^ 2 в графе G определяется как последовательность Ck его дуг вида (v1, v2), (v2, v3),... , (vk-1 ,vk), (vk, v1), в которой все встречающиеся вершины различны. Граф, не содержащий контуров, называется бесконтурным. Вершина v, по определению, достижима в графе G из вершины u, если существует последовательность примыкающих дуг (u, v1), (v1, v2),... , (vk, v), соединяющая u с v. Отношение достижимости в графе обозначим через В бесконтурном графе отношение достижимости является отношением порядка (о бесконтурных графах см. [7]). Очевидно, что минимальными элементами в упорядоченном множестве (V, $) являются стоки графа G, т. е. те его вершины, из которых не исходит ни одна дуга в другие вершины. Максимальными элементами в (V,$) являются источники графа G, т.е. те его вершины, в которые не входит ни одна дуга из других вершин. Связный бесконтурный граф G = (V, а) назовём шпернеровым, если упорядоченное множество (V, $) обладает шпернеровым свойством. Пусть n ^ 2 - натуральное число. Под n-угольным графом будем понимать всякий граф, полученный из контура Cn переориентацией некоторого количества k его дуг. Будем считать, что 1 ^ k < n. Следовательно, контуры исключаются из числа многоугольных графов, которые, таким образом, попадают в класс связных бесконтурных графов [8]. Для шестиугольного графа M' : v1 ^ v2 ^ v3 ^ v4 ^ v5 ^ v6 ^ v1 ^-упорядочен-ное множество его вершин содержит одну главную антицепь - {2, 4,6}. Она является правильной, так что M' - шпернеров граф. Аналогично, для шестиугольного графа M" : v* ^ v2 ^ v3 ^ v4 ^ v5 ^ v6 ^ v* 8-упорядоченное множество вершин содержит тоже единственную главную антицепь - {2, 4, 6}, но здесь она не является правильной, так что M" - не шпернеров граф. Под цепью в многоугольном графе будем понимать его максимальную собственную связную часть, в которой 1) есть хотя бы одна вершина, не являющаяся ни источником, ни стоком, и 2) любые две соседние дуги одинаково направлены. Например, цепями в графе M' являются v* ^ v2 ^ v3 и v* ^ v6 ^ v5, а в графе M" - v* ^ v2 ^ v3 и v5 ^ v4 ^ v3. Всякая цепь начинается в источнике и завершается стоком. Зигзагом в многоугольном графе назовём его максимальную собственную связную часть, в которой 1) каждая вершина является источником или стоком и 2) любые две соседние дуги противоположно направлены. Зигзаги классифицируются по виду их концевых вершин: в ss-зигзаге оба конца являются источниками; в st-зигзаге один конец источник, другой сток; в tt-зигзаге оба конца стоки. Так, в графе M' есть tt-зигзаг v3 ^ v4 ^ v5, а в графе M" имеется ss-зигзаг v* ^ v6 ^ v5. Теорема. Многоугольный граф тогда и только тогда является шпернеровым, когда в нём нет ss-зигзагов.

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