Graflarning berilish usullari




Download 278.98 Kb.
bet1/2
Sana31.05.2022
Hajmi278.98 Kb.
#22504
  1   2
Bog'liq
Diskretlabaratoriya
Adabiyot. 6-sinf. 1-qism (2017, S.Ahmedov, R.Qo\'chqorov), Adabiyot. 6-sinf. 2-qism (2017, S.Ahmedov, R.Qo\'chqorov), So\'rovlarni optimallashtirish masalasi har doim ma\'lumotlar baza, lGDeBzYb6VciGc4WoLCPd2aVJGDA1iKOLUBCwXYA, OILA PE. O\'QITISH METODIKASI, Xusanov Islomjon Jasur o‘g‘li, Berdiyorova N, multimedia tizimlari, 4-tajriba analog, “keys-stadi” texnologiyasi “Keys-stadi” haqida tushuncha “Keys-s-fayllar.org, 15-top, DRIVES, 7a8d233a-41cb-401b-b05f-1ff3151ac2f1 (1), 7a8d233a-41cb-401b-b05f-1ff3151ac2f1

Graflarning berilish usullari
Grafning geometrik ifodalanishi.
Graflarning turlicha berilish usullari mavjud. Grafning abstrakt matematik ta’rifi uning berilish usullaridan biridir. Grafning abstrakt matematik ta’rifi uni tasavvur qilish, anglash, uning xossalarini o‘rganish va bu xossalarni amalda qo‘llash jarayonida ba’zi qiyinchiliklar tug‘dirishi tabiiydir. Shuning uchun grafning boshqa berilish usullaridan ham foydalaniladi. Masalan, grafning elementlarini, ya’ni uchlari va qirralarini (yoylarini) yozish yoki aytish grafning berilish usuli sifatida qaralishi munkin. Albatta, grafning yana boshqa berilish usullari ham mavjud. Quyida bu usullarning bir nechasi bilan tanishamiz.
Grafning uchlarini tekislikda yoki fazoda nuqtalar bilan, qirralarini (yoylarini) esa mos uchlarni tutashtiruvchi uzluksiz chiziqlar bilan ifodalab, qandaydir diagrammaga – grafning ko‘rgazmali tasviriga ega bo‘lamiz. Agar uchlar to‘plami va bu uchlarning tutashishlarini ko‘rgazmali qilib taqdim qilish kerak bo‘lsa, grafning geometrik tasvirlanishiga mos shaklni qog‘ozda chizib grafni tasvirlash mumkin. Shuni ta’kidlaymizki, ba’zi hollarda diagrammada graf uchlari doirachalar yordamida yoki qandaydir boshqa usulda ifodalanadi. Grafning qirralariga (yoylariga) mos chiziqlarning to‘g‘ri yoki egri bo‘lishi va ularning uzunligi ahamiyatga ega emas. Muhimi, bu chiziqlar uzluksiz bo‘lib, grafning qandaydir ikkita uchlarini tutashtirishi lozim. Agar qirra yo‘nalishga ega bo‘lsa (ya’ni u yoy bo‘lsa), u holda bunday qirrani ifodalovchi chiziqda yo‘nalish biror usul bilan, masalan, strelka bilan ko‘rsatiladi. Ixtiyoriy graf uchun bunday diagrammalarni istalgancha tuzish mukinligi ravshan. Agar biror diagrammada grafning uchlariga mos keluvchi nuqtalar ustma-ust tushmasa, qirralarga mos keluvchi chiziqlar, chetki nuqtalarni hisobga olmaganda, umumiy nuqtalarga ega bo‘lmasa, bunday diagramma grafning geometrik ifodalanishi deyiladi. Shuni ta’kidlash kerakki, bitta graf turlicha geometrik ifodalanishi mumkin. Graflar izomorfligining ta’rifi va grafni geometrik ifodalashning mohiyatidan kelib chiqadiki, abstrakt ta’rif yordamida ifodalangan graf va uning geometrik ifodalanishi o‘zaro izomorf bo‘ladi. Tabiiyki, izomorf graflar turlicha geometrik ifodalanishlari mumkin.

  1. t e o r e m a . Har qanday chekli grafni 3 o‘lchovli Evklid fazosida geometrik ifodalash mumkin.

I s b o t i . Teoremaning quyidagi konstruktiv isbotini keltiramiz. Grafning abstrakt ta’rifiga binoan uning hech bo‘lmasa bitta uchi mavjud. Agar grafda faqat bitta uch bo‘lsa, u holda uni 3 o‘lchovli Evklid fazosining biror nuqtasi sifatida ifodalaymiz. Agar grafda uchlar bittadan ko‘p bo‘lsa, u holda ularni uch o‘lchovli Evklid fazosidagi biror to‘g‘ri chiziqning (hech qaysi ikkitasi ustma-ust tushmaydigan) nuqtalariga mos keladi deb hisoblaymiz. Shu to‘g‘ri chiziqdan qirralarning (yoylarning) har biriga mos keluvchi turli yarim tekisliklarni o‘tkazamiz (graf chekli bo‘lgani uchun buning imkoniyati bor). Har bir qirrani (yoyni) unga mos yarim tekislikda, chetlari mos uchlarni ifodalovchi nuqtalarda bo‘lgan hamda bu to‘g‘ri chiziq bilan boshqa umumiy nuqtasi bo‘lmagan qandaydir chiziq vositasida ifodalaymiz. Yarim tekisliklarning tuzilishiga ko‘ra bu chiziqlar, chetki nuqtalarni hisobga olmaganda, umumiy nuqtalarga ega emas.
Grafik ma'lumotlar strukturasi bo'lib, u quyidagi ikkita komponentdan iborat: 

Download 278.98 Kb.
  1   2




Download 278.98 Kb.