O’ZBEKISTON RESPUBLIKASI RAQAMLI
TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI
RIVOJLANTIRISH
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT
AXBOROT TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI
TELEKOMMUNIKATSIYA TEXNOLOGIYALARI FAKULTETI
RI 11 23 GURUH TALABASINING
DISKRIT TUZULMALAR fanidan
5-MUSTAQIL ISHI
Bajardi Xolturayev.A
.
Qabul qildi: Xo'jayev L.
Reja:
1.
Grafda zanjir, marshrut, sikl tushunchalari. Eyler, Gamilton sikllari va
graflari.
2.
To’la grafda Gamilton sikllari sonini hisoblash formulasi. Kommivoyajer
masalasi,
3.
Graf ostov daraxti, uni qurish tartibi.
4.
Graf uchlari va qirralarini bo’yash. Graf siklomatik soni va sinfini aniqlash.
5.
Daraxt uchlari va shoxlari soni orasidagi munosabat. O’rmon, undagi
daraxtlar sonini aniqlash formulasi.
6.
Oriyentirlangan graflar uchun insidensiya matritsasi.
Narxlangan grafda
arzon marshrutni aniqlash
Teorema (Eyler 1752)
.
Tekis va bog‘lamli graf uchun tenglik o‘rinlidir, bu yerda ,
, – yoqlar soni.
Isboti.
Teoremani isbotlash uchun matematik induksiya usulini grafdagi qirralar
soni bo‘yicha qo‘llaymiz. Induksiya usulining bazasi sifatida bo‘lgan holni
qaraymiz. Bu holda teoremaning tasdig‘iga ko‘ra bo‘lishi kerak. Haqiqatdan ham,
tekis va bog‘lamli graf bo‘lgani uchun, u yagona uchdan tashkil topadi va bu uch
yagona (cheksiz) yoqda yotadi, ya’ni va . Demak, bu holda teoremaning tasdig‘i
to‘g‘ridir.
Induksion o‘tish: teoremaning tasdig‘i uchun to‘g‘ri bo‘lsin deb faraz qilib, uning
uchun ham to‘g‘ri ekanligini ko‘rsatamiz. Farazimizga ko‘ra tenglik o‘rinlidir. ta
qirraga ega tekis va bog‘lamli grafga ( )- qirrani (uni bilan belgilaymiz) shunday
qo‘shish kerakki, bunda qirra graf joylashgan tekislikda yotsin va hosil bo‘lgan
graf ham bog‘lamli bo‘lsin. Bu amalni bajarganda quyidagi uchta holdan biri ro‘y
beradi:
1) qo‘shilayotgan qirra sirtmoqdir – bu holda qirra, albatta, grafdagi uchlardan
biriga insident bo‘lib, yoqlardan birida yotadi va bu yoqni ikkiga (sirtmoq yotgan
yoqning sirtmoq chizig‘i bilan chegaralangan ichki va tashqi qismlari) ajratadi,
ya’ni uchlar soni o‘zgarmaydi, yoqlar soni esa birga oshadi: ;
2) qo‘shilayotgan qirra grafda bor bo‘lgan ikkita uchlarni tutashtiradi – bu holda
ham grafning biror ( qirra yotgan) yoqi ikkiga ajraladi,
uchlari soni esa
o‘zgarmaydi: ;
3) qo‘shilayotgan qirra sirtmoq emas va u grafdagi uchlardan faqat bittasiga
insidentdir – bu holda grafning biror yoqida qirraga insident bo‘lgan bitta boshqa
uch yasaladi (grafning uchlari soni bittaga oshadi) va qirra joylashgan yoq
yaxlitlikni saqlagan holda qirrani o‘z ichiga oladi (yoqlar soni o‘zgarmaydi): .
Teoremaning tasdig‘idagi tenglik
