grafning geometrik ifodalanishi

DOCX 10 sahifa 447,4 KB Bepul yuklash

10 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 447,4 KB

Fayl turi DOCX

Sahifalar 10

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 10

23-ma’ruza. graflarning berilish usullari: geometrik ifodalanishi, ko’phad yorlamida berilishi, matritsalar yordamida berilishi reja: 1 grafning geometrik ifodalanishi. 2. grafning maxsus turdagi ko‘phad yordamida berilishi. 3. qo‘shnilik matritsalari. 4. insidentlik matritsalari. 1. 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 …

2 / 10

ar 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- teorema. har qanday chekli grafni 3 o‘lchovli evklid[footnoteref:1] fazosida[footnoteref:2] geometrik ifodalash mumkin. [1: evklid (ευκλείδης, eramizdan oldingi iii asrda yashagan) – qadimgi yunon (grek) olimi.] [2: o‘lchovli evklid fazosida ikkita va vektorlar orasidagi masofa (metrika) formula bo‘yicha aniqlanadi.] isboti. 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 …

3 / 10

qlar yordamida tasvirlash imkoniyati faqat ba’zi graflargagina xos, ya’ni har qanday grafning 2 o‘lchovli evklid fazosida (tekislikda) geometrik ifodalanishi mavjud bo‘lavermaydi. graflarning geometrik ifodalanishiga doir misollar keltiramiz. 1- misol. 1- shaklda tasvirlangan grafni deb belgilaymiz. berilgan graf belgilangan graf bo‘lib, 4ta uch va 6ta qirraga ega. demak, u (4,6)-grafdir. bu graf uchun: , , , , , , . grafning barcha () qirralari oriyentirlanmagan (chunki uchlarini tutashtiruvchi chiziklarda yo‘nalish ko‘rsatilmagan) bo‘lgani uchun oriyentirlanmagan grafdir. grafning qirralaridan biri, aniqrog‘i, sirtmoqdir, va esa karrali qirralardir. bu grafda, masalan, 1 va 2 uchlar qo‘shni, 1 va 4 uchlar esa qo‘shni emas. undagi 2 va 3 uchlar qirraga insident va, aksincha, qirra 2 va 3 uchlarga insidentdir. bu yerda va qirralar qo‘shni qirralardir, chunki ular umumiy uchga (3 uch) ega, va qirralar esa qo‘shni emas. 1- shakl 1 2 3 4 2- misol. geometrik ifodalanishi 2- shakldagi ko‘rinishda bo‘lgan oriyentirlangan grafni qaraymiz. bu grafda …

4 / 10

inmi?” bu savolga javob izlash maqsadida ko‘priklardan o‘tishlar muhimligini e’tiborga olgan holda qo‘yilgan masalani tahlil qilish uchun 4- shaklda tasvirlangan grafni qaraymiz. bu grafning uchlari shaharning , , va qismlariga, qirralari esa ko‘priklarga mos keladi. qaralayotgan graf oriyentirlanmagan graf bo‘lib, 4ta uch va 7ta qirralardan tashkil topgan. uning qirralari orasida karralilari bor, lekin sirtmoqlar yo‘q.4- shakl 1 4 2 3 5 7 6 a c b d kyonigsberg shahridagi ko‘priklardan faqat bir marta o‘tgan holda yurish boshlangan joyga qaytib kelish muammosi, 4- shakldagi grafdan foydalangan holda, ushbu bobning 5- paragrafida hal qilinadi. 4- misol. 5- shaklda tasvirlangan graflar bir-biriga izomorfdir. 5- shakl 5- misol. 6- shaklda tasvirlangan graflarning har biri oltita uch va yettita qirralarga ega bo‘lib, ular izomorf emas. 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[footnoteref:3] jismlari. shunisi qiziqki, barcha platon …

5 / 10

cha 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.8- shakl platon jismlariga mos barcha graflar tekis graflardir. tekis grafga izomorf graf planar graf deb ataladi. tekis bo‘lmagan grafga ajoyib misol uchta uy va uchta quduq haqidagi boshqotirma masalaga mos grafdir. uchta , , uylar va uchta , , quduqlar bor. har bir uydan har bir quduqqa ixtiyoriy ikkitasi kesishmaydigan qilib uzluksiz yo‘lakchalar o‘tkazish mumkinmi? qog‘ozda masala shartini qanoatlantiradigan grafni chizishga urinishlar muvaffaqiyatsiz tugaydi. shunday urinishlardan biri 9- shaklda keltirilgan.9- shakl darvoqe, uchta uy va uchta quduq haqidagi boshqotirma masalaga mos graf har bir bo‘lagida uchtadan uchi bo‘lgan ikki bo‘lakli to‘la grafga misol bo‘la oladi. tekis bo‘lmagan grafga yana bir misol beshta uchga ega bo‘lgan to‘la graf – grafdir. bu grafning o‘nta qirralari borligi ravshan. bu yerda ham grafni hech qaysi ikkita qirralari kesishmaydigan …

Ko'proq o'qimoqchimisiz?

Barcha 10 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"grafning geometrik ifodalanishi" haqida

23-ma’ruza. graflarning berilish usullari: geometrik ifodalanishi, ko’phad yorlamida berilishi, matritsalar yordamida berilishi reja: 1 grafning geometrik ifodalanishi. 2. grafning maxsus turdagi ko‘phad yordamida berilishi. 3. qo‘shnilik matritsalari. 4. insidentlik matritsalari. 1. 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 ...

Bu fayl DOCX formatida 10 sahifadan iborat (447,4 KB). "grafning geometrik ifodalanishi"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: grafning geometrik ifodalanishi DOCX 10 sahifa Bepul yuklash Telegram