Фарис теоремасы - Fárys theorem - Wikipedia

Математикада, Фери теоремасы кез келген қарапайым жазықтық график бола алады сызылған оның шеттері түзу болатындай етіп өткелдерсіз сызық сегменттері. Яғни, графиктің шеттерін түзу кесінді емес, қисық түрінде салу мүмкіндігі графиктердің үлкен класын салуға мүмкіндік бермейді. Теорема атымен аталған Истван Фери, дегенмен бұл өз бетінше дәлелденді Клаус Вагнер  (1936 ), Фери  (1948 ), және Шерман К.Штайн  (1951 ).

Дәлел

Фери теоремасын дәлелдеуге арналған индукциялық қадам.

Фери теоремасын дәлелдеудің бір әдісі - қолдану математикалық индукция.^[1] Келіңіздер G қарапайым бол жазықтық графигі бірге n төбелер; егер қажет болса, жиектерді қосуға болады G максималды жазықтық графигі болып табылады. Егер n <3, нәтижесі маңызды емес. Егер n ≥ 3, содан кейін барлық беттер G үшбұрыш болуы керек, өйткені біз максималды жазықтықтың болжамына қайшы келетін, жоспарлылықты сақтай отырып, кез-келген бетке жиекті қосатын едік. Үш шыңды таңдаңыз а, б, в үшбұрышты бетін қалыптастыру G. Біз индукция арқылы дәлелдейміз n түзудің изоморфты қайта біріктірудің түзу сызығы бар G үшбұрышта abc кірістірудің сыртқы беті болып табылады. (Комбинаторлық тұрғыдан изоморфты жаңа сызбадағы шыңдар, шеттер мен беттер ескі суреттегі суреттерге сәйкес келетін етіп жасалуы мүмкін дегенді білдіреді, осылайша шеттер мен шеттер арасындағы барлық инциденттер сақталуы керек, тек шыңдар мен шеттер арасында емес). негізгі жағдай, нәтиже болған кезде тривиальды болады n = 3 және а, б және в ішіндегі жалғыз шыңдар G. Осылайша, біз бұл туралы ойлауымыз мүмкін n ≥ 4.

Авторы Эйлер формуласы жоспарлы графиктер үшін, G бар 3n − 6 жиектер; эквивалентті, егер біреуін анықтаса жетіспеушілік шыңның v жылы G болу 6 − градус (v), кемшіліктердің жиынтығы 12. Бастап G кем дегенде төрт төбесі және барлық беткейлері бар G үшбұрыш болып табылады, сондықтан әрбір шыңы G кем дегенде үш дәрежесі бар. Сондықтан әрбір шыңы G кем дегенде үшеуі жетіспейді, сондықтан оң жетіспейтін кем дегенде төрт шыңы бар. Атап айтқанда, біз шыңды таңдай аламыз v ең көп дегенде бес көршісімен ерекшеленеді а, б және в. Келіңіздер G ' жою арқылы қалыптасады v бастап G және бетті қалпына келтіру f жою арқылы қалыптасады v. Индукция бойынша, G ' құрамына изоморфты түзудің қайтадан ендірілуі кіреді abc сыртқы бет. Қайта ендіру болғандықтан G ' изоморфты болды G ', одан жасау үшін қосылған шеттерін алып тастаңыз G ' бетті қалдырады f, ол қазір көпбұрышқа айналды P ең көп дегенде бес жағы. Суретті түзудің изоморфты қайта түзу сызықты сызығына аяқтау үшін G, v көпбұрышқа орналастырылып, көпбұрыштың шыңдарына түзу сызықтармен қосылуы керек. Бойынша көркем галерея теоремасы, нүктелік интерьер бар P қай уақытта v шеттері болатындай етіп орналастыруға болады v шыңдарына дейін P дәлелдеуді аяқтай отырып, басқа шеттерден өтпеңіз.

Осы дәлелдеудің индукциялық қадамы оң жақта көрсетілген.

Ұқсас нәтижелер

Де Фрейссейс, Пач және Поллак сызықтық уақытта графиканың өлшемдерінде сызықтық сызықтары бар торда түзу сызықты қалай табуға болатынын көрсетті. әмбебап нүктелер жиынтығы квадраттық өлшеммен Осындай әдісті Шнидер кеңейтілген шекараны дәлелдеу үшін қолданды және а жоспарлықтың сипаттамасы аурудың ішінара ретіне негізделген. Оның жұмысы а деп аталатын үш ағашқа максималды жоспарлы графиктің шеттерінің белгілі бір бөлігінің болуын баса айтты Шнайдер ағашы.

Туттенің көктем теоремасы әрбір 3 қосылған планарлы графикті жазықтықта қиылыстарсыз жүргізуге болады, сондықтан оның шеттері түзу кесінділерге, ал сыртқы жағы дөңес көпбұрышқа айналады деп тұжырымдайды (Tutte 1963). Бұл деп аталады, өйткені мұндай ендіруді жүйенің тепе-теңдік күйі ретінде табуға болады бұлақтар графиктің шеттерін бейнелейтін.

Штайниц теоремасы әрбір 3 қосылған планарлы графикті үш өлшемді кеңістіктегі дөңес полиэдрдің шеттері ретінде көрсетуге болатындығын айтады. Тік сызықты ендіру ${ displaystyle G,}$ Тутте теоремасында сипатталған типті жазықтыққа осындай көпсалалы бейнелеуді шығару арқылы пайда болуы мүмкін.

The Дөңгелек орау теоремасы әрбір жазықтық графикі ретінде ұсынылуы мүмкін екенін айтады қиылысу графигі жазықтықтағы қиылыспайтын шеңберлер жиынтығының. Графиктің әр шыңын сәйкес шеңбердің ортасына орналастыру түзу сызықты бейнелеуге әкеледі.

Математикадағы шешілмеген мәселе: Әрбір жазықтық графиктің барлық ұзындықтары бүтін сандар болатын түзу сызығы бар ма? (математикадағы шешілмеген мәселелер)

Хейко Харборт әрбір жазықтық графиктің барлық ұзындықтары бүтін болатын түзу сызықты бейнесі бар ма деген сұрақ қойды.^[2] Шындық Харборттың болжамдары 2014 жылға дейін белгісіз болып қалады^{[жаңарту]}. Алайда, түзу сызыққа бүтіндей қашықтыққа ендіру үшін белгілі текше графиктер.^[3]

Сакс (1983) а графикасы бар ма деген сұрақ қойды сілтемесіз ендіру үш өлшемді Евклид кеңістігі барлық жиектері түзу сызықтар кесіндісімен ұсынылған сілтемесіз ендірмеге ие, мысалы, Фари теоремасына екі өлшемді ендіру теоремасына ұқсас.

Сондай-ақ қараңыз

• Иілуді азайту

Ескертулер

Әдебиеттер тізімі

• Фери, Истван (1948), «Пландық графиктің түзу сызбасы бойынша», Acta Sci. Математика. (Сегед), 11: 229–233, МЫРЗА  0026311.
• де Фрейссейс, Гюберт; Пач, Янос; Pollack, Ричард (1988), «Fary планарлы графиктің кірістіруін қолдайтын шағын жиынтықтар», Компьютерлік есеп теориясының жиырмасыншы жыл сайынғы ACM симпозиумы, 426-433 б., дои:10.1145/62212.62254, ISBN  0-89791-264-0, S2CID  15230919.
• де Фрейссейс, Гюберт; Пач, Янос; Pollack, Ричард (1990), «Торға жазықтық графигін қалай салуға болады», Комбинаторика, 10: 41–51, дои:10.1007 / BF02122694, МЫРЗА  1075065, S2CID  6861762.
• Джилин, Джим; Гуо, Анжи; МакКиннон, Дэвид (2008), «Бүтін шеттерінің ұзындығымен текше жазықтық графиктердің түзу сызықтары» (PDF), Дж. Графикалық теория, 58 (3): 270–274, дои:10.1002 / jgt.20304.
• Харборт, Х .; Кемниц, А .; Моллер М .; Sussenbach, A. (1987), «Ganzzahlige planare Darstellungen der platonischen Korper», Элем. Математика., 42: 118–122.
• Кемниц, А .; Harborth, H. (2001), «Жазықтықты графиктердің жазықтықтың интегралды суреттері», Дискретті математика., 236 (1–3): 191–195, дои:10.1016 / S0012-365X (00) 00442-8.
• Мохар, Боян (2003), Беттердегі графиктер кітабындағы мәселелер.
• Мохар, Боян; Томассен, Карстен (2001), Беттердегі графиктер, Джон Хопкинс Университеті Баспасы, roblem 2.8.15 б., ISBN  0-8018-6689-8.
• Сакс, Хорст (1983), «Планарлық графиктер туралы Куратовский теоремасының кеңістіктік аналогы туралы - Ашық мәселе», Хоровецкиде, М .; Кеннеди, Дж. В .; Сисло, М.М. (ред.), Графикалық теория: Польшаның Шагов қаласында өткен конференция материалдары, 10-13 ақпан, 1981 ж, Математикадан дәрістер, 1018, Springer-Verlag, б. 230–241, дои:10.1007 / BFb0071633, ISBN  978-3-540-12687-4.
• Шнайдер, Вальтер (1990), «Торға жоспарлы графиктерді енгізу», Proc. Дискретті алгоритмдер бойынша 1-ші ACM / SIAM симпозиумы (SODA), 138–148 бб.
• Штейн, С.К. (1951), «дөңес карталар», Американдық математикалық қоғамның еңбектері, 2 (3): 464–466, дои:10.2307/2031777, JSTOR  2031777, МЫРЗА  0041425.
• Тутте, В. Т. (1963), «Графикті қалай салуға болады», Лондон математикалық қоғамының еңбектері, 13: 743–767, дои:10.1112 / plms / s3-13.1.743, МЫРЗА  0158387.
• Вагнер, Клаус (1936), «Bemerkungen zum Vierfarbenproblem», Jahresbericht der Deutschen Mathematiker-Vereinigung, 46: 26–32.