Yashiklar prinsipi

Глоссарий

Термин	Ўзбек тилидаги шархи
Маршрут	графдаги учлар ва қирраларнинг ҳар икки қўшни қирралари умумий четки учга эга кўринишдаги чекли ёки чексиз кетма-кетлиги графдан қиррани иккига бўлиш амалини чекли марта кетма-кет қўллаш воситасида ҳосил қилинган граф
Бошланғич учи	маршрутда қандайдир учдан олдин учлар мавжуд бўлмаган уч.
Охирги учи	шу учдан кейин маршрутга тегишли учлар бўлмаган уч
Йўналган маршрут	Агар маршрутнинг бошланғич учи ва охирги учи бўлса, у ҳолда уни учдан учга йўналган маршрут.
Икки томонлама чексиз маршрут	бошланғич учга ҳам охирги учга ҳам эга бўлмаган маршрут.
Тривиал маршрут	бирорта ҳам қиррага эга бўлмаган маршрут.

Дарахтлар

Режа:

1. 
   Дарахт ва унга эквивалент тушунчалар.
   
2. 
   Теорема ва натижалар.
   
3. 
   Графнинг Цикломатик сони.
   

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

1- мисол. 1- шаклда боғламли компонентали сони бешга тенг бўлган граф тасвирланган бўлиб, у ўрмондир. Бу графдаги боғламли компоненталарнинг ҳар бири дарахтдир. ■
2- мисол. 2- шаклда тўртта учга эга бир-бирига изоморф бўлмаган барча (улар бор-ёғи иккита) дарахтларнинг геометрик ифодаланиши тасвирланган. ■
Бешта учга эга бир-бирига изоморф бўлмаган барча дарахтлар учта, олтита учга эга бундай барча дарахтлар эса олтита эканлигини кўрсатиш қийин эмас.
Дарахт тушунчасига бошқача ҳам таъриф бериш мумкин. Умуман олганда, - граф учун дарахтлар ҳақидаги асосий теорема деб аталувчи қуйидаги теорема ўринлидир.
1- теорема. Учлари сони ва қирралари сони бўлган граф учун қуйидаги тасдиқлар эквивалентдир:
1) дарахтдир;
2) аЦикликдир ва ;
3) боғламлидир ва ;
4) боғламлидир ва ундан исталган қиррани олиб ташлаш амалини қўллаш натижасида боғламли бўлмаган граф ҳосил бўлади, яъни нинг ҳар бир қирраси кўприкдир;
5) графниннг ўзаро устма-уст тушмайдиган исталган иккита учи фақат битта оддий занжир билан тутаҳтирилади;
6) аЦиклик бўлиб, унинг қўшни бўлмаган иккита учини қирра билан туташтириш амалини қўллаш натижасида фақат битта Циклга эга бўлган граф ҳосил бўлади.