Yashiklar prinsipi

1- мисол. 1- шаклда тасвирланган графни қараймиз. Бу гҳафда , , ; ва занжирлар диаметрал занжирлардир, ва занжирлар эса диаметрал занжирдирлар бўла олмайди. Берилган графда 4, 5 ва 6 белгили учлар марказлар бо ълиб, ҳамда ва радиал оддий занжирлардир. ■
2. Минимал узунликка эга йўл ҳақидаги масала. Берилган боғламли графнинг ҳар бир қиррасига (агар берилган граф ориентирланган бўлса – ёйига) қандайдир ҳақиқий сон мос қўйиб, бу сонни қирранинг (ёйнинг) узунлиги деб атаймиз. Қирранинг (ёйнинг) узунлиги аддитивлик хоссасига эга деб фараз қиламиз, яъни қирралар (ёйлар) ёрдамида тузилган занжирнинг (йўлнинг) узунлиги шу занжирни (йўлни) ташкил этувчи қирралар (ёйлар) узунликлари йиғиндисига тенгдир.
Табиийки, қирранинг ёки ёйнинг узунлиги тушунчаси ечилаётган масаланинг моҳиятига қараб муайян бир маънога эга бўлиши мумкин. Масалан, иккита шаҳар орасидаги масофа, қандайдир операцияни бажариш учун зарур маблағ (харажатлар) ёки вақт ва бошқалар. Шу нуқтаи назардан, умуман олганда, бу ерда манфий узунликка эга ёки узунлиги нолга тенг қирра (ёй) ҳам маънога эга деб ҳисобланади.
Амалиётда учрайдиган кўплаб масалаларда маршрут узунлиги максималлаштирилиши ёки минималлаштирилиши талаб этилади. Шундай масалалардан бирига, аниқроғи, коммивояжер масаласига Гамилтон графлари билан шуғулланганда дуч келган эдик.
ориентирланган граф берилган бўлсин, бу ерда . графнинг бирор учидан бошқа учига борувчи йўллар орасида узунлиги энг кичик бўлганини топиш масаласи билан шуғулланамиз. Бу масалани минимал узунликка эга йўл ҳақидаги масала деб атаймиз. Қуйида бу масаланинг умумлашмаси ҳисобланган масалани қараб, уни ҳам ўша ном билан атаймиз.
Графдаги ёйнинг узунлигини билан белгилаб, , матрица берилган деб ҳисоблаймиз. Юқорида таъкидлаганларимизга кўра, матрицанинг элементлари орасида манфийлари ёки нолга тенглари ҳам бўлишлари мумкин. Агар графда бирор учдан чиқиб учга киррувчи ёй мавжуд бўлмаса, у ҳолда бу ёйнинг узунлигини чексиз катта деб қабул қиламиз ( ). Бундан ташқари, графда умумий узунлиги манфий бўлган сикл мавжуд эмас деб ҳисоблаймиз, чунки акс ҳолда узунлиги энг кичик бўлган йўл мавжуд эмас⁵.