Yashiklar prinsipi

1. Маршрутлар ва занжирлар ҳақида умумий маълумотлар. Учлари тўплами ва қирралар кортежи бўлган ориентирланмаган граф берилган бўлсин. Бу графдаги учлар ва қирраларнинг ҳар икки қўшни қирралари умумий четки учга эга

кўринишдаги чекли ёки чексиз кетма-кетлиги маршрут деб аталади. Маршрутни унинг учлари кетма-кетлиги ёки қирралари кетма-кетлиги кўринишда ҳам белгилаш мумкин.
Агар маршрутда қандайдир учдан олдин учлар бўлмаса, бу учни маршрутнинг бошланғич учи деб, шу учдан кейин маршрутга тегишли учлар бўлмаганда эса, уни маршрутнинг охирги учи деб атайдилар.
Агар маршрутнинг бошланғич учи ва охирги учи бўлса, у ҳолда уни учдан учга йўналган маршрут ёки четлари ва бўлган маршрут деб аталади.
Маршрутдаги иккита қошни қирраларга тегишли уч ички уч ёки оралиқ уч деб аталади.
Маршрутда қирралар ва учлар такрорланиши мумкин бўлгани учун маршрутнинг ички учи, бир вақтнинг ўзида, унинг бошланғич ва (ёки) охирги учи бўлиши ҳам мумкин ва тескариси, маршрутнинг бошланғич ва (ёки) охирги учи унинг ички учи бўлиши ҳам мумкин.
Табиийки, маршрут:
– бошланғич учга ҳам охирги учга ҳам эга бўлмаслиги мумкин (бундай маршрут икки томонлама чексиз маршрут деб аталади);
– бошлангич учга эга бўлиб, охирги учга эга бўлмаслиги мумкин ёки, аксинча, охирги учга эга бўлиб, бошлангич учга эга бўлмаслиги мумкин (бир томонлама чексиз маршрут);
– ягона қиррадан иборат бўлиши мумкин (нотривиал маршрут);
– бирорта ҳам қиррага эга бўлмаслиги мумкин (нол маршрут ёки тривиал маршрут).
Маршрутнинг узунлиги деб ундаги қирралар сонига айтилади.
Турли қирралардан ташкил топган маршрутга занжир деб аталади. Агар занжирнинг четларидан ташқари барча учлари турлича бўлса, у ҳолда уни оддий занжир деб атайдилар.
Берилган занжир ёки оддий занжир учун бўлса, у ёпиқ занжир деб аталади. Ҳеч бўлмаганда битта қиррага эга ёпиқ оддий занжир сикл деб аталади.
Сиртмоқ ёки бир жуфт каррали қирралар сикл ташкил этиши равшандир.
Тушунарлики, графдаги занжир графнинг қисм графи деб қаралиши мумкин.
Ориентирланган графлар учун ҳам ундаги ёйларнинг йўналишини (ориентатсиясини) инобатга олмасдан ориентирланмаган маршрут, занжир ва оддий занжир тушунчаларини киритиш мумкин. Лекин, ориентирланган графлар учун ориентирланган маршрут тушунчасини киритиш табиийдир.
Ёйларнинг ориентатсиялари ҳисобга олинган ёйлар ва учлар кетма-кетлиги ориентирланган маршрут деб аталади.
Ориентирланган маршрут учун занжир тушунчасига ўхшаш йўл (ёки ориентирланган занжир) тушунчасини ҳам киритиш мумкин. Бошланғич ва охирги учлари устма-уст тушадиган ориентирланган занжир контур деб аталади.