marshrutlar va zanjirlar

DOCX 8 стр. 294,3 КБ Бесплатная загрузка

8 стр.

FaylHub.uz

Скачать через Telegram

Размер 294,3 КБ

Тип файла DOCX

Страницы 8

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 8

mavzu: marshrutlar va zanjirlar graf. uch. qirra. marshrut. boshlang‘ich, oxirgi, ichki, oraliq uch. ikki tomonlama cheksiz, bir tomonlama cheksiz, notrivial va nol marshrut. marshrutning uzunligi. zanjir. oddiy, yopiq zanjir. sikl. oriyentirlangan marshrut. yo‘l. kontur. bog‘langan uchlar. uchlarni bog‘lovchi marshrut. bog‘lamli graf. bog‘lamlilik komponentalari. ekvivalentlik munosabati. diz’yunktiv birlashma. ajratuvchi qirralar. kesim. ko‘prik. ko‘ndalangiga izlash. 1. marshrutlar va zanjirlar haqida umumiy ma’lumotlar. uchlari to‘plami va qirralar korteji bo‘lgan oriyentirlanmagan graf berilgan bo‘lsin. bu grafdagi uchlar va qirralarning har ikki qo‘shni qirralari umumiy chetki uchga ega ko‘rinishdagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi. marshrutni uning uchlari ketma-ketligi yoki qirralari ketma-ketligi ko‘rinishda ham belgilash mumkin. agar marshrutda qandaydir uchdan oldin uchlar bo‘lmasa, bu uchni marshrutning boshlang‘ich uchi deb, shu uchdan keyin marshrutga tegishli uchlar bo‘lmaganda esa, uni marshrutning oxirgi uchi deb ataydilar. agar marshrutning boshlang‘ich uchi va oxirgi uchi bo‘lsa, u holda uni uchdan uchga yo‘nalgan marshrut yoki chetlari va bo‘lgan marshrut deb …

2 / 8

m qirraga ega bo‘lmasligi mumkin (nol marshrut yoki trivial marshrut). marshrutning uzunligi deb undagi qirralar soniga aytiladi. turli qirralardan tashkil topgan marshrutga zanjir deb ataladi. agar zanjirning chetlaridan tashqari barcha uchlari turlicha bo‘lsa, u holda uni oddiy zanjir deb ataydilar. berilgan zanjir yoki oddiy zanjir uchun bo‘lsa, u yopiq zanjir deb ataladi. hech bo‘lmaganda bitta qirraga ega yopiq oddiy zanjir sikl deb ataladi. sirtmoq yoki bir juft karrali qirralar sikl tashkil etishi ravshandir. tushunarliki, grafdagi zanjir grafning qism grafi deb qaralishi mumkin. 1- misol. ushbu bobning 2- paragrafidagi 1- shaklda tasvirlangan graf uchun ketma-ketlik 3 belgili uchdan 4 belgili uchga yo‘nalgan marshrutdir, bunda 3 – boshlang‘ich uch, 4 – oxirgi uchdir. bu marshrutda 1, 2 va 3 belgili uchlar oraliq uchlar hisoblanadi. qaralayotgan marshrutning uzunligi 6a teng bo‘lib, u zanjir bo‘la olmaydi, chunki unda 1 belgili uch 2 marta (bir marta oraliq uch sifatida, ikkinchi marta esa oxirgi uch sifatida) …

3 / 8

anjir bo‘la olmaydi. bu ketma-ketlik oriyentirlangan marshrut ham bo‘la olmaydi, chunki unda marshrut yo‘nalishiga teskari yo‘nalishga ega yoylar bor (). qaralayotgan graf uchun ketma-ketlik oriyentirlangan marshrutni tashkil etadi. bu marshrut yo‘ldir, lekin u kontur emas. berilgan grafda faqat bitta kontur bo‘lib, bu konturni yoki ko‘rinishda ifodalash mumkin. ■ 1- teorema. agar grafdagi har bir uchning lokal darajasi ikkidan kichik bo‘lmasa, u holda bu graf siklga ega. isboti. agar grafda sirtmoqlar yoki karrali qirralar bo‘lsa, teoremaning tasdig‘i to‘g‘riligi ravshandir. shuning uchun teorema tasdig‘ini graf sirtmoqsiz va karrali qirralari bo‘lmagan holda isbotlaymiz. faraz qilaylik, berilgan sirtmoqsiz va karrali qirralari bo‘lmagan grafning ixtiyoriy uchi bo‘lsin. qaralayotgan uchga qo‘shni uchni va bu uchga dan farqli boshqa qo‘shni uchni, uchga esa dan farqli boshqa qo‘shni uchni, va hakoza, uchga dan farqli boshqa qo‘shni uchni, va hakoza, tanlab, qirralar ketma-ketligini tuzamiz. teoremaning shartlariga ko‘ra yuqoridagi jarayonni amalga oshirish va talab etilgan xossaga ega uchni topish mumkinligini …

4 / 8

a uchlarni bog‘lovchi oddiy zanjir ko‘rinishdagi marshrutni hosil qilish mumkin. shuning uchun, marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham bo‘glangan bo‘ladi degan xulosaga kelamiz. bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf bog‘lamli graf deb ataladi. agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo‘lsa, u holda bu ikkita uch ekvivalent (bog‘langan) deyiladi. bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentalari (qisqacha, komponentalari) deb ataluvchi bog‘lamli qismlarning birlashmasi deb qarash mumkin. bu yerda berilgan graf bog‘lamlilik komponentalariga bo‘laklandi (ajratildi) deb aytish mumkin. isbotlash mumkinki, har qanday graf o‘zining bog‘lamlilik komponentalarining diz’yunktiv birlashmasi sifatida ifodalanishi mumkin, bunda grafning bog‘lamlilik komponentalariga bo‘laklanishi bir qiymatli aniqlanadi. keyingi ma’lumotlarni bayon etish uchun yoq tushunchasi zarur bo‘ladi. tekislikda geometrik ifodalanuvchi grafni qaraymiz. bu grafga tegishli bo‘lmagan (ya’ni grafning hech qaysi uchi bilan ustma-ust tushmaydigan va uning …

5 / 8

‘yicha qo‘llaymiz. induksiya usulining bazasi sifatida bo‘lgan holni qaraymiz. bu holda teoremaning tasdig‘iga ko‘ra bo‘lishi kerak. haqiqatdan ham, tekis va bog‘lamli graf bo‘lgani uchun, u yagona uchdan tashkil topadi va bu uch yagona (cheksiz) yoqda yotadi, ya’ni va . demak, bu holda teoremaning tasdig‘i to‘g‘ridir. induksion o‘tish: teoremaning tasdig‘i uchun to‘g‘ri bo‘lsin deb faraz qilib, uning uchun ham to‘g‘ri ekanligini ko‘rsatamiz. farazimizga ko‘ra tenglik o‘rinlidir. ta qirraga ega tekis va bog‘lamli grafga ()- qirrani (uni bilan belgilaymiz) shunday qo‘shish kerakki, bunda qirra graf joylashgan tekislikda yotsin va hosil bo‘lgan graf ham bog‘lamli bo‘lsin. bu amalni bajarganda quyidagi uchta holdan biri ro‘y beradi: 1) qo‘shilayotgan qirra sirtmoqdir – bu holda qirra, albatta, grafdagi uchlardan biriga insident bo‘lib, yoqlardan birida yotadi va bu yoqni ikkiga (sirtmoq yotgan yoqning sirtmoq chizig‘i bilan chegaralangan ichki va tashqi qismlari) ajratadi, ya’ni uchlar soni o‘zgarmaydi, yoqlar soni esa birga oshadi: ; 2) qo‘shilayotgan qirra grafda bor …

Хотите читать дальше?

Скачайте все 8 страниц бесплатно через Telegram.

Скачать полный файл

О "marshrutlar va zanjirlar"

mavzu: marshrutlar va zanjirlar graf. uch. qirra. marshrut. boshlang‘ich, oxirgi, ichki, oraliq uch. ikki tomonlama cheksiz, bir tomonlama cheksiz, notrivial va nol marshrut. marshrutning uzunligi. zanjir. oddiy, yopiq zanjir. sikl. oriyentirlangan marshrut. yo‘l. kontur. bog‘langan uchlar. uchlarni bog‘lovchi marshrut. bog‘lamli graf. bog‘lamlilik komponentalari. ekvivalentlik munosabati. diz’yunktiv birlashma. ajratuvchi qirralar. kesim. ko‘prik. ko‘ndalangiga izlash. 1. marshrutlar va zanjirlar haqida umumiy ma’lumotlar. uchlari to‘plami va qirralar korteji bo‘lgan oriyentirlanmagan graf berilgan bo‘lsin. bu grafdagi uchlar va qirralarning har ikki qo‘shni qirralari umumiy chetki uchga ega ko‘rinishdagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi. marshrutni uning uchlari ket...

Этот файл содержит 8 стр. в формате DOCX (294,3 КБ). Чтобы скачать "marshrutlar va zanjirlar", нажмите кнопку Telegram слева.

Теги: marshrutlar va zanjirlar DOCX 8 стр. Бесплатная загрузка Telegram