|
O’zbekiston respublikasi raqamli texnologiyalari va kommunikatsiyalarini rivojlantirish
|
| bet | 2/2 | | Sana | 20.05.2024 | | Hajmi | 394,81 Kb. | | #246866 |
Bog'liq diskret 5Eyler formulasi deb ataladi.
Eyler formulasi stereometriyada ham qo‘llaniladi: uchlari ta, yoqlari ta va qirralari ta ixtiyoriy ko‘pyoqli uchun Eyler formulasi o‘rinlidir. Bu tasdiqning negizida isboti o‘quvchiga havola qilinayotgan quyidagi tasdiq yotadi: stereometriyada berilgan ta’rifga ko‘ra aniqlangan ixtiyoriy ko‘pyoqliga mos tekis izomorf graf mavjuddir.
Eyler teoremasidan bir qator natijalar kelib chiqadi. Masalan, bu teoremadan foydalanib uni osonlik bilan bog‘lamli bo‘lmagan graflar uchun quyidagicha umumlashtirish mumkin. Agar bog`liqli grafda barcha uchlar juft bo`lsa, bu graf eyler sikliga ega bo`ladi.
Teskari tasdiq ham o`rinli: agar graf eyler sikliga ega bo`lsa, uning barcha uchlari darajalari juft bo`ladi.
Misol.
Agar grafda oddiy cikl mavjud bo`lib, bu ciklda grafning barcha uchlari qatnashsa, bunday sikl Gamilton sikli deyiladi. Oddiy zanjir Gamilton zanjiri deyiladi, agar bunday grafda uchlarning hammasi ishtirok etsa. Boshqacha aytganda, agar zanjir grafning barcha uchlaridan bir martadan o`tsa, bunday zanjirga gamilton zanjiri deyiladi. Unda uch va qirralar takrorlanmasligi kerak.
Grafda Gamilton tsikli mavjud bo`lsa, bu graf Gamilton grafi deyiladi. Yoki agar bog`liqli grafda har bir uchdan faqat bir martadan o`tuvchi sikl mavjud bo`lsa, bunday graf gamilton grafi deyiladi. Hammasi bo`lib beshta qavariq muntazam ko‘pyoqli mavjudligi qadimdan ma’lum (Evklid isbotlagan): tetraedr, kub, oktaedr, dodekaedr va ikosaedr. Bu ko‘pyoqlilarning umumiy nomi ham bor – Platon jismlari. Barcha Platon jismlariga mos graflar tekislikda geometrik ifodalanadi. Masalan, tetraedr va kubga mos graflarning geometrik ifodalanishi 39- rasmda tasvirlangan.
Platon jismlaridan tetraedr, kub va dodekaedr kubik grafga misol bo`ladi.
rasmda tasvirlangan Petersen grafi deb ataluvchi graf ham kubik grafdir.
Agar graf tekislikda geometrik ifodalanishga ega
bo`lsa, u holda bunday graf tekis (yassi) graf deb ataladi. Bunday graf tekislikda yotuvchi graf deb ham atalishi mumkin.
Boshqacha so`zlar bilan aytganda, tekis grafning barcha uchlari bir tekislikda yotadi hamda barcha qirralari (yoylari) o`sha tekislikda yotuvchi o`zaro kesishmaydigan uzluksiz chiziqlar bo`lib, ular faqat o`zlari insident bo`lgan uchlardagina umumiy nuqtalarga ega. Platon jismlariga mos barcha graflar tekis graflardir.
Tekis grafga izomorf graf planar graf deb ataladi.
. Kortej tushunchasi. Matemetikada, jumladan, kombinatorika va graflar nazariyasida, to‘plam tushunchasi bilan bir qatorda, kortej tushunchasi alohida o‘rin tutadi. Turli xossalarga ega bo‘lgan obycktlar bilan ish ko‘rganda, kortej tushunchasidan foydalanish mumkin. Kortej tushunchasi yordamida kombinatorikaning ko‘plab lushunchalari tabiiy ravishda oson anglanadi. Kortej tushunchasini o'rganishdan oldin to‘plamning elementlari takrorlanmasligini fsliitib o‘tamiz. Ixtiyoriy Ar A2,...An to‘plamlar berilgan bo‘lsin. Bu to‘plamlaming ixtiyoriy biridan, masalan, ^ to‘plamdan qandaydir fl/( clcmentni, \ to‘plamdan boshqa istalgan A ^to‘plamning qandnydir a^ elementini va hokazo, oxirgi Jo‘plamdan qandaydir <>j elementni olamiz. Bu elementlarni ulaming berilgan to‘plamlardan olinishi tartibidajoylashtirib < a-,a^,...,a^ > tuzilmaga cga bo'lamiz. Bu tuzilmada har bir element o‘zining qat’iy joylasliish o‘miga ega. Shunday usul bilan boshqa tuzilmalami ham liosil qilish mumkin. Bu tuzihnalarning har biri elementar kortej (qisqacha, kortej), deb ataladi. Kortejni boshqa usullar yordamida ham tashkil qilish mumkin. Masalan, faqat bitta to‘plam clcmentlaridan (hattoki, bu to‘plam yagona elementli bo‘lsa ham) loydalanib, tarkibida elementlari ko‘p bo‘lgan kortej tuzish mumkin. Kortejlami belgilashda, ko‘pincha, lotin yoki yunon alifbosining bosh harilaridan foydalaniladi. Av A2,..., An to‘plamlar ixtiyoriy bolgani uchun bu to‘plamlar umumiy elementlarga ega bo‘lishi ehtimoldan .xoli emas. Ba’zi hoUarda kortej iborasining o‘miga vektor yoki uning uzunligini e’tiborga olgan holda juftlik (uzunligi ikkiga teng kortej), uchlik, to ‘rtlik va hokazo w-lik (uzunligi n ga teng kortej) iboralari ham ishlatiladi. Uzunligi n bo‘lgan kortej n о ‘rinli kortej, deb ham ataladi. Kortejni tashkil etuvchi elementlar soni, ya’ni kortejning uzunligi shu kortejning quwati, deb ataladi. Berilgan К kortejning uzunligi (quwati) |AJ ko‘rinishda belgilanadi. Kortej tarkibidagi elementlar takrorlanishi mumkinligidan, ularning kortejda tutgan o ‘rinlari muhim hisoblanadi. Shuning uchun kortejning muayyan elementi nazarda tutilganda, uning o‘mini aniqlovchi raqam hisobga olinishi kerak. Uzunliklari teng bo'lgan ikkita kortejning mos o‘rinlaridagi elementlari aynan bir xil bo‘lsagina, bu kortejlar teng, deb ataladi. Kortejni tashkil qiluvchi elementlar, uning komponentalari yoki koordinatalari, deb ataladi. Ba’zan, kortejni tashkil qiluvchi elementlar uchun, qisqacha qilib, kortejning elementlari iborasi ham qo‘llaniladi. Tabiiyki, uzunliklari teng bo‘lmagan kortejlar teng emas. Kortejlar teng bo‘lishi uchun ularning mos komponentalari o‘zaro bir xil bo‘lishi shart. Masalan, to£rt komponentali va kortejlar o‘zaro tengdir, chunki ularning toq o‘rinlaridagi komponentalari aynan bir xil va juft o‘iinlarida turgan komponentalari esa to‘plamlar sifatida bir-biriga teng bo‘lgani uchun aynan bir xildir. 1-misol. X={a,b}, Y={b,c,d) va Z—{e} to‘plamlar uchun ularning berilish tartibiga (X, Y,Z) mos keluvchi hamda har bir to'plamdan faqat bittadan element olish sharti bilan tuzilgan barcha elementar kortejlar quyidagilardir: , , , , , . ■ Л 2-misol. To‘g‘ri burchakU xOy Dekart koordinatalari sistemasining abssissalar va ordinatalar o‘qlariga ikkita [a,b] va [c,d\ kesmalar 6-shakldagidek joylashtirilgan __^ bo‘lsin mlsol. 1835-yilda S. Morze1 tomonidan yaratilgan matnli ma’luHl*Mill kodlash sistemasi (Morze alifbosi) bir asrdan ko‘p davr lliohiivnldn ma’lumot uzatishda asosiy sistema bo‘lib keldi. Bu iMiHHmlit faqat ikkita bir-biridan farqli elementlar — nuqta «•» signal) va tire «—» (uzun signal) bo‘lib, ular yordamida ItMMHliigl bclgilar (harflar, raqamlar va boshq.) kodlanadi. Bunday muMn lu/ilgan har bir kodni kortej, deb hisoblash mumkin. Morze MllfttoKHla u/.unliklari birdan oltigacha bo‘lgan kortejlar bor. ■ 4 mlsol. 0 ‘zbekiston Respublikasida shaxsiy •VlOinoblllarni davlat ro‘yxatiga olishda yetti o‘rinli 114C2993 fcnrHlimlun foydalaniladi. Har bir kortejdagi dastlabki lit к I o'rlnga 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 raqamlar, hi liiiichl o'ringa lotin alifbosining 26 harfidan bittasi va qolgan bmi o'ringa raqamlar joylashtiriladi. Bunday usulda tuzilgan har till m ’yxatga olish belgisini kortej, deb hisoblash mumkin. Inliilyki, bu yerda raqamlar takrorlanishlari mumkin. Masalan, I kliuklda tasvirlangan ro‘yxatga olish belgisiga mos keluvchi I /I,С ,2,9,9,3> kortejda 9 raqami ikki marta yozilgan. ■ .1 mlsol. Microsoft (MS) Office tarkibiga kiruvchi MS Excel lU lrniiisida ma’lum otlar elektron jadvallardagi kataklarga kiylimhliriladi. Foydalanuvchi bu jadvallami turli nomlar bilan hi Igllitb, ma’lumotlami fayl shaklida kompyuter xotirasida saqlashi nmmkm Har bir elektron jadval ustunlar va satrlarga ega. MS I uol sislemasida ustunlar (jami 256 ta) lotin alifbosi tartibida iilillu «Л» dan «Z»gacha bitta harf bilan, keyin «АА» dan «IV» Mill Ini Ikkita harflar bilan, satrlar esa ldan 65536 gacha sonlar lilliiu belgilanadi. Bu yerda, jadvallar nomlari,uning ustunlari va Mliliiil lo'plamlaridan bittadan elementni tartib bilan olib uch mi mli kortej tuzish mumkin. Bunday usul vositasida tuzilgan uch H'lliili barcha kortejlar soni k="jadvallar soni"x65536x256 bo‘ladi. M’* I xccl sistemasida bu kortejlardan elektron jadvallardagi katakImulng adreslari sifatida foydalaniladi.
|
| |
