Дипломдық ЖҰмыс тақырыбы: «Жұлдызша тәрізді таралған мобильді фракталды тордың өлшемділігін бағалау» 5В071900 «Радиотехника, электроника және телекоммуникация»
жүктеу/скачать 452,44 Kb.
|
Дипломдық жұмыс
Қазақстан Республикасы Білім және ғылым министрлігі әл-Фараби атындағы Қазақ ұлттық университеті Физика-техникалық факультеті Қатты дене және бейсызық физика кафедрасы ДИПЛОМДЫҚ ЖҰМЫС тақырыбы: «Жұлдызша тәрізді таралған мобильді фракталды тордың өлшемділігін бағалау» 5В071900 – «Радиотехника, электроника және телекоммуникация» Орындаған:___________________________________ (Т.А.Ж.) (қолы)
Қорғауға жіберілді: Хаттама № , « » _________ 20___ ж. Кафедра меңгерушісі _________________________________ (Т.А.Ж.) (қолы және мөрі) Нормобақылау _________________________________ (Т.А.Ж.) (қолы) Алматы, 2022 ж. Мазмұны 1 Кіріспе......…………….………………………………………..…………3 1.1 Жалпы фракталдық……………………………………….…….. 5 1.2 Желілердің фракталдығы…………………………………………….. 5 2 Алгоритмдер.......……………………………………………… 6 2.1 Сараң бояу……………..……………………….………………… 6 2.2 Шағын қорапты сығу………………………..……………………… 7 2.3 Алынып тасталынған массалық жаппай күйік…...…………. 8 2.4 Шығарылған массаның қатынасы... …………………………………9 3 Зерттелетін желілер .......……………………………………………… 10 3.1 Теориялық модельдер. .....………………………10 3.1.1Ультракүлгін гүл………………………………. 10 3.2 Нақты әлемдік желілер. ……………………….………………………11 3.2.1 ECOli желісі…….…………………….……………12 3.2.2 Ферменттік желі………………………….……………………. 13 3.2.3 Миннесота желісі …………….………………………………13 4 Әдістер және нәтижелер ………………….……………………14 4.1 Ұяшық нөмірлері ………………….……………………………… 4.1.1 Қорап өлшемдері ………………….……………………………… 5 Қорытынды ………………….………………………………… Пайдаланылған әдебиеттер тізімі.........………………………………… 1. Кіріспе Желілік ғылым - желілік операцияларды сипаттауға және талдауға бағытталған өте белсенді зерттеу саласы. Нысандар тобының арасындағы қатынастарды табиғи түрде график ретінде модельдеуге болады, мұнда түйіндер мен жиектер сәйкесінше топ мүшелерін және олардың қарым-қатынастарын көрсетеді, бұл желілік ғылымды практикалық өмірде көптеген әлеуетті қолданбалары бар пәнге айналдырады. Фракталдардың қысқаша тарихы. Фракталдық геометрия 1975 жылы les Objects Fractals кітабының алғашқы басылымымен" ресми түрде дүниеге келді". Мандельброт ойлап тапқан "фрактал" сөзі латынның фрактус сөзінен шыққан, ол "фрагменттелген"дегенді білдіреді. Фракталдық объект, әдетте, өзіне ұқсас мінез-құлықты көрсетеді, яғни фракталдық объектінің үлгісі әр түрлі масштабтар кеңейту (кішірейту) немесе қысу (масштабтау) нәтижесінде пайда болғанына қарамастан әр түрлі масштабта қайталанады. Мандельброт былай деп жазды:"...фракталдар-бұл кедір-бұдыр және фрагментациялану үрдісі жоқ, жоғары және төмен емес, бірақ зерттеуді үнемі ұлғайту және нақтылау кезінде өзгеріссіз қалады". Фракталдар "өзіне ұқсас геометриялық фигуралар"ретінде анықталған. Қысқаша түсінік беру үшін, фракталдық желілер түсінігі геометриядан алынған фрактал ұғымының азды-көпті қорытылуы болып табылады. Фракталды желілердің қызықты қасиеттері бар деп болжанады, олар сыртқы әсерлерге төзімділігінде көрінеді [6]. Әдебиеттер фракталдық желілер әдейі жасалған шабуылдарға салыстырмалы түрде төзімді деп болжайды, бұл, мысалы, көптеген биологиялық желілердің фракталдық мінез-құлыққа қарай дамитынын түсіндіруі мүмкін [6]. Бұл мақалада біз фракталдық желілерді талдау үшін жасалған көптеген алгоритмдерді қарастырамыз. Атап айтқанда, кейінірек енгізілген қорап тәрізді желілік қамтуды орындау үшін. Біз әдебиеттерден белгілі әдістерді жинадық, оларды жүзеге асырдық және олардың әртүрлі нақты желілерде және теориялық желілік модельдердегі өнімділігін салыстырдық. Бұған көптеген желілердегі көптеген алгоритмдерді жүйелі түрде салыстыру басты үлес деп есептейміз. Сонымен қатар, біз GitHub жүйесінде ашық бастапқы Python пакеті ретінде кодымызды шығаруды жоспарлап отырмыз, осылайша біздің нәтижелер қайталануы мүмкін және әріптестер біздің блоктарды қамтитын алгоритмдер жинағын пайдалана алады. Олкоманданың бір бөлігі болмаса да, біз Ботонд Дивики-Надидің осы жобадағы жұмысын мойындаймыз. 1.1 Жалпы фракталдылық «Фрактал» термині евклидтік кеңістіктердің геометриясынан шыққан. Біз әдетте d-өлшемді кеңістікте (IRd) қарастыратын объектілердің нақты анықталған көлемі бар, оны келесідей бағалауға болады: біз бүкіл кеңістікті өлшемді біркелкі тормен жабамыз және гиперкубтардың жалпы көлемін есептейміз, біздің нысанда қамтылған. Мысалы, екі өлшемді шеңбер үшін шетінің ұзындығы l болатын квадраттар торын саламыз және шеңбердің ішіндегі шаршылардың санын санаймыз, содан кейін көбейтеміз. l → 0 шегін қабылдағанда, біздің нәтижелер объектінің көлеміне жақындайды. Егер кем дегенде бір нысан нүктесі бар блоктар санын қарастырсақ, әдетте бұл N саны асимптоталық түрде сияқты әрекет ететінін табамыз, мұндағы d - кеңістік өлшемі. Енді фракталдар -де өмір сүрсе де, жоғарыда сипатталған егжей-тегжейлі процедураны орындайтын болсақ, онда біз N болатынын көреміз, мұндағы объектілердің фракталдық өлшемі, әдетте not d-ке тең және натурал сан емес. Фракталдардың жарқын мысалы, Сьерпинский үшбұрышы 1-суретте көрсетілген. 1-сурет: Сиерпински үшбұрышы [7] фракталдық өлшем ≈ 1,59 [8] 1.2 Желілердің фракталдығы Фракталды желілер түсінігі кәдімгі фракталдарға өте ұқсас. Ұқсастықты көру үшін желілердің фракталдық өлшемін өлшеуге болатын әдісті еске түсірейік: қорапты жабу [3] 1. Егер осы түйіндердің кез келген жұбы үшін олардың ең қысқа қашықтығы -ден аз болса, түйіндер тобы өлшемді қорапқа сәйкес келеді деп айтамыз. 2. Желі өлшемді ұяшықтармен жабылады, егер оның түйіндері әрбір топ өлшемді бір ұяшыққа сыятындай етіп бөлінген болса. 3. Ықтимал қақпақтардың саны шектеулі болғандықтан, желіні өлшемді қораптармен жабу үшін қораптардың ең аз саны бар. Мұны біз ( ) деп белгілейміз. 4. Егер ( ) болса, желі фракталды өлшемі фракталды. Айта кету керек, бұл анықтама шектеулі желілер үшін қатаң түрде орындала алмайды. Тәжірибеде деректер нүктелерінің жиыны ( ) есептеледі, содан кейін тәуелділік жақсы жуықтау үшін қуат заңы болып табылатынын көру үшін логарифмдік графикпен тексеріледі.
2 Алгоритмдер 2.1 Сараң бояу Сараң бояудың нұсқалары графиктің боялмаған бөлігінің құрылымын білмей-ақ түстерді онлайн режимінде таңдайды немесе түстердің жалпы санын азайту үшін бірінші қолжетімді түстерден басқа түстерді таңдайды. Сараң бояу алгоритмдері бөлу мәселелерін жоспарлау және тіркеуге, комбинаторлық талдауға және басқа математикалық нәтижелерді, соның ішінде бояу мен дәреже арасындағы байланыс туралы Брукс теоремасын дәлелдеуге қолданылған. Сараң бояғыштардан алынған графикалық теориядағы басқа ұғымдарға графиканың «Қанық» саны (Сараң бояу арқылы табуға болатын ең көп түс саны) және жақсы боялған графиктер, барлық сараң бояулар бірдей санды пайдаланатын графиктер кіреді. Берілген графиктің төбелері берілген реттілікпен боялатын, бірақ әрбір шың үшін таңдалған түс міндетті түрде бірінші қолжетімді түс болып табылмайтын сараң бояу алгоритмінің вариацияларын анықтауға болады. Оларға графиканың боялмаған бөлігі алгоритмге белгісіз немесе алгоритмге негізгі сараң алгоритмге қарағанда жақсырақ бояу таңдауы үшін біршама еркіндік берілген әдістер жатады. Сараң алгоритмнің алғашқы қолданбаларының бірі курсты жоспарлау сияқты мәселелерге қатысты болды, онда тапсырмалар жинағы берілген уақыт аралығына тағайындалуы керек, сәйкес келмейтін тапсырмалардың бір уақыт аралығына тағайындалуын болдырмайды. Оны төбелері регистрлерге тағайындалатын мәндерді көрсететін және жиектері бір регистрге тағайындалмайтын екі мән арасындағы қайшылықтарды көрсететін графикке қолдану арқылы оны регистрлерді бөлу үшін компиляторларда да қолдануға болады. Көптеген жағдайларда бұл интерференциялық графиктер хордалық графиктер болып табылады, бұл сараң бояуға оңтайлы регистр тағайындауын жасауға мүмкіндік береді. Қорапты бояуы сараң болатын алгоритмдер тобы өзекті мәселе болып табылады. Ұйғарым мынада: бастапқы желіміздің қос графигін қарастырайық: бұл график бірдей төбелерден және «қос жиектерден» тұрады [4]. Бұл екі төбенің қос графтың жиегі арқылы қосылғанын білдіреді, егер олардың бастапқы желідегі қашықтығы -ден үлкен болса ғана. Ұйғарым 2-суретте көрсетілген, = 2. 2-сурет: График (сол жақта) және оның егізі (оң жақта). Біз сонымен қатар қос графиктің рұқсат етілген бояуын көрсетеміз. (Біз lB = 2 қолдандық.) Осы алдын ала қадамдардан кейін біз екілік графиктің төбелерін бояуды мақсат етеміз, осылайша i) көрші төбелер бірдей түске ие болмайтындай ii) ең аз мүмкін түстерді пайдалануды мақсат етеміз. Бұл мәселе бастапқы желідегі бір блокқа жататын бірдей «қос» түсті төбелерді анықтаған кезде бастапқы желінің қабаттасуымен тең. Өкінішке орай, графикті бояу NP-қатты. Белгілі жуықтау алгоритмі - сараң бояу. Бұл алгоритм екі негізгі қадамнан тұрады:
2.2 Шағын қорапты сығу Бұл алгоритм сонымен қатар түйіндерді сығу түсінігін пайдаланады. Бастапқы идея [4]-де ұсынылды. Мәселе - блоктағы кез келген түйіннен lB-ден алыс емес барлық түйіндерді қамтитын жиынтықтан жаңа түйіндерді кездейсоқ таңдайтындай етіп блоктарды өсіру. Бұл авторлардың мағынасында қораптың ықшам болуын қамтамасыз етеді. 3-сурет: MEMB үшін иллюстрация. Сол жақ сызба жабық түйіндерге орталық ретінде рұқсат етілмеген кезде нәтижені көрсетеді, оң жақта оларға рұқсат етілген кездегі нәтиже (rB=1 пайдалану) 2.3 Ең көп алынып тасталынған массалық жаппай күйік (MEMB) Бұл алгоритм [4]-де де ұсынылған. пайдаланудың орнына бұл әдіс центрленген қораптар тұжырымдамасын пайдаланады: әрбір қорапта арнайы түйін, орталық бар. Блоктар әрбір блок элементінің түйіні орталықтан аспайтындай етіп салынған. Алгоритм барлық блоктардың қосылуын қамтамасыз етеді, бір блоктың екі түйінін әрқашан блок ішіндегі жол арқылы қосуға болады. Алгоритмді екі жолмен кездейсоқ реттілік әдісін жақсарту ретінде қарастыруға болады, бірақ аналогия жұмыс істемейді, себебі жазбаны жүзеге асыру жолы кездейсоқ реттілік әдісінен ерекшеленеді. Біріншіден, келесі орталық максималды алынып тасталған массаға, яғни орталықтан rB аспайтын жабылмаған түйіндердің санына негізделген4 таңдалады. • Келесі орталық таңдалғаннан кейін, rB ішіндегі барлық жабылмаған түйіндер жабылады, бірақ блоктарға әлі тағайындалмаған. • Соңында, әрбір түйін жабылғаннан кейін орталық емес түйіндер орталықтарға тағайындалады, осылайша алынған блоктар қосылады. Қораптардың «концентратордың жұмысындағы ақаулар» емес, тек соңында қалыптасу себебін 3-суреттен түсінуге болады. Авторлардың мақсаты бірінші орталықтарды таңдау арқылы «түйіндердің ақауларын» болдырмау болды, содан кейін оларға қалған түйіндерді тағайындау. 2.4 Шығарылған массаның жақындықтың орталықтылығына қатынасы (REMCC) Бұл алгоритмді MEMB-тің өзгертілген нұсқасы ретінде қарастыруға болады [15].Әрбір қадамда жабылмаған түйіндерден жаңа орталық таңдап алынады, осылайша таңдау «f нүктесін», мақаладағы жаңа метрика, ол барлық басқа түйіндерге орташа ең қысқа жолға көбейтілген алынып тасталған масса болып табылады. Содан кейін орталықтың rB-шарындағы барлық түйіндер жабылады. Бұл процедурада орталықтар MEMB-тен айырмашылығы ашылғандардың ішінен таңдалады. 3.Зерттелетін желілер Біз көптеген нақты желілерде және теориялық желілік модельдерде енгізілген алгоритмдерді сынап көрдік. Бұл бөлімде пайдаланылатын желілер берілген. Сонымен қатар, желілердің көлемі мен дәрежесі бойынша таралуы салыстырылады. Бұл белгілі бір дәрежеде желілерді сипаттайды. 3.1.1 Ультракүлгін гүл 4-сурет: Алғашқы екі буын UV21 УК гүлі- бұл фракталдық желілерді беретін әйгілі модель [4]. Желінің құрылымы оны құруды ескере отырып жақсы түсініледі: біз түйіндерінің дөңгелек графигінен бірінші (g = 1) буын ретінде бастаймыз. Әрқайсы буында біз барлық қолданыстағы жиектерді және ұзын жолдармен алмастырамыз. Бұл процесс n (g=n) генерациясына дейін қайталанады. Біз УК-түстердің кейбір маңызды қасиеттерін береміз [4]. Оларды дәрежелер бойынша бөлу-бұл күш Заңы: P ( ) ∝ , мұндағы P ( ) - дәрежесі бар түйіндердің салыстырмалы жиілігі және дәреже көрсеткіші үшін: γ = 1+ (1) Сонымен қатар, 1 < u ≤ v кезінде желінің фракталдық өлшемі: (2) u = 1 үшін желі фракталдық емес. Біз (u, v, n)=(2,2,5) және (2,4,4) болатын желілерді қарастырдық. Бұл желілер сәйкесінше 684 түйіннен, 1024 жиектен және 1038 түйіннен, 1296 жиектен тұрады. 5-сурет: m=2, x=1 болатын SHM моделінің алғашқы үш буыны 3.2 Нақты әлемдік желілер
3.2.2 Ферменттік желі Бұл желі салыстырмалы түрде шағын, максималды қосылған құрамдас бөлігі 125 түйіннен және олардың арасындағы 141 қосылымнан [24] [25] алынған. Ферменттік байланыстарды біз келесі жолмен қарастырғанымызды ескереміз: егер екі фермент кез келген бағыттағы байланыстың түрінде болса, біз оларды бағытталмаған жиекпен қосылған деп санадық. 3.2.3 Миннесота желісі Бұл желі Миннесота 10 [24] [25] жол желісін көрсететін бағытталмаған, салмағы жоқ желі. Максималды қосылған желі құрамдас бөлігі 2640 түйіннен және 3302 жиектен тұрады. Нақты желілердің дәрежелік таралуы Нақты желілерде дәреженің таралуы туралы түсінікке ие болу үшін біз оны бейнелейтін гистограммалар дайындадық. Миннесота мен ферментте жоғары дәрежелі түйіндер жоқ екенін көреміз. (Мысалы. Ол торға немесе ұқсас нәрсеге ұқсауы мүмкін.) Керісінше, EСoli-де бірнеше өте жоғары дәрежелі орталықтар бар. 4 Әдістер және нәтижелер 4.1 Ұяшық нөмірлері
4.1.1 Қорап өлшемдері Алдыңғы процедура әрбір қорап өлшемі үшін қайталанады. Блок өлшемдері әртүрлі алгоритмдердің нәтижелерін салыстыруға келгенде, бізде өлшемдер бірдей болатындай етіп таңдалады. Бұл анық емес мәлімдеменің артында кейбір алгоритмдердің тіктөртбұрыштың радиусы бойынша, басқалары тіктөртбұрыштың өлшемі бойынша параметрленетіндігі жасырылады. 4.1.2 Шексіз желілердің өлшемдері 6-сурет. p = 1 болатын үш тізбек -дегі түйіндердің күтілетін саны , -дегі доғалардың күтілетін саны , ал -тің күтілетін диаметрі Δt болсын. , және Δt шамалары p-ге тәуелді, бірақ шартты қарапайымдылық үшін біз бұл тәуелділікті өткізіп жібереміз. Әрбір доға р ықтималдығы бар үш доғамен және 1 − p ықтималдығы бар төрт доғамен ауыстырылғандықтан, t ≥ 1 үшін бізде мұндағы соңғы теңдік = 1 болып шығады, өйткені бір доғадан тұрады. 7-сурет. p = 0 болатын үш тізбек Біз өз үлесімізді болашақ зерттеулер үшін бірнеше ықтимал бағыттарды тізімдеу арқылы аяқтаймыз: • Жүргізілген алгоритмдерді көбірек желілерде салыстыру керек. Бұл тек уақыт пен есептеу ресурстарының мәселесі болуы керек. Бұл әрекеттер кезінде: • Алгоритмдердің ресурс сыйымдылығын азайту қажет болады. Жақында біз қазіргі енгізуіміз тым көп пайдаланатын мәселеге тап болдық, жергілікті құрылғыда жұмыс істеуге арналған жад, шамамен 4 ГБ оперативті жады жұмыс қорабын жабу үшін бөлінген. Негізгі мәселе түйіннің ең қысқа жол деректерін тиімді сақтау болады деп ойлаймын. (Бұл деректер шынымен де сирек емес, сондықтан бір өріске сыймас үшін тым алыс орналасқан түйіндер үшін қажетсіз есептеулерді және жадты бөлуді болдырмау үшін оны жылдам есептеу керек.) Бірнеше желілерді қарастырған кезде алгоритмдердің өнімділігінің белгілі желі функцияларымен сәйкестігін зерттеуге болады. Біз өз жұмысымызда концентраторсыз желілерде рандомизацияланған алгоритмдердің (біріктіру, кездейсоқ реттілік) салыстырмалы артықшылығын ғана талдадық. Бұл бақылаулар берілген желі үшін сәйкес алгоритмді таңдауға көмектеседі. • Біз қолданып көрген іске асырылған алгоритмдерге қоса, алдыңғы бөлімде егжей-тегжейлі сипатталғандай, біріктіру және MCWR алгоритмдерін өнімділікті жақсарту үшін сәл өзгерту қажет болуы мүмкін. Басқа ашкөздік стратегияларын да сынап көру керек. Үлкенірек желілерге масштабтауға қол жеткізілсе, белгілі фракталды өлшемі бар теориялық желілік модельдерге назар аудару керек. Өлшенген фракталдық өлшемді негізгі ақиқат мәнімен салыстыру үшін блокты қамтитын алгоритмдердің өнімділігін бағалау өте табиғи және ақылға қонымды әдіс болар еді. Жақында біз желілік модельдердің шектеулі санына осындай талдау жасадық (көлемі біздің архитектурамен шектелген). Біз өлшенген және теориялық мәндер арасындағы таңқаларлық үлкен сәйкессіздікті таптық. Зерттеулер негізгі шындықтың фракталдық өлшеміне желінің өлшемі ұлғайған сайын асимптоталық жолмен ғана жетеді деген идеяны қолдайды. Бұл мәселе ұзақ мерзімді перспективада шешілуі керек. • Көбірек алгоритмдерді сынау. Шындығында, біз енгізген барлық алгоритмдерді қоспадық, себебі олардың кейбіреулері тым баяу немесе тым көп гиперпараметрлерді (мысалы, имитацияланған күйдіру, дифференциалды эволюция, бөлшектер тобын оңтайландыру) қамтиды. Кездейсоқ ретті түйінді жазу әдісі өшірілген блоктарды жасай алатыны сияқты, блокты жазу арқылы жасалған блоктарды өшіруге болады. (Осылайша, G қамту үшін радиусқа негізделген блок эвристикасы да, G қамту үшін диаметрге негізделген блок эвристикасы да ажыратылған блоктарды жасай алады.) Бұл 6-суреттегі желіде көрсетілген s = 3 үшін. Барлық бес түйін диаметрі 2 бірдей ұяшықта бола алмайды. Егер w бірінші кездейсоқ тұқым болса, онда бірінші өрісте u, v және w болады. Егер x екінші кездейсоқ тұқым ретінде таңдалса, құрамында x және y бар екінші өріс өшіріледі. x пен у-ны қосатын жалғыз жол бірінші өрістегі түйін арқылы болады. Бұл екі қорап G кем дегенде 3-мұқабасын құрайды. Дегенмен, бұл желі үшін және s = 3 үшін екі қосылған блокты пайдаланатын ең аз 3-мұқаба бар: бірінші блокқа x, y және u, ал v және w мәндерін блокқа қойыңыз. екінші блок. Қорапты жағу әдісін жүзеге асыру оңай болғанымен, оның орындалу уақыты шамадан тыс. Жылдамырақ ықшам қорапты жазу эвристикалық диаметрге негізделген қораптарды да пайдаланады. Алдымен, BD(s) = 0 инициализациясы. Шағын блоктың әрбір итерациясы Жазба келесі қадамдарды пайдаланып жабылмаған түйіндердің U жиынын өңдейді. (i) инициализация Z = ∅ мұндағы Z — G қамту аймағында жасалған келесі өрістегі түйіндер жиыны. U = N инициализациясы. BD(лар) санын 1-ге көбейтеміз. (ii) x ∈ U кездейсоқ түйінін таңдаңыз; Z-ке x-ті қосыңыз және U-дан x-ті алып тастаймыз, өйткені x енді Z түйіндер жиыны бар өріспен жабылған. (iii) Әрбір y ∈ U түйіні үшін, егер dist(x, y) ≥ s болса, онда x және U-дан y-ді алып тастаймыз. y екеуі де Z-ге тиесілі бола алмайды. (iv) U бос болғанша (ii) және (iii) қадамдарын қайталаймыз. U бос болғанда, Z-ге басқа түйін қосу мүмкін емес. Егер N бос болса, біз аяқталды. Егер N бос болмаса, шағын блок енгізуінің тағы бір итерациясы қажет. Осы жаңа итерацияны бастау үшін алдымен Z ішіндегі әрбір түйінді N ішінен алып тастаңыз, себебі бұл түйіндер енді жабылған. Енді (i) қадамнан қайталауды жалғастырамыз. Шағын блоктарды жазудың бірінші итерациясында (i) қадамда U = N инициализациялағанда, N жиыны G жүйесіндегі барлық түйіндердің бастапқы жиыны болып табылатынын ескеріңіз. Келесі итерацияларда N енді барлық түйіндердің бастапқы жиыны емес. G-де, өйткені әрбір дәйекті итерация N-дан Z-дегі әрбір түйінді жоюдан басталады. Ықшам блоктарды жазуға арналған псевдокод 6-суретте көрсетілген. Біз s = 2 үшін ықшам қорапты суреттейміз, қайтадан 6-суреттегі желіні пайдаланамыз. Сурет-8: Кездейсоқ дәйекті түйінді жазу хаб және сәулелік желіге қолданылады 1-итерация BD(2) = 0 инициализациялайды. Бірінші итерацияны бастау үшін U = N орнатамыз, BD(лар) көбейтіңіз (U бос емес болғандықтан, кем дегенде тағы бір өріс қажет) және бос Z жиынын жасаймыз. (ii) қадамда f пәрменін таңдаймыз. Z-ге f қосып, U-дан f-ны алып тастаймыз. (iii) a, b, c, d түйіндерін U түйінінен алып тастаймыз, себебі олардың f нүктесінен қашықтығы 1-ден үлкен. U бос емес болғандықтан, (ii) тармағына оралып, e параметрін таңдаймыз. . Z-ге e түйінін қосамыз, оны U-дан жоямыз және U-дан g түйінін алып тастаймыз, өйткені оның e-ден қашықтығы 1-ден үлкен. Енді U бос. Дәлелдеу: u және v түйіндеріне бірдей түс тағайындалды делік. Сонда u және v Gs доғасының соңғы нүктелері бола алмайды, өйткені егер олар болса, оларға әртүрлі түстер тағайындалған болар еді. Демек, dist(u, v) < s, сондықтан u және v диаметріне негізделген s өлшемді бір жәшікке орналастырылуы мүмкін. Бұл BD(s) ≤ χ(Gs) дегенді білдіреді. Кері теңсіздікті дәлелдеу үшін BD(s) блоктарын пайдаланып кез келген минималды s-қаптаманы қарастырамыз және B осы қақпақтағы кез келген блок болсын. Бұл өрістегі кез келген x және y түйіндері үшін бізде dist(x, y) < s бар, сондықтан x пен у Gs доғасымен қосылмаған. Осылайша, x және y бір түске тағайындалуы мүмкін, бұл χ(G s) ≤ BD(s) дегенді білдіреді. Біз суреттегі желіні пайдаланып түйінді бояу формуласын суреттейміз. s = 3 үшін G3 көмекші графигі суретте көрсетілген. 8.2(i). Доға (x, y) ішінде G3 бар, егер G-де dist(x, y) ≥ 3 болса ғана. Осылайша, c түйіні G3-те оқшауланған, өйткені оның G-дегі барлық басқа түйіндерге дейінгі қашықтығы аспайды. Сонымен қатар, G-дегі g-ден а-дан басқа барлық түйіндерге дейінгі қашықтық 2-ден аспайды, сондықтан доға (g, a) G3-те бар. Қарапайым желінің хроматикалық саны χ(G3) (8-сурет (i)) түйіндердің кездейсоқ реті негізінде түстерді тағайындайтын сараң бояу әдісі арқылы дәл есептеуге болады. Үлкен желілер үшін cараң бояу әдетте әртүрлі кездейсоқ түйін тапсырыстарын пайдалана отырып, бірнеше рет орындалады; 10 000 кездейсоқ тапсырысты пайдаланған кезде сараң бояуы айтарлықтай дәлдікті қамтамасыз етеді. Әдіс өте тиімді, өйткені түйіндердің берілген кездейсоқ реті үшін барлық түйіндер арқылы бір өту барлық блок өлшемдері үшін G s-мұқабасын есептеу үшін жеткілікті.
0 жүктеу/скачать 452,44 Kb. Достарыңызбен бөлісу:
|