Кіріспе
d өлшемдегі d+2 нүктелерді екі қосалқы жиынға бөлуге болады, олардың дөңгелек қабықшалары қиылысады. Геометрияда, 1921 жылы Иоганн Радон жариялаған дөңгелек жиынтар туралы Радон теоремасы былай гласиды: d+2 нүктеден тұратын кез келген жиынтықты Rd кеңістігінде екі жиынға бөлуге болады, олардың дөңгелек қабықшалары қиылысады. Осы дөңгелек қабықшалардың қиылыс нүктесі жиынның Радон нүктесі деп аталады. Мысалы, d=2 болғанда, Евклид жазықтығындағы төрт нүктенің кез келген жиынтығы екі түрдің бірімен бөлінеді. Ол үштік пен жеке нүктеден тұруы мүмкін, мұнда үштіктің (үшбұрыштың) дөңгелек қабықшасы жеке нүктені қамтиды; немесе екі қиылысатын түзу кесінділерінің ұштарын құрайтын екі жұп нүктеден тұруы мүмкін.
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that:Any set of d + 2 points in Rd can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these convex hulls is called a Radon point of the set. For example, in the case d = 2, any set of four points in the Euclidean plane can be partitioned in one of two ways. It may form a triple and a singleton, where the convex hull of the triple (a triangle) contains the singleton; alternatively, it may form two pairs of points that form the endpoints of two intersecting line segments.
Топологиялық Радон теоремасы
Радон теоремасының эквивалентті формулировкасы: Егер ƒ — (d + 1) өлшемді симплекс Δd+1-ден Rd-ге дейінгі кез келген аффиндік функция болса, онда Δd+1-дің екі бөлек жатқан беттері бар, олардың ƒ бойынша бейнелері қиылысады. Олар эквивалентті, себебі симплекстегі кез келген аффиндік функция оның төбелерінің бейнелерімен толық анықталады. Формальды түрде, ƒ-ны Δd+1-ден Rd-ге дейінгі аффиндік функция деп есептейік. Δd+1 төбелері болсын, ал олардың ƒ бойынша бейнелері болсын. Бастапқы формулировка бойынша, төбелер екі бөлек жиынға бөлінеді, мысалы, (xi)i∈I және (xj)j∈J, олардың дөңгелек қабықшалары жапсарлы. f аффиндік болғандықтан, I жиынындағы (xi)i-нің дөңгелек қабықшасы I жиынындағы (vi)i төбелері арқылы анықталатын беттің бейнесі, ал сол сияқты J жиынындағы (xj)j-нің дөңгелек қабықшасы J жиынындағы (vj)j төбелері арқылы анықталатын беттің бейнесі болады. Бұл екі бет бөлек, ал олардың f бойынша бейнелері жаңа формулировка бойынша талап етілгендей қиылысады. Топологиялық Радон теоремасы осы формулировканы жалпылайды. Ол f-тің міндетті түрде аффиндік емес, кез келген үздіксіз функция болуына мүмкіндік береді: келесідей:
Sd (d өлшемді сфера) — Δd+1-ге үздіксіз g бейнелеуін құрастырыңыз, онда сферадағы әрбір x нүктесі үшін g(x) және g(-x) Δd+1-дің екі бөлек бетінде жатады. g функциясына Борсук-Улам теоремасын қолданыңыз, ол Sd-ден Rd-ге үздіксіз функция. Теорема бойынша, кез келген мұндай функция үшін Sd-де y нүктесі бар, онда f(g(y)) = f(g(-y)). g(y) және g(-y) нүктелері Δd+1-дің екі бөлек бетінде жатыр және олар f арқылы Rd-тің бір нүктесіне бейнеленеді. Бұл осы екі беттің бейнелері қиылысады дегенді білдіреді. Ловаш және Шрайвер басқа да дәлел келтірді. Үшінші дәлелді Матушек келтіреді:
K — симплекс Δd+1 болсын, ал — K-нің өзімен жойылған қосылысы болсын. геометриялық іске асырылуы Sd+1 сферасына гомеоморфты. Сондықтан, Z2 индексі d+1-ге тең. Топологиялық Радон теоремасы келесі жалпы теоремадан туындайды. Кез келген симплициалдық комплекс K үшін, егер Z2 индексі d-ден үлкен болса, онда ||K||-ден Rd-ге кез келген үздіксіз бейнелеу үшін K-нің екі бөлек бетінің бейнелері қиылысады.
Қолданбалар
Жазықтағы кез келген төрт нүктенің Радон нүктесі – олардың геометриялық медианасы, яғни басқа нүктелерге дейінгі қашықтықтардың қосындысын ең төменге түсіретін нүкте. Радон теоремасы – дөңес жиындардың қиылыстары туралы Хелли теоремасының стандартты дәлелінің маңызды қадамы болып табылады; осы дәлел Радон теоремасының бастапқы ашылуына түрткі болды. Радон теоремасын сызықтық бөліністерге қатысты d өлшемді нүктелердің VC өлшемін есептеу үшін де қолдануға болады. d + 1 нүктеден тұратын жиынтықтар бар (мысалы, тұрақты симплекстің нүктелері), онда кез келген екі бос емес ішкі жиынтықты гипержазық арқылы бір-бірінен бөлуге болады. Дегенмен, d + 2 нүктенің қандай жиынтығы берілсе де, Радон бөлімінің екі ішкі жиынтығын сызықтық түрде бөлу мүмкін емес. Сондықтан, осы жүйенің VC өлшемі дәл d + 1-ге тең. Кездейсоқ алгоритм, d + 2 нүктенің жиынтығын олардың Радон нүктесімен қайта-қайта алмастыра отырып, кез келген нүктелер жиынтығының центрін табуға жуықтауды есептеу үшін қолданылуы мүмкін, бұл операция нүктелер саны мен өлшемдеріне қатысты полиномиалды уақыт алады. Радон теоремасы графтар үшін. Кез келген бағытталмаған графта, дөңес жиынтық – жиынтықтағы төбелерді байланыстыратын әрбір индукцияланған жолды қамтитын төбелер жиынтығы деп анықталады. Осы анықтама бойынша, графтың ω + 1 төбесінен тұратын кез келген жиынтығын екі ішкі жиынтыққа бөлуге болады, олардың дөңес қабықшалары қиылысады, ал ω + 1 – мұндай бөлуге болатын ең аз сан, мұнда ω – берілген графтың клика саны. Индукцияланған жолдардың орнына ең қысқа жолдарды қолданатын ұқсас нәтижелер үшін және қараңыз.