Тығыз байланысқа ие сирең графтар

Кіріспе

Қатты байланысты сиреп тұрған график. Графтар теориясында экспандерлік график – сиреп тұрған, бірақ күшті байланысқа ие график, оның байланыстылығы төбелік, қабырғалық немесе спектрлік кеңею арқылы өлшенеді. Экспандерлік құрылымдар таза және қолданбалы математикада зерттеулерге бастап, күрделілік теориясы, берік компьютерлік желілерді жобалау және қателерді түзету кодтарының теориясы салаларында көптеген қолданыс тапты.

Анықтамалар

Интуитивті түрде, экспандерлік граф – бұл шекті, бағытталмаған көпқырлы граф, онда "тыныш үлкен" емес төбелердің кез келген ішкі жиынының "үлкен" шекарасы болады. Осы ұғымдардың әртүрлі формалдануы экспандерлердің әртүрлі түрлерін тудырады: жиек экспандерлері, төбе экспандерлері және спектрлік экспандерлер, төменде анықталғандай. Үзіліссіз граф экспандер бола алмайды, себебі байланысқан компоненттің шекарасы бос. Кез келген байланысқан граф – экспандер болып табылады; алайда, әртүрлі байланысқан графтардың әртүрлі экспансия параметрлері болады. Толық граф ең жақсы экспансия қасиетіне ие, бірақ ол мүмкін болатын ең жоғары дәрежеге ие. Формальды емес айтқанда, граф жақсы экспандер болып есептеледі, егер оның төмен дәрежесі және жоғары экспансия параметрлері болса.

Әр түрлі кеңею қасиеттерінің арасындағы қатынастар

Жоғарыда анықталған кеңею параметрлері бір-бірімен байланысты. Атап айтқанда, кез келген d реттелі граф G үшін,

Осылайша, тұрақты дәрежелі графтар үшін, төбелік және қабырғалық кеңею сапалық тұрғыдан бірдей.

Құрылыстар

Экпандерлік графиктер отбасыларын тікелей құрудың төрт негізгі стратегиясы бар. Бірінші стратегия алгебралық және топтық-теориялық, екінші стратегия аналитикалық және қосымша комбинаториканы пайдаланады, үшінші стратегия комбинаторлық және зигзаг және оған байланысты график көбейтімдерін қолданады, ал төртінші стратегия көтерулерге негізделген. Нога Алон шекті геометриядан құралған белгілі бір графиктердің жоғары кеңейтілген графиктердің ең сирек мысалдары екенін көрсетті.

Кездейсоқ құрылымдар

Ықтималдық аргументтер арқылы жақсы кеңейту қасиеттеріне ие графиктердің бар екенін көрсететін көптеген нәтижелер бар. Шындығында, кеңейтушілердің бар екендігін алғаш рет Пинскер дәлелдеді, ол кездейсоқ таңдалған n төбелі сол жақтан d реттегі екі жақты граф үшін, төбелердің барлық ішкі жиындары үшін жоғары ықтималдықпен, d-ге тәуелді тұрақты шама бар екенін көрсетті. Ал Алон мен Ройхман әрбір 1 > ε > 0 үшін қандай да бір c(ε) > 0 табылатынын көрсетті, осыған сәйкес: n реттік G тобы үшін, G-ден кездейсоқ таңдалған элементтермен G-дегі Кейли графигін қарастырыңыз. Содан кейін n шексіздікке жақындағанда, алынған граф дерлік қамтитын ε кеңейтуші болады.

Қолданылулары мен пайдалы қасиеттері

Кеңейтушілердің бастапқы мақсаты экономикалық тұрақты желілерді (телефондық немесе компьютерлік) құру болды: шектеулі дәрежелі кеңейтуші – бұл барлық ішкі жиындар үшін өлшеммен (түйіндер санымен) сызықтық өсетін асимптотикалық тұрақты граф. Экпандерлік графтар компьютерлік ғылымда алгоритмдерді, қателерді түзету кодтарын, экстракторларды, псевдорандомдық генераторларды, сұрыптау желілерін және тұрақты компьютерлік желілерді жобалауда кеңінен қолданылады. Олар есептеу күрделілігі теориясындағы SL = L және PCP теоремасы сияқты маңызды нәтижелерді дәлелдеуде де пайдаланылды. Криптографияда экспандерлік графтар хэш-функцияларды құру үшін қолданылады. 2006 жылғы экспандерлік графтар туралы шолуда Хури, Линиал және Вигдерсон экспандерлік графтарды зерттеуді төрт санатқа бөлді: экстремалдық мәселелер, типтік мінез-құлық, нақты құрылымдар және алгоритмдер. Экстремалдық мәселелер кеңейту параметрлерін шектеуге бағытталған, ал типтік мінез-құлық мәселелері кеңейту параметрлерінің кездейсоқ графтарда қалай таралатынын сипаттайды. Нақты құрылымдар белгілі бір параметрлерді оңтайландыруға арналған графтарды құруға бағытталған, ал алгоритмдік сұрақтар параметрлерді бағалау және анықтауды зерттейді.

Экспандермен жүгіру үлгісін алу

Чернофф шектеуі [−1, 1] диапазонындағы кездейсоқ шамадан көптеген тәуелсіз үлгілер алынғанда, осы үлгілердің орташа мәні жоғары ықтималдылықпен кездейсоқ шаманың математикалық күтілуіне жақын болатынын көрсетеді. Expander walk sampling lemma, және , экспандер графигіндегі жүрістен үлгі алғанда да осы қағида сақталады екенін дәлелдейді. Бұл, әсіресе, дерandomization теориясында маңызды, себебі экспандерлік жүріс бойынша үлгі алу, тәуелсіз үлгі алуға қарағанда әлдеқайда аз кездейсоқ биттерді қажет етеді.

AKS сұрыптау желісі және шамамен жартылай бөлу

Сорталау желілері кіріс жиынтығын қабылдап, кірістерді сұрыптау үшін параллель қадамдар сериясын орындайды. Параллель қадам – бұл кез келген сандағы байланыссыз салыстыруларды орындау және салыстырылған кіріс жұптарын ауыстырудан тұрады. Желінің тереңдігі оның параллель қадамдарының санымен анықталады. Экспандерлік графтар AKS сорттау желісінде маңызды рөл атқарады, ол O(log n) тереңдігіне жетеді. Бұл сорттау желісі үшін асимптотикалық жағынан ең жақсы белгілі тереңдік болғанымен, экспандерлерге тәуелділік тұрақты шекті практикалық қолдану үшін тым жоғары етеді. AKS сорттау желісінде экспандерлік графтар шектелген тереңдіктегі ε-жартылай бөлуші құрастыру үшін қолданылады. ε-жартылай бөлуші (1, …, n) ұзындығы n пермутациясын кіріс ретінде қабылдайды және кірістерді екі ажыратылған жиынға – A және B-ге бөледі, мұнда әрбір k бүтін саны үшін ең көп дегенде εk ең кіші k кіріс B жиынында, ал ең көп дегенде εk ең үлкен k кіріс A жиынында болады. A және B жиындары ε-жартылай бөлуді құрайды. d тереңдіктегі ε-жартылай бөлушіні келесідей құрастыруға болады. X және Y бөліктері тең мөлшердегі n төбелі, d дәрежелі екі жақты экспандер алыңыз, яғни ең көп дегенде εn өлшемді төбелердің кез келген ішкі жиынында кем дегенде көршілер болады. Графтың төбелерін кірістерді сақтайтын тіркегіштер ретінде қарастыруға болады, ал қабырғаларын – екі тіркегіштің кірісін салыстыратын сымдар ретінде қарастыруға болады. Бастапқыда кірістердің жартысын X-ке, жартысын Y-ке кездейсоқ орналастырыңыз және қабырғаларды d толық сәйкестікке бөліңіз. Мақсат – X кірістердің шамамен жартысын, ал Y кірістердің үлкен жартысын қамтитындай етіп аяқтау. Мұны іске асыру үшін әрбір сәйкестіктің қабырғаларымен жұптастырылған тіркегіштерді салыстырып, реті бойынша орналаспаған кірістерді түзету керек. Нақтырақ айтқанда, сәйкестіктің әрбір қабырғасы үшін, егер үлкен кіріс X тіркегішінде болса және кіші кіріс Y тіркегішінде болса, кішісі X-те, үлкені Y-де болуын қамтамасыз ету үшін екі кірісті ауыстырыңыз. Бұл процесс d параллель қадамнан тұрады. Барлық d айналымнан кейін A жиыны X тіркегішіндегі кірістерден, ал B жиыны Y тіркегішіндегі кірістерден құралады, осылайша ε-жартылай бөлуді аламыз. Мұны мысалы қарастырайық, егер X-тегі u және Y-дегі v тіркегіштері uv қабырғасымен байланысқан болса, онда осы қабырғамен сәйкестендіру өңделгеннен кейін u тіркегішіндегі кіріс v тіркегішіндегі кірістен кіші болады. Бұдан әрі, бұл қасиет процестің қалған бөлігінде де сақталады. Енді, егер кейбір (1, …, k) кірістерінің εk-дан астамы B жиынында болса деп есептейік. Содан кейін графтың экспансиялық қасиеттеріне сәйкес, Y жиынындағы осы кірістердің тіркегіштері X жиынындағы кем дегенде тіркегіштермен байланысады. Барлығы k тіркегіштен артық, сондықтан X жиынында A тіркегішінің кейбіреуі Y жиынындағы B тіркегішіне қосылуы керек, сондықтан A тіркегішінің соңғы кірісі (1, …, k) емес, ал B тіркегішінің соңғы кірісі (1, …, k) болады. Бұл алдыңғы қасиетке қайшы келеді, сондықтан A және B жиындары ε-жартылай бөлуді құруы керек.

Sorting networks take a set of inputs and perform a series of parallel steps to sort the inputs. A parallel step consists of performing any number of disjoint comparisons and potentially swapping pairs of compared inputs. The depth of a network is given by the number of parallel steps it takes. Expander graphs play an important role in the AKS sorting network, which achieves depth O(log n). While this is asymptotically the best known depth for a sorting network, the reliance on expanders makes the constant bound too large for practical use. Within the AKS sorting network, expander graphs are used to construct bounded depth ε halvers. An ε halver takes as input a length n permutation of (1, , n) and halves the inputs into two disjoint sets A and B such that for each integer at most εk of the k smallest inputs are in B and at most εk of the k largest inputs are in A. The sets A and B are an ε halving. Following , a depth d ε halver can be constructed as follows. Take an n vertex, degree d bipartite expander with parts X and Y of equal size such that every subset of vertices of size at most εn has at least neighbors. The vertices of the graph can be thought of as registers that contain inputs and the edges can be thought of as wires that compare the inputs of two registers. At the start, arbitrarily place half of the inputs in X and half of the inputs in Y and decompose the edges into d perfect matchings. The goal is to end with X roughly containing the smaller half of the inputs and Y containing roughly the larger half of the inputs. To achieve this, sequentially process each matching by comparing the registers paired up by the edges of this matching and correct any inputs that are out of order. Specifically, for each edge of the matching, if the larger input is in the register in X and the smaller input is in the register in Y, then swap the two inputs so that the smaller one is in X and the larger one is in Y. It is clear that this process consists of d parallel steps. After all d rounds, take A to be the set of inputs in registers in X and B to be the set of inputs in registers in Y to obtain an ε halving. To see this, notice that if a register u in X and v in Y are connected by an edge uv then after the matching with this edge is processed, the input in u is less than that of v. Furthermore, this property remains true throughout the rest of the process. Now, suppose for some that more than εk of the inputs (1, , k) are in B. Then by expansion properties of the graph, the registers of these inputs in Y are connected with at least registers in X. Altogether, this constitutes more than k registers so there must be some register A in X connected to some register B in Y such that the final input of A is not in (1, , k), while the final input of B is. This violates the previous property however, and thus the output sets A and B must be an ε halving.

Зерттеу мақалалары

Please provide the English text you want me to translate. I need the content of the "..." to begin the translation process. I will use the existing translation reference you provided *only* as a guide for terminology, prioritizing accuracy to the original English meaning.