Кіріспе

Графикте ойналатын математикалық ойын. Графикті таспен жабу – графикада ойналатын математикалық ойын, онда әр төбесінде нөл немесе одан көп тас болуы мүмкін. Ойын, таспен жасалатын бірнеше қимылдан тұрады. Графикте таспен қимыл жасау үшін кем дегенде екі тасы бар төбе таңдалып, одан екі тас алынып, біреуі іргелес төбеге қосылады (екінші алынған тас ойыннан шығарылады). π(G), G графигінің таспен жабу саны, келесі шартты қанағаттандыратын ең кіші табиғи сан: Егер графикте кез келген мақсатты немесе "түбір" төбесі және n тастың бастапқы орналасуы берілсе, таспен жасалатын мүмкін бос қимылдар сериясынан кейін, белгіленген түбір төбесінде бір немесе бірнеше тас болатын жаңа орналасуға жетуге болады. Мысалы, екі төбесі және оларды байланыстыратын бір қабырғасы бар графикте, таспен жабу саны 2-ге тең. Екі тас графиктің төбелеріне қалай орналасқандығына қарамастан, таңдалған төбеде тас болуының қажетті нәтижесіне жету әрқашан мүмкін; егер бастапқы орналасуда әр төбеде бір тас болса, онда мақсатқа жету үшін таспен жасалған қимылдар қажет емес. Графикті таспен жабудың басты сұрақтарының бірі – берілген G графигі үшін π(G) мәні. Таспен жабудың басқа тақырыптарына қаптамамен жабу, ең оңтайлы жабу, үстемдікпен қаптамамен жабу, шектеулер және таспен жабу сандарының шегі, сондай-ақ терең графтар кіреді. Таспен жабу ойындарының бір қолданылуы – криптографиядағы жадқа төзімді функциялардың қауіпсіздік талдауында.

π ((G) графиктің қиыршықты саны

Пебблинг ойынын алғаш рет Лагариас пен Сакс сандар теориясындағы нақты бір мәселені шешу құралы ретінде ұсынды. 1989 жылы Ф. Р. К. Чунг осы түсінікті әдебиетке енгізіп, пебблинг саны π(G) деп атады. N төбесі бар толық граф үшін пебблинг саны n екенін оңай тексеруге болады: егер графқа (n - 1) тас қойылса, онда мақсатты төбеден басқа әр төбеге бір тас қоюға болады. Егер ешбір төбеде екі немесе одан көп тас болмаса, қозғалыс жасау мүмкін емес, демек мақсатты төбеге тас қоюға болмайды. Сондықтан, пебблинг саны n - 1-ден үлкен болуы керек. n тас берілген жағдайда екі мүмкіндік бар. Егер әр төбеде бір тас болса, қозғалыс қажет емес. Егер кез келген төбе бос болса, онда кем дегенде бір басқа төбеде екі тас болуы керек, ал бір тас қозғалысы толық графтың кез келген мақсатты төбесіне тас қоюға мүмкіндік береді.

Грэхамның қисынды болжамы

Рональд Грэмге графтардың декарт көбейтіндісінің тас түйреу саны, көбейтіндідегі факторлардың тас түйреу сандарының көбейтіндісінен артық емес деген болжамды жатқызылды. Бұл Грэмнің тас түйреу болжамы деп белгілі болды. 2019 жылға дейін ол шешілмеген күйде қалды, бірақ жеке жағдайлар белгілі.

γ(G) графиктің қаптамасының саны

Крулл және тағы басқалар қаптама тас себу концепциясын енгізді. γ(G), графтың қаптама тас себу саны – бастапқыда тастардың кез келген орналасуынан, бірқатар тас себу амалдарынан кейін графты жабу үшін қажетті ең аз тас саны: әрбір төбеде кем дегенде бір тас болуы керек. «Қабаттасу теоремасы» деп аталатын нәтиже кез келген граф үшін қаптама тас себу санын анықтайды.

Қоспалау теоремасы

Қоспалау теоремасына сәйкес, ең көп тас қаптамасын шешуге қажетті тастардың бастапқы орналасуы барлық тастар бір төбеге орналасқан кезде болады. Осы байқауға негізделіп, G графындағы әрбір v төбесі үшін, мұнда d(u, v) – u төбесінен v төбесіне дейінгі қашықтық болса, келесіні анықтаймыз:

Содан кейін қаптаманың тас саны – нәтижесінде алынған ең үлкен s(v) шамасы болады.