• Yonaltirilmagan G graf berilgan bo`lsin.
  • Gamilton sikli
  • TOPSHIRIQLAR
    		•

    Graph qachon ishlatiladi?




    Download 1,58 Mb.
    bet4/4
    Sana19.05.2024
    Hajmi1,58 Mb.
    #244422
    1   2   3   4
    Bog'liq
    Mashxura

    Graph qachon ishlatiladi?
    Real hayotdagi juda ko’p tizimlar graph’larga asoslangan bo’ladi. Masalan Facebook ijtimoiy tarmog’idagi do’stlik aloqalari undirected graph’ga asoslangan. Siz Facebookdagi do’stingiz uchun ham do’st hisoblanasiz.
    Twitter va Instagram tarmoqlaridagi do’stlik (yoki kuzatish – follow) esa bir tomonlama bog’lanishga ega. Siz kuzatadigan odamlar sizni kuzatmasligi mumkin. Demak Twitter va Instagramdagi following – directed graph hisoblanadi.
    Yo'naltirilmagan G graf berilgan bo`lsin.
    Eyler sikli shunday siklki, unda grafning ma'lum bir uchidan chiqib, barcha qirralardan faqat bir marta o'tib, yana shu uchga qaytib kelishi kerak.
    Grafda Eyler sikli mavjud bo`lishi uchun:

    1. Graf bog`langan bo`lishi;

    2. Grafning barcha uchlarining darajalari juft bo`lishi kerak;


    Agar grafda oddiy sikl mavjud bo`lib, bu siklda grafning barcha uchlari qatnashsa, bunday sikl Gamilton sikli deyiladi.
    Oddiy zanjir Gamilton zanjiri deyiladi, agar bunday grafda uchlarning hammasi ishtirok etsa. Boshqacha aytganda, agar zanjir grafning barcha uchlaridan bir martadan o`tsa, bunday zanjirga gamilton zanjiri deyiladi. Unda uch va qirralar takrorlanmasligi kerak.
    Grafda Gamilton tsikli mavjud bo`lsa, bu graf Gamilton grafi deyiladi. Yoki agar bog`liqli grafda har bir uchdan faqat bir martadan o`tuvchi sikl mavjud bo`lsa, bunday graf gamilton grafi deyiladi.

    TOPSHIRIQLAR

    19. Grafni hosil qiling va unda Eyler va Gamilton sikli mavjudligini tekshiring. Uning hususiyatlarini aytib bering.








    Download 1,58 Mb.
    1   2   3   4




    Download 1,58 Mb.