Yashiklar prinsipi

Маршрутлар ва занжирлар

Режа:

1. 
   Маршрутлар ва занжирлар ҳақида умумий маълумотлар.
   
2. 
   Графнинг боғламлилиги тушунчаси.
   
3. 
   Асосий теоремалар.
   

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

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