• 16-MAl, zanjir, sikl. Eyler va Gamelton graflari(4 soat). REJA Yolanganlik tushunchasi. Bogzlar
  • Marshrutlar va zanjirlar haqida umumiy maplami va qirralar korteji bolsin. Bu grafdagi uchlar va qirralarning har ikki qorinishdagi chekli yoki cheksiz ketma-ketligi marshrut
    		•

    16-mal, zanjir, sikl. Eyler va Gamelton graflari(4 soat). Reja




    Download 17.82 Kb.
    Sana27.04.2024
    Hajmi17.82 Kb.
    #209124
    Bog'liq
    16-ma’ruza. Yo‘l, zanjir, sikl. Eyler va Gamelton graflari(4 soa-hozir.org
    Operatsion tizimlar xavfsizlik kategoriyalari Operatsion tizizml, photochemistry, GALOGENLASH, Reja Xaara bazislarida spektral analiz-fayllar.org, [14.04.2024 07 09] МАРГИЛАН ТАШКЕНТ ПАСС ЦЕНТР., Optimal qaror qabul qilish Graflar. Umumiy ma’lumotlar Graf-hozir.org, Bajardi boynazarov a tekshirdi begulov o, Eyler va Hamilton grafi-fayllar.org, 9-lab Piroliz orqali olingan etilen polimerlar, 2 LAB, kh3, Mavzu Chiziqli dasturlash masalalari uchun tayanch yechim tushu-fayllar.org, Buxoro davlat universiteti, Mavzu Algoritmlarni eng yomon va o‘rtacha holatlarda baholash-fayllar.org

    xmlns:w="urn:schemas-microsoft-com:office:word"
    xmlns="http://www.w3.org/TR/REC-html40">
    16-mal, zanjir, sikl. Eyler va Gamelton graflari(4 soat). Reja
    16-MAl, zanjir, sikl. Eyler va Gamelton graflari(4 soat).
    REJA

    1. Yolanganlik tushunchasi. Bogzlar:       Yolanganlik, bogl, sikl, zanjir.
      Tarif 2. Grafning har bir uchidan bir martadan o`tgan yo`l elementar deyiladi. Graf yoylari orqali bir martadan o`tgan yo`l oddiy yo`l deyiladi. Aks holda murakkab yo`l deyiladi.
      Marshrutlar va zanjirlar haqida umumiy maplami va qirralar korteji bolsin. Bu grafdagi uchlar va qirralarning har ikki qorinishdagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi. Marshrutni uning uchlari ketma-ketligi yoki qirralari ketma-ketligi kolmasa, bu uchni marshrutning boshlanglmaganda esa, uni marshrutning oxirgi uchi deb ataydilar.
      Agar marshrutning boshlanglsa, u holda uni uchdan uchga yolgan marshrut deb ataladi.
      Marshrutdagi ikkita qoshni qirralarga tegishli uch ichki uch yoki oraliq uch deb ataladi.
      Marshrutda qirralar va uchlar takrorlanishi mumkin bozida, uning boshlanglishi ham mumkin va teskarisi, marshrutning boshlanglishi ham mumkin.
      Tabiiyki, marshrut:
      ich uchga ham oxirgi uchga ham ega bo boshlangich uchga ega bolmasligi mumkin yoki, aksincha, oxirgi uchga ega bolmasligi mumkin (bir tomonlama cheksiz marshrut);
      lishi mumkin (notrivial marshrut);
      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 bolsa, u yopiq zanjir deb ataladi. Hech bonalgan marshrutdir, bunda 3 ich uch, 4 lib, u zanjir bosha graf uchun zanjirning oxirgi boini sifatida yoki qirralardan qaysisi olinishiga bognalishini (oriyentatsiyasini) inobatga olmasdan oriyentirlanmagan marshrut, zanjir va oddiy zanjir tushunchalarini kiritish mumkin. Lekin, oriyentirlangan graflar uchun oriyentirlangan marshrut tushunchasini kiritish tabiiydir.
      Yoylarning oriyentatsiyalari hisobga olingan yoylar va uchlar ketma-ketligi oriyentirlangan marshrut deb ataladi.
      Oriyentirlangan marshrut uchun zanjir tushunchasiga ol       (yoki oriyentirlangan zanjir) tushunchasini ham kiritish mumkin. Boshlangla olmaydi. Bu ketma-ketlik oriyentirlangan marshrut ham bonalishiga teskari yoldir, lekin u kontur emas. Berilgan grafda faqat bitta kontur borinishda ifodalash mumkin.
      Teorema.Agar grafdagi har bir uchning lokal darajasi ikkidan kichik bolsa, teoremaning tasdiggini graf sirtmoqsiz va karrali qirralari bolmagan grafning ixtiyoriy uchi boshni uchni va bu uchga dan farqli boshqa qoshni uchni, va hakoza, uchga dan farqli boshqa qora yuqoridagi jarayonni amalga oshirish va talab etilgan xossaga ega uchni topish mumkinligini taplami chekli tolganligidan, yuqorida bayon etilgan uchlar ketma-ketligini qurish jarayonida chekli qadamdan solamiz. Agar uch ketma-ketlikda ikki marta uchragan dastlabki uch boshish jarayonini tolanganlik tushunchasi. Boglangan       deb, marshrutning olovchi marshrut debataladi.

      Tabiiyki, agar qandaydir uchlarni bogtsa, u holda marshrutning siklik qismini olib tashlab (bunda siklik qismning osha uchlarni bogrinishdagi marshrutni hosil qilish mumkin. Shuning uchun, marshrut bilan bogglangan bolangan graf boglsa, u holda bu ikkita uch ekvivalent (bogplami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar toyicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni boglamli qismlarning birlashmasi deb qarash mumkin. Bu yerda berilgan graf boglaklandi (ajratildi) deb aytish mumkin. Isbotlash mumkinki, har qanday graf olamlilik komponentalarining dizlamlilik komponentalariga bolumotlarni bayon etish uchun yoq tushunchasi zarur bolmagan (yalmagan uzluksiz chiziq bilan tutashtirish mumkin boplami grafning nuqtani orifga koqirqiblmaganda bitta yoqi boz-orif 1. Qirraning boshi yoki oi uchning darajasini P(ton tsikli deyiladi.


      Oddiy zanjir Gamilton zanjiri deyiladi, agar bunday grafda tugunlarning hammasi ishtirok etsa. Tugun va qirralar takrorlanmasligi kerak.
      Grafda Gamilton tsikli mavjud bo'lsa, bu graf Gamilton grafi deyiladi.
      Nazorat uchun savollar:

      1. Insidentlik tushunchasini tarifini bering.

      2. Planar graf nima?

      3. Qanday graflar gomeomorf deyiladi?

      4. Yig`indi graf deb nimaga aytiladi?

      5. Ko`paytma graf deb nimaga aytiladi?

      6. Grafning diametri deb nimaga aytiladi?

      7. Pontryagin-Kuratovskiy teoremasini ayting.


      1

      2

      http://hozir.org
      Download 17.82 Kb.




    Download 17.82 Kb.
    Bosh sahifa
    Aloqalar
        Bosh sahifa
    Dərs
    Mühazirə
    Qaydalar
    Referat
    Xülasə
    Yazı


    16-mal, zanjir, sikl. Eyler va Gamelton graflari(4 soat). Reja

    Download 17.82 Kb.