Yashiklar prinsipi

Глоссарий

Термин	Ўзбек тилидаги шархи
Эйлер занжири	ҳар бир қиррасидан фақат бир марта ўтадиган занжир
Эйлер граф	ёпиқ эйлер занжирига (жаъни эйлер циклига) эга граф.
Ярим эйлер графи	графда ёпиқ бўлмаган эйлер занжири топилса.
Гамилтон занжири	Графнинг ҳар бир учидан фақат бир марта ўтадиган занжир
Гамилтон графи	Ёпиқ Гамилтон занжирига (жаъни Гамилтон циклига) эга граф.
ярим Гамилтон графи	графда ёпиқ бўлмаган Гамилтон занжири

Графнинг метрик характеристикалари

Режа:

1. 
   Графларда масофа тушунчаси.
   
2. 
   Минимал узунликка эга йўл ҳақидаги масала.
   
3. 
   Дейкстра алгоритми.
   

Калит сўзлар: Граф, уч, қирра, учлар орасидаги масофа, занжир, оддий занжир, метрика аксиомалари, учбурчак тенгсизлиги, учнинг экссентриситети, графнинг диаметри, диаметрал занжир, графнинг радиуси, графнинг маркази, марказий уч, радиал оддий занжир, қирранинг (ёйнинг) узунлиги, аддитивлик, занжирнинг (йўлнинг) узунлиги, минимал узунликка эга йўл, Дейкстра алгоритми.

1. Графларда масофа тушунчаси. Боғламли граф берилган бўлсин. Бу графда ҳар қандай иккита ва учлар боғланган бўлгани учун четлари ва учлардан иборат бўлган ҳеч бўлмаса битта маршрут бор. ва учларни боғловчи энг қисқа маршрутнинг узунлиги ва учлар орасидаги масофа деб аталади ва у билан белгиланади. Равшанки, энг қисқа маршрут оддий занжирдир. Табиий равишда деб қабул қиламиз.
Шуни таъкидлаш керакки, графларда масофа тушунчасини бошқа усул билан ҳам аниқлаш мумкин.
Юқоридаги усул билан аниқланган масофа метрика аксиомалари деб аталувчи қуйидаги шартларни қаноатлантиради:
1) ;
2) бўлгандагина бўлади;
3) ;
4) .
Охирги аксиома учбурчак тенгсизлиги деб аталади.
Боғламли граф берилган бўлсин. графнинг ихтиёрий учи учун аниқланган

миқдор шу учнинг экссентриситети деб аталади.
Боғламли граф барча учларининг экссентриситетлари орасидаги қиймати энг каттаси (максимали) шу графнинг диаметри деб аталади.
графнинг диаметри, одатда, билан белгиланади: . Диаметр бу графнинг исталган икки учи орасидаги мумкин бўлган энг катта масофадир, яъни .
Узунлиги га тенг бўлган оддий занжир диаметрал занжир деб аталади. Табиийки, графда диаметрал занжир ягона бўлмаслиги мумкин.
Боғламли граф барча учларининг экссентриситетлари орасидаги қиймати энг кичиги (минимали) шу графнинг радиуси деб аталади.
графнинг радиуси, одатда, билан белгиланади: . Равшанки, .
Боғламли графдаги экссентриситети радиусга тенг уч графнинг маркази (марказий учи) деб аталади.
Агар уч графнинг маркази бўлса, у ҳолда бўлади, яъни графнинг марказий учи минимал экссентриситетга эгадир.
Агар графнинг марказидан бошқа бирор учигача бўлган оддий занжир энг узун масофага эга бўлса, у ҳолда бу занжир радиал оддий занжир деб аталади.
Табиийки, графнинг радиуси унинг диаметридан катта эмас ва граф биттадан кўп марказга эга бўлиши ҳам мумкин. Бундан ташқари, графнинг барча учлари унинг марказий учлари бўлиши ҳам мумкин.
Графнинг марказий учларини топиш билан боғлиқ масалалар аҳолига хизмат кўрсатадиган қандайдир объектнинг (касалхона, мактаб ва шу кабиларнинг) жойлашиш ўрнини аниқлаш билан боғлиқ муаммоларни ҳал қилишда қўлланилиши мумкин. Таъкидлаш керакки, муайян вазиятларда, кўпинча, бошқа ҳолатларни, жумладан, объектгача бориш вақти, пунктлар орасидаги масофа ва шу кабиларни ҳисобга олишга тўғри келади. Бундай вазиятларда жойлаштиришнинг минимакс масалалари деб аталувчи масалалар вужудга келади.