graflarning berilish usullari

DOCX 8 sahifa 250,4 KB Bepul yuklash

8 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 250,4 KB

Fayl turi DOCX

Sahifalar 8

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 8

mavzu: graflarning berilish usullari graf. orgraf. uch. qirra. yoy. sirtmoq. karrali qirralar. uchning local darajasi. multigraf. ko‘phad. grafning uchlari qo‘shniligi matritsasi. oriyentirlanmagan multigrafning uchlari qo‘shniligi matritsasi. oriyentirlangan grafning uchlari qo‘shniligi matritsasi. sirtmoqsiz orgraf uchlari qo‘shniligi matritsasi. grafning qirralari qo‘shniligi matritsasi. insidentlik matritsasi. 2.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 …

2 / 8

yoriy 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- 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 …

3 / 8

hunki tekislikda qirralarini (yoylarini) ifodalovchi kesishmaydigan (aniqrog‘i, chetki nuqtalaridan boshqa umumiy nuqtalari bo‘lmagan) chiziqlar 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 …

4 / 8

idan birida joylashgan uydan chiqib, yettita ko‘priklarning har biridan faqat bir marta o‘tgan holda yana o‘sha uyga qaytib kelish mumkinmi?” 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.3- shakl 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- shakl 1 4 2 3 5 7 6 a c b d 4- misol. 5- shaklda tasvirlangan graflar bir-biriga izomorfdir. ■ 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 …

5 / 8

raf deb ataladi. bunday graf tekislikda yotuvchi graf deb ham atalishi mumkin.6- shakl 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.7- shakl 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.8- 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 …

Ko'proq o'qimoqchimisiz?

Barcha 8 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"graflarning berilish usullari" haqida

mavzu: graflarning berilish usullari graf. orgraf. uch. qirra. yoy. sirtmoq. karrali qirralar. uchning local darajasi. multigraf. ko‘phad. grafning uchlari qo‘shniligi matritsasi. oriyentirlanmagan multigrafning uchlari qo‘shniligi matritsasi. oriyentirlangan grafning uchlari qo‘shniligi matritsasi. sirtmoqsiz orgraf uchlari qo‘shniligi matritsasi. grafning qirralari qo‘shniligi matritsasi. insidentlik matritsasi. 2.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 usul...

Bu fayl DOCX formatida 8 sahifadan iborat (250,4 KB). "graflarning berilish usullari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: graflarning berilish usullari DOCX 8 sahifa Bepul yuklash Telegram