Yashiklar prinsipi

2. Гамилтон графлари. Графлар назариясининг натижалари муайян шартларни қаноатлантирувчи маршрутларни топиш масаласига келтирилувчи бир қатор муаммоларни ҳал этишда қўлланилиши мумкин. Шундай муаммолардан бири сифатида Уилям Гамилтон номи билан боғлиқ масалани келтирамиз. У. Гамилтон додекаедрни текшириб, унинг ҳар бир учидан фақат бир марта ўтадиган циклни излаб топган ва шу асосда 1859 йилда “Олам бўйлаб саёҳат” номли ўйинни топган.
Графнинг ҳар бир учидан фақат бир марта ўтадиган занжир Гамилтон занжири деб аталади. Ёпиқ Гамилтон занжирига (жаъни Гамилтон циклига) эга граф Гамилтон графи деб аталади. Агар графда ёпиқ бўлмаган Гамилтон занжири топилса, у ҳолда бундай граф ярим Гамилтон графи деб аталади.
Ориентирланган графларда ҳам графнинг ҳар бир учидан фақат бир марта ўтувчи ориентирланган циклларни қараш мумкин.
Эйлер ва Гамилтон графлари бир-бирларига ўхшаш таърифлансада, графнинг Гамилтон графи эканлигини тасдиқлайдиган аломат (мезон) топиш масаласи анча мураккаб муаммо ҳисобланади. Ҳозирги вақтгача графлар назариясида графнинг Гамилтон графи эканлигини тасдиқловчи шартларни ўрганиш бўйича изланишлар давом этиб, бу соҳадаги ишлар ҳанузгача долзарблигини йўқотмасдан келмоқда.
Қандайдир шартларга бўйсунувчи графларда Гамилтон цикли мавжудлиги ҳақида бир неча тасдиқлар мавжуд. Қатор ҳолларда бу тасдиқларнинг исботлари конструктив бўлганлигидан, Гамилтон циклини тузишга доир самарали алгоритмлар ҳам яратилган. 1952 йилда Г. Э. Дирак қуйидаги теоремани исботлади.
2- теорема (Дирак). Учлари сони учтадан кам бўлмаган графдаги исталган учнинг даражаси учлар сонининг ярмидан кам бўлмаса, бу граф Гамилтон графи бўлади.
Исботи. Учлари сони бўлган граф берилган бўлсин. Бу графнинг исталган учи учун шарт бажарилсада, у Гамилтон графи бўлмасин деб фараз қиламиз.
Табиийки, исталган графга етарлича сондаги янги учларни қўшиб олиб, бу учларнинг ҳар бирини графдаги ҳар бир уч билан қирра орқали туташтирсак, берилган графдан Гамилтон графини ҳосил қилиш мумкин. Бу усул билан берилган графдан Гамилтон графини ҳосил қилиш учун қўшилаётган зарур учларнинг минимал сонини билан белгилаймиз.
Юқорида баён қилинган усулни қўллаш натижасида ҳосил бўлган графдаги учлардан ташкил топган кетма-кетлик бирор Гамилтон цикли бўлсин, бунда , – берилган графнинг учлари, эса қўшиб олинган учлардан бири. Тушунарлики, уч учга қўшни эмас, акс ҳолда циклни тузишда учни ишлатмаслигимиз мумкин бўлар эди. Бу эса сонининг минималлигига зиддир.
Агар графдаги уч уч билан қўшни, уч эса уч билан қўшни бўлса, уч циклда учдан бевосита кейинги уч бўла олмайди, чунки бу ҳолда циклни циклга алмаштириш мумкин. Натижада ҳосил бўлган графнинг учга қўшни бўлмаган учлари сони учга қўшни учлари сонидан кичик эмаслиги (яъни бу сон камида га тенг эканлиги) равшан. Бошқа томондан эса ҳосил бўлган графнинг учга қўшни учлари сони камида га тенглиги кўриниб турибди. Ҳосил бўлган графнинг ҳар бир учи бир вақтнинг ўзида учга қўшни ҳам, қўшнимас ҳам бўлиши мумкин эмаслигидан ҳосил бўлган граф учларининг умумий сони ( ) ушбу сондан кичик эмас, яъни . Охирги тенгсизлик фақат бўлгандагина тўғридир. Бу эса шартига зиддир. ■