Кіріспе

Кесісулерден аулақ болудың математикалық жұмбағы

Су, газ және электр энергиясы деп аталатын классикалық математикалық жұмбақ, жазықтықта үш үй мен үш коммуналдық компания арасында кесіспейтін байланыстарды табуды сұрайды. ХХ ғасырдың басында Генри Дудени бұл мәселені бұрыннан белгілі проблема деп жазған. Бұл орындалмайтын жұмбақ: тоғыз сызықты қиылыстарсыз жалғастыру мүмкін емес. Тор немесе Мёбиус жолағы сияқты жазық емес беттердегі мәселенің нұсқалары, немесе басқа үйлер мен коммуналдық қызметтер арқылы өтуге рұқсат беретін нұсқалары шешіледі. Бұл жұмбақты топологиялық граф теориясының мәселесі ретінде формалдауға болады, яғни үйлер мен коммуналдық қызметтерді көрсететін төбелері және олардың байланыстарын көрсететін жиектері бар толық екі жақты графтың жазықтықта бейнеленуіне қатысты сұрақ туындайды. Жұмбақтың орындалмауының себебі – бұл граф жазық емес. Бұл мүмкін еместіктің бірнеше дәлелдемелері белгілі және олар Куратовский теоремасының дәлелдемесінің бір бөлігін құрайды, бұл теорема екі тыйым салынған кішіграф арқылы жазық графтарды сипаттайды, олардың бірі – толық екі жақты графтардың сызбаларындағы кесісулер санын азайту мәселесі Туранның кірпіш фабрикасы проблемасы ретінде белгілі, ал ең аз кесісулер саны – бір. Бұл алты төбесі және тоғыз жиегі бар граф, ол көбінесе мәселеге қатысты пайдалы граф деп аталады. Ол сондай-ақ 19 ғасырдың химигі Джулиус Томсеннің құрметіне Томсен графы деп те аталады. Бұл жақсы жабылатын граф, ең кішкентай үшбұрышсыз кубтық граф және ең кішкентай жазық емес, минималды қатты граф.

Тарих

Үш коммуналдық қызмет проблемасының тарихын қарастырып, автор оны "өте ежелгі" деп сипаттайды. Кульман тапқан ең ерте жарияланымда бұл проблема "су, газ және электр энергиясы" деп аталған. Алайда, Дюденей бұл мәселенің "электр жарығынан да, тіпті газдан да ескі" екенін айтады. Дюденей осы жұмбақты бұрын, 1913 жылы The Strand Magazine журналында жариялаған. Біріншілік туралы таласқа Сэм Лойд да үміткер, оның ұлы жариялаған естеліктерде ол осы мәселені 1900 жылы жариялағаны айтылған. Проблеманың тағы бір ерте нұсқасы үш үйді үш құдыққа қосуды қарастырады. Бұл басқа (шешімі бар) жұмбаққа ұқсас, онда үш үй және үш бұрқақ бар, барлық үш бұрқақ пен бір үй тіктөртбұрышты қабырғаға жанасады; жұмбақта да қиылыспайтын қосылыстар жасау қажет, бірақ тек үш үй мен құдықтардың немесе бұрқақтардың белгіленген жұптары арасында, қазіргі заманғы сандық байланыс жұмбақтарындағыдай. Лойдтың "Даулы көршілер" жұмбағы да үш үйді үш қақпаға үш қиылыспайтын жолмен қосуды қарастырады (коммуналдық қызметтер проблемасындағыдай тоғыз емес); бір үй және үш қақпа тіктөртбұрышты ауланың қабырғасында орналасқан, ал қалған екі үй ауланың ішінде. Үш коммуналдық қызмет проблемасындағыдай, граф 19-шы ғасырдың соңы мен 20-шы ғасырдың басындағы жарияланымдарда, сондай-ақ құрылымдық беріктіктің және химиялық графтар теориясының алғашқы зерттеулерінде кездеседі, онда Джулиус Томсен оны 1886 жылы бензолдың құрылымының сол кездегі белгісіздігі үшін ұсынған. Томсеннің еңбегінің құрметіне граф кейде Томсен графы деп аталады.

Ерітпеушілік

Әдетте ұсынылғандай (жас екі өлшемді жазықтықта), пайдалы жұмбақтың шешімі "жоқ": бір-бірімен қиылыспай тоғыз байланысты жасаудың жолы жоқ. Басқаша айтқанда, граф жазық емес. Казимеж Куратовский 1930 жылы оның жазық емес екенін мәлімдеді, одан проблеманың шешімі жоқ екендігі көрінеді. Дегенмен, "Қызықтайтыны, Куратовский [ ] жазық емес екендігін дәлелдеудің толық нұсқасын жарияламады". Графты жазық түрде бейнелеудің мүмкін еместігін дәлелдеудің бір жолы Иордания қисық теоремасын қолданатын жағдайды талдау болып табылады. Бұл шешімде графтың 4 циклына қатысты төбелердің орналасуының әртүрлі мүмкіндіктері қарастырылады және олардың барлығы жазық бейнелеуге сәйкес келмейтіні көрсетіледі. Сонымен қатар, кез келген көпірсіз екі жақты жазық графтың *n* төбесі және *m* жиегі болса, Эйлер формуласын (*F* – жазық бейнелеудегі беттер саны) қолданып, *F* = *m* - *n* + 2 екенін көрсетуге болады. Беттер саны жиектер санының жартысынан аспайды (әр беттің төбелері үйлер мен коммуналдық қызметтер арасында кезектесіп орналасуы керек, сондықтан әр бетте кем дегенде төрт жиек болады, ал әр жиек дәл екі бетке тиесілі). Пайдалылық графында *n* және *m* сондықтан пайдалылық графында бұл теңсіздік орындалмайды, демек пайдалылық графы жазық бола алмайды.

Ережелерді өзгерту

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

Пайдалылық графигінің қасиеттері

Пайдалы жұмбақтан өзге, осы график бірнеше басқа математикалық контексттерде де кездеседі, оның ішінде қаттылық теориясы, торлар мен жақсы жабылған графиктерді жіктеу, графиктің қиылысу сандарын зерттеу және графиктің кішігелеулері теориясы.

Қаттылық

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

Басқа графтық-теориялық қасиеттер

үшбұрышсыз график, онда әрбір төбеде дәл үш көрші бар (кубтық график). Мұндай графиктердің арасында бұл ең кішісі. Сондықтан бұл (3,4) қақпақ, яғни әрбір төбесінде үш көршісі бар және ең қысқа циклдің ұзындығы төртке тең болатын ең кішкентай график. Барлық басқа толық екі бөлікті графиктер сияқты, бұл жақсы жабылған график, яғни кез келген максималды тәуелсіз жиынның мөлшері бірдей. Осы графикте екі ғана максималды тәуелсіз жиын бар – екі бөліктің екі жағы, және олардың мөлшері тең. Бұл 3-ретті, 3-байланысқан, жақсы жабылған графиктердің тек жеті графигінің бірі.

Жалпылау

Жазық графиктердің екі маңызды сипаттамасы – Куратовский теоремасы, онда жазық графиктер дәл сол графиктер екені айтылады, оларда толық график пен толық график бөлшектенген түрінде де кездеспейді, және Вагнер теоремасы, онда жазық графиктер дәл сол графиктер екені айтылады, оларда толық график пен толық график кішігірім түрінде де кездеспейді. Бұл теоремалар Пал Туранның "кірпіш фабрикасы" мәселесінің жазық еместігін пайдаланады және жалпылайды. Пал Туранның "кірпіш фабрикасы" мәселесі екі бөлікке бөлінген толық графты салу кезіндегі қиылыстардың ең аз санын екі бөліктің төбелерінің санына қарай анықтау формуласын табуға бағытталған. Пайдалы графты тек бір қиылыспен салуға болады, бірақ ешқандай қиылыссыз салу мүмкін емес, сондықтан оның қиылыс саны бірге тең.