Yashiklar prinsipi
Download 0.89 Mb.
|
Graflar nazariyasi
- Bu sahifa navigatsiya:
- 7- теорема .
- Исботи .
|
6- теорема (Понтрягин-Куратовский). Граф планар бўлиши учун у ёки графга гомеоморф қисм графларга эга бўлиши зарур ва етарлидир.
Исботи топшириқ сифатида ўқувчига ҳавола қилинади. ■ 7- теорема. Агар каррали қирралари бўлмаган сиртмоқсиз графда та уч, та қирраи ва та боғламлилик компоненталари бўлса, у ҳолда қуйидаги муносабат ўринлидир: . Исботи. Аввал қирралар сони бўйича математик индуксия усулини қўллаб тенгсизликни исботлаймиз. Агар графда қирралар бўлмаса (яъни, математик индуксия усулининг базаси сифатида деб олинса), у ҳолда графдаги учлар сони унинг боғламлилик компоненталари сонига тенгдир: . Демак, бўлганда муносабат тўғридир. Индуксион ўтиш. Графдаги қирралар сонини билан белгилаб, бу сон минимал бўлсин, яъни графдан исталган қиррани олиб ташлаш амали боғламлилик компоненталари сони ўзгарган граф ҳосил қилсин деб фараз қиламиз. Бундан ташқари, математик индуксия усули талабига биноан учун исботланиши керак бўлган тенгсизлик ўринли бўлсин деб фараз қиламиз. Табиийки, бу ҳолда графдан исталган қиррани олиб ташласак (бунда олиб ташланган қирранинг четларидаги учлар графга тегишли бўлиб қолаверади), ҳосил бўлган графнинг учлари сони га, қирралари сони ( )га, боғламлилик компоненталари сони эса ( )га тенг бўлади. Индуксия фаразига биноан тенгсизлик ўринлидир. Бу тенгсизликдан келиб чиқади. Шундай қилиб, тенгсизлик исботланди. Енди тенгсизликни исботлаймиз. Бунинг учун графнинг ҳар бир боғламлилик компонентаси тўла граф бўлсин деб фараз қиламиз. Берилган графнинг учлари сонлари мос равишда ва бўлган иккита боғламлилик компоненталари ва графлардан иборат бўлсин, бу ерда . Тушунарлики, ва графларнинг учлари умумий сони ( )га тенгдир. Бу ва графларни учлари сонлари мос равишда ( ) ва ( ) бўлган тўла графлар билан алмаштирсак, учлар умумий сони ўзгармайди, лекин қирраларнинг умумий сони миқдорга ўзгаради. Охирги ифоданинг кўринишини қуйидагича ўзгартирамиз: . Шундай қилиб, учлари сони ва боғламлилик компоненталари сони бўлган графда максимал сондаги қирралар бўлиши учун у ( )та яккаланган учлар ва ( )та учга эга тўла граф бирлашмасидан ташкил топиши керак экан. Бу ердан исботланиши керак бўлган тенгсизлик келиб чиқади. ■ 7- теореманинг татбиқи сифатида қуйидаги тасдиқни келтирамиз. Download 0.89 Mb. Do'stlaringiz bilan baham: 
|