Yashiklar prinsipi

2. Grafning abstract ta`rifini va u bilan bog`liq boshlang`ich tushunchalar.
Avvalo, grafning abstract matematik tushuncha sifatidagi ta`rifini va boshqa ba`zi soda tushunchalarni keltiramiz. qandaydir bo`shmas to`plam bo`lsin. Uning va elementlaridan tuzilgan ko`rinishdagi barcha juftliklar (kortejlar) to`plamini ( to`plamning o`z-o`ziga Dekart ko`paytmasini) bilan belgilaymiz.
Graf deb shunday juftlikka aytiladiki, bu yerda va – ( , ) ko`rinishdagi juftliklar korteji <sup>1</sup> bo`lib, to`plamning elementlaridan tuzilgandir.
Bundan buyon grafni belgilashda yozuv o`rniga yozuvdan foydalanamiz. Grafning tashkil etuvchilarini ko`rsatish muhim bo`lmasa, u holda uni lotin alifbosining bitta harfi, masalan, bilan belgilaymiz.
graf berilgan bo`lsin. тўпламнинг элементларига графнинг учлари, тўпламнинг ўзига эса, граф учлари тўплами дейилади.
Графлар назариясида “уч” ибораси ўрнига, баъзан, тугун ёки нуқта ибораси ҳам қўлланилади. Умуман олганда, ҳанузгача графлар назариясининг баъзи иборалари бўйича умумий келишув қарор топмаган. Шунинг учун, бундан кейинги таърифларда, имконият борича, муқобил (алтернатив) ибораларни ҳам келтиришга ҳаракат қиламиз.
графнинг таърифига кўра, бўш кортеж бўлиши ҳам мумкин. Агар бўш бўлмаса, у ҳолда бу кортеж ( , ) кўринишдаги жуфтликлардан² ташкил топади, бунда бўлиши ҳамда ихтиёрий жуфтлик кортежда исталганча марта қатнашиши мумкин.
жуфтликни ташкил этувчи ва учларнинг жойлашиш тартибидан боғлиқ ҳолда, яъни йўналишнинг борлиги ёки йўқлигига қараб, уни турлича аташ мумкин. Агар жуфтлик учун уни ташкил этувчиларнинг жойлашиш тартиби аҳамиятсиз, яъни бўлса, жуфтликка йўналтирилмаган (ориентирланмаган) қирра (ёки, қисқача, қирра) дейилади. Агар бу тартиб муҳим, яъни бўлса, у ҳолда жуфтликка ёй ёки йўналтирилган (ориентирланган) қирра дейилади.
кортежнинг таркибига қараб, уни ё графнинг қирралари кортежи, ё ёйлари кортежи, ёки қирралари ва ёйлари кортежи деб атаймиз.
Графнинг учлари ва қирралари (ёйлари) унинг элементлари деб аталади. граф элементларининг сони ( )га тенгдир, бу ерда графнинг учлари сони ва билан унинг қирралари (ёйлари) сони белгиланган.
Графнинг қирраси (ёйи), одатда, уни ташкил этувчи учлар ёрдамида , ёки , ёки кўринишда белгиланади. Бошқа белгилашлар ҳам ишлатилади: масалан, ёй учун ёки , қирра учун , ёй ёки қирра учун (яъни учлари кўрсатилмасдан битта ҳарф воситасида) кўринишда.
Граф ёйи учун унинг четки учларини кўрсатиш тартиби муҳим эканлигини таъкидлаймиз, яъни ва ёзувлар бир-биридан фарқ қилувчи ёйларни ифодалайди. Агар ёй кўринишда ифодаланган бўлса, у ҳолда унинг бошланғич учи, эса охирги учи деб аталади. Бундан ташқари, ёй кўринишда ёзилса, у ҳақида учдан чиқувчи (бошланувчи) ва учга кирувчи (учда туговчи) ёй деб айтиш ҳам одат тусига кирган.
Қирра учун унинг ёзувидаги ҳарфлар жойлашиш тартиби муҳим рол ўйнамайди ва ва элементлар қирранинг учлари ёки четлари деб аталади.
Агар графда ё қирра, ё ёй, ёки ёй топиллса, у ҳолда ва учлар туташтирилган дейилади. Агар графнинг иккита учини туташтирувчи қирра ёки ёй бор бўлса, у ҳолда улар қўшни учлар деб, акс ҳолда эса, қўшни бўлмаган учлар деб айтилади.
Графнинг иккита учи қўшни бўлса, улар шу учларни туташтирувчи қиррага (ёйга) инсидент, ўз навбатида, қирра ёки ёй бу учларга инсидент дейилади.
Графда иккита қирра (ёй) умумий четга эга бўлса, улар қўшни қирралар (ёйлар) дейилади.
Шуни таъкидлаш керакки, қўшнилик тушунчаси графнинг бир жинсли, инсидентлик тушунчаси эса унинг турли жинсли элементлари орасидаги муносабатни ифодалайди.
Баъзан граф ундаги элементлар сонига қараб, яъни учлар сони ва қирралар (ёйлар) сони га қараб белгиланади ва бу ҳолда графни -граф деб атайдилар.
Агар графда кортеж фақат қирралардан иборат бўлса, у ҳолда йўналтирилмаган (ориентирланмаган) ва фақат йўналтирилган (ориентирланган) қирралардан (яъни, ёйлардан) ташкил топган бўлса, у ҳолда у йўналтирилган (ориентирланган) граф деб аталади. Ориентирланган граф, қисқача, орграф деб ҳам аталади.
Қатор ҳолларда ориентирланмаган қирралари ҳам, ориентирланган қирралари ҳам бўлган графлар билан иш кўришга тўғри келади. Бундай графлар аралаш графлар деб аталади.
Агар графнинг (орграфнинг) кортежи таркибида тўпламдан олинган такрорланувчи элементлар бўлса, у ҳолда улар каррали ёки параллел қирралар (ёйлар) деб аталади. Каррали қирралари ёки ёйлари бўлган граф мултиграф дейилади.
Иккала четки (бошланғич ва охирги) учлари устма-уст тушган қирра (ёй), яъни графнинг элементи сиртмоқ деб аталади. Сиртмоқ, одатда, йўналтирилмаган деб ҳисобланади. Қирралари (ёйлари) орасида сиртмоқлари бўлган граф псевдограф дейилади.
Умумий ҳолда учлар тўплами ва (ёки) қирралар (ёйлар, қирра ва ёйлар) кортежи чексиз кўп элементли бўлиши мумкин. Бундан кейин тўплам ва кортеж фақат чекли бўлган графларни қараймиз. Бундай графлар чекли графлар деб аталади.
Ҳеч қанақа қирра (ёй) билан боғланмаган уч яккаланган (ажралган, холис, ялонғоч) уч деб аталади.
Фақат яккаланган учлардан ташкил топган граф (яъни, графда қирралар ва ёйлар бўлмаса) нолграф ёки бўш граф деб аталади. Учлари сони га тенг бўлган бўш графни ёки каби белгилаш қабул қилинган.
Исталган иккита учлари қўшни бўлган сиртмоқсиз ва каррали қирраларсиз ориентирланмаган граф тўла граф деб аталади. Учлари сони га тенг бўлган тўла граф билан белгиланади. Равшанки, графнинг қирралар сони бўлади.
Агар орграфнинг исталган иккита учини ҳар бир йўналишда туташтирувчи фақат биттадан ёй мавжуд бўлса, у ҳолда унга тўла орграф деб аталади. Равшанки, тўла графдаги қирраларнинг ҳар бирини иккита (йўналишлари бир-бирига қарама-қарши бўлган) ёйларга алмаштирилса, натижада тўла орграф ҳосил бўлади. Шунинг учун, тўла орграфдаги ёйлар сони ориентирланмаган тўла графдаги қирралар сонидан икки баравар кўпдир, яъни учлари та бўлган тўла орграфдаги ёйлар сони бўлади.
Агар графнинг учларига қандайдир белгилар, масалан, сонлари мос қўйилган бўлса, у белгиланган граф деб аталади.
Агар ва графларнинг учлари тўпламлари, яъни ва тўпламлар орасида учларнинг қўшнилик муносабатини сақлайдиган ўзаро бир қийматли мослик ўрнатиш мумкин бўлса, у ҳолда ва графлар изоморф графлар деб аталади. Бу таърифни қуйидагича ҳам ифодалаш мумкин: агар ва уларга мос бўлган ( , ) учун ( , ) бўлса, у ҳолда ва графлар изоморфдир. Агар изоморф графлардан бири ориентирланган бўлса, у ҳолда иккинчиси ҳам, албатта, ориентирланган бўлиши ва улардаги мос ёйларнинг йўналишлари ҳам бир-бирларига мос бўлишлари шарт.
Граф учига инсидент қирралар сони шу учнинг локал даражаси, ёки, қисқача, даражаси, ёки валентлиги деб аталади. Графдаги учнинг даражасини билан белгилаймиз.
Сиртмоққа инсидент бўлган учнинг даражасини аниқлашда шуни эътиборга олиш керакки, қаралаётган масалага боғлиқ ҳолда сиртмоқни битта қирра деб ҳам, иккита қирра деб ҳам ҳисоблаш мумкин. Равшанки, ажралган учнинг даражаси нолга тенг. Даражаси бирга тенг уч четки (ёки осилган) уч деб аталади. Четки (осилган) учга инсидент қирра ҳам четки (ёки осилган) қирра деб аталади.
Агар графнинг барча учлари бир хил даражага эга бўлса, у ҳолда бундай граф даражали регуляр граф деб аталади. Уч даражали регуляр граф кубик (ёки уч валентли) граф деб аталади. граф нол даражали регуляр граф эканлигини, эса ( ) даражали регуляр граф эканлигини таъкидлаймиз.
Кўриниб турибдики, ориентирланмаган графда барча учлар даражаларининг йиғиндиси қирралар сонининг икки бараварига тенг жуфт сон бўлади, чунки қирраларни санаганда ҳар бир қирра ҳисобда икки марта қатнашади. Шундай қилиб, XVIII асрдаёқ Л. Эйлер томонидан исботланган қуйидаги тасдиқ ўринлидир.