|
Graflarning berilish usullari
|
| bet | 11/12 | | Sana | 13.05.2024 | | Hajmi | 61,74 Kb. | | #229485 |
Bog'liq Mustaqil ishi-4-kompy.infoGraflarning 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:
Cheklangan cho'qqilar to'plami, shuningdek, tugunlar deb ham ataladi.
(u, v) ko'rinishdagi tartiblangan juftlikning chekli to'plami chekka deb
ataladi. Juftlik tartiblangan, chunki (u, v) yo'naltirilgan grafik (di-graf) holatida (v, u) bilan bir xil emas. Shakl juftligi (u, v) cho'qqi u dan v cho'qqigacha chekka
borligini bildiradi. Qirralarda og'irlik/qiymat/narx bo'lishi mumkin.
Grafiklar ko'plab real hayot ilovalarini ko'rsatish uchun ishlatiladi: Grafiklar
tarmoqlarni ifodalash uchun ishlatiladi. Tarmoqlar shahar yoki telefon tarmog'i yoki elektron tarmoqdagi yo'llarni o'z ichiga olishi mumkin. Grafiklar linkedIn, Facebook kabi ijtimoiy tarmoqlarda ham qo'llaniladi. Masalan, Facebook-da har bir shaxs tepa (yoki tugun) bilan ifodalanadi. Har bir tugun tuzilma bo'lib, shaxs identifikatori, ismi, jinsi va mahalliy til kabi ma'lumotlarni o'z ichiga
oladi. Grafikning qo'shimcha ilovalari uchun buni ko'ring.
Quyida 5 ta burchakli yo'naltirilmagan grafik misoli keltirilgan.
uyidagi ikkitasi grafikning eng ko'p ishlatiladigan tasvirlari.
Qo'shnilik matritsasi
Qo'shnilik ro'yxati Boshqa ko'rinishlar ham mavjud: Insidans matritsasi va Insidans
List. Grafik tasvirni tanlash vaziyatga xosdir. Bu butunlay bajariladigan operatsiyalar turiga va foydalanish qulayligiga bog'liq.
|
| |
