Кіріспе
Жазық графтардағы инциденттік қатынастардың реттік өлшемдері
Графтар теориясында Шнайдер теоремасы – жазық графтарды олардың инциденттік позиттерінің реттік өлшемдері тұрғысынан сипаттайды. Бұл теорема 1989 жылы дәлелін жариялаған Уолтер Шнайдердің есімімен аталған. V төбелер және E қабырғалар жиынтығын қамтитын бағытталмаған G графигінің P(G) инциденттік позиті – V ∪ E элементтері бар биіктігі 2-ге тең жартылай реттелген жиынтық. Бұл жартылай реттелуде, x < y реттік қатынасы бар, мұнда x – төбе, y – қабырға, ал x – y қабырғасының екі соңғы нүктесінің бірі. Реттік өлшем – бұл берілген жартылай реттің қиылысы болатын ең кішкентай толық реттелулер саны; мұндай реттелулер жиынтығы жартылай реттің іске асырушысы деп аталады. Шнайдер теоремасына сәйкес, G графигі жазық болады, егер және тек қана P(G) реттік өлшемі үштен аспаса.
In graph theory, Schnyder's theorem is a characterization of planar graphs in terms
of the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in 1989. The incidence poset P(G) of an undirected graph G with vertex set V and edge set E is the partially ordered set of height 2 that has V ∪ E as its elements. In this partial order, there is an order relation x < y when x is a vertex, y is an edge, and x is one of the two endpoints of y. The order dimension of a partial order is the smallest number of total orderings whose intersection is the given partial order; such a set of orderings is called a realizer of the partial order. Schnyder's theorem states that a graph G is planar if and only if the order dimension of P(G) is at most three.
Ұзартулар
Бұл теорема осы авторлар тарапынан конвекс полиэдрдің төбелерінен, қабырғаларынан және жақтарынан немесе жалпы алғанда, енгізілген жазық графтан аналогты түрде құрылған биіктігі үш жартылай реттелген жиынтықтардың өлшемдеріне қатысты тығыз шектемеге дейін жалпыландырылды: екі жағдайда да, жиынтықтың реттік өлшемдері төрттен аспайды. Дегенмен, бұл нәтижені жоғары өлшемді конвекс политоптарға жалпылауға болмайды, себебі беттік торлары шексіз реттік өлшемдерге ие төрт өлшемді политоптар бар. Одан да жалпы алғанда, абстрактілі симплекстік кешендер үшін кешеннің беттік жиынтығының реттік өлшемдері ең көп дегенде 1 + d-ға тең, мұнда d – кешеннің геометриялық іске асырылуын қамтамасыз ететін Евклид кеңістігінің ең төменгі өлшемі.
Басқа графиктер
Шнайдердің айтуынша, G графигінің инциденттік посетінің реттік өлшемі екіге тең, егер және тек қана график жол немесе жолдың ішкі графигі болса. Себебі, инциденттік посеттің реттік өлшемі екі болған жағдайда, оның жалғыз мүмкін іске асырылуы – графтың төбелерімен шектелгенде бір-біріне кері екі толық реттен тұрады. Кез келген басқа екі рет екі төбе арасындағы реттік қатынасты қамтитын қиылысқа ие болады, ал мұндай қатынастар инциденттік посеттерде рұқсат етілмейді. Осы екі рет бойынша төбелерде, екі жиектің соңғы нүктесінен кейін бірден орналастыру арқылы, бірінен кейін бірі келетін төбелер арасындағы жиектерді ретке қосуға болады, бірақ басқа жиектерді қосуға болмайды. Егер графикті төрт түспен бояуға болады, онда оның инциденттік посетінің реттік өлшемі төрттен аспайды. n төбесі бар толық графиктің инциденттік посетінің реттік өлшемі болады.
The incidence poset of a complete graph on n vertices has order dimension .