Yashiklar prinsipi

Термин
Ўзбек тилидаги шархи
Граф	жуфтликка айтиладики, бу ерда ва – ( , ) кўринишдаги жуфтликлар кортежи бўлиб, тўпламнинг элементларидан тузилган тўплам.
Графнинг учлари	графда тўпламнинг элементлари.
Йўналтирилмаган (ориентирланмаган) қирра	бўладиган жуфтлик.
Қўшни қирралар	умумий четга эга бўлган иккита қирра (ёй).
Сиртмоқ	графнинг элементи

Графларнинг берилиш усуллари

Режа:

1. 
   Графнинг геометрик ифодаланиши.
   
2. 
   Графнинг махсус турдаги кўпҳад ёрдамида берилиши.
   
3. 
   Қўшнилик матритсалари.
   
4. 
   Инсидентлик матритсалари.
   

Калит сўзлар: Граф, орграф, уч, қирра, ёй, сиртмоқ, каррали қирралар, учнинг лоcал даражаси, мултиграф, кўпҳад, графнинг учлари қўшнилиги матритсаси, ориентирланмаган мултиграфнинг учлари қўшнилиги матритсаси, ориентирланган графнинг учлари қўшнилиги матритсаси, сиртмоқсиз орграф учлари қўшнилиги матритсаси, графнинг қирралари қўшнилиги матритсаси, инсидентлик матритсаси.
1. Графнинг геометрик ифодаланиши.
Графларнинг турлича берилиш усуллари мавжуд. Графнинг абстракт математик таърифи унинг берилиш усулларидан биридир. Графнинг абстракт математик таърифи уни тасаввур қилиш, англаш, унинг хоссаларини ўрганиш ва бу хоссаларни амалда қўллаш жараёнида баъзи қийинчиликлар туғдириши табиийдир. Шунинг учун графнинг бошқа берилиш усулларидан ҳам фойдаланилади. Масалан, графнинг элементларини, яъни учлари ва қирраларини (ёйларини) ёзиш ёки айтиш графнинг берилиш усули сифатида қаралиши мункин. Албатта, графнинг яна бошқа берилиш усуллари ҳам мавжуд. Қуйида бу усулларнинг бир нечаси билан танишамиз.
Графнинг учларини текисликда ёки фазода нуқталар билан, қирраларини (ёйларини) эса мос учларни туташтирувчи узлуксиз чизиқлар билан ифодалаб, қандайдир диаграммага – графнинг кўргазмали тасвирига эга бўламиз. Агар учлар тўплами ва бу учларнинг туташишларини кўргазмали қилиб тақдим қилиш керак бўлса, графнинг геометрик тасвирланишига мос шаклни қоғозда чизиб графни тасвирлаш мумкин.
Шуни таъкидлаймизки, баъзи ҳолларда диаграммада граф учлари доирачалар ёрдамида ёки қандайдир бошқа усулда ифодаланади. Графнинг қирраларига (ёйларига) мос чизиқларнинг тўғри ёки эгри бўлиши ва уларнинг узунлиги аҳамиятга эга эмас. Муҳими, бу чизиқлар узлуксиз бўлиб, графнинг қандайдир иккита учларини туташтириши лозим. Агар қирра йўналишга эга бўлса (яъни у ёй бўлса), у ҳолда бундай қиррани ифодаловчи чизиқда йўналиш бирор усул билан, масалан, стрелка билан кўрсатилади.
Ихтиёрий граф учун бундай диаграммаларни исталганча тузиш мукинлиги равшан. Агар бирор диаграммада графнинг учларига мос келувчи нуқталар устма-уст тушмаса, қирраларга мос келувчи чизиқлар, четки нуқталарни ҳисобга олмаганда, умумий нуқталарга эга бўлмаса, бундай диаграмма графнинг геометрик ифодаланиши дейилади. Шуни таъкидлаш керакки, битта граф турлича геометрик ифодаланиши мумкин.
Графлар изоморфлигининг таърифи ва графни геометрик ифодалашнинг моҳиятидан келиб чиқадики, абстракт таъриф ёрдамида ифодаланган граф ва унинг геометрик ифодаланиши ўзаро изоморф бўлади. Табиийки, изоморф графлар турлича геометрик ифодаланишлари мумкин.