Eyler formulasi - Zbekiston respublikasi raqamli texnologiyalari va kommunikatsiyalarini

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