• 3.Ostov daraxti. Minimal ostov daraxti. Ildiz daraxt.
  • O’z-o’zidan ravshanki, O’z-o’zidan ravshanki
  • 1. Daraxtda halqalar yoki bir nechta qirralar yoq.
  • 5. Daraxtdagi har qanday 2 ta v va w uchlari qirra bilan tutashgan bo‘lsa, u holda aynan bitta yopiq zanjir hosil bo‘ladi.
    		•

    Mavzu O‘rmon




    Download 3,11 Mb.
    bet1/4
    Sana24.05.2024
    Hajmi3,11 Mb.
    #251746
      1   2   3   4
    Bog'liq
    M20 O‘rmon

    Mavzu O‘rmon.

    • Mavzu O‘rmon.
    • (Daraxtlar. Daraxtlarning xossalari. Ostov daraxti. Minimal ostov daraxti. Ildiz daraxt. Daraxtlar haqidagi teoremalar)
    • Reja

      • 1.O‘rmon.

      2.Daraxtlar. Daraxtlarning xossalari.

      3.Ostov daraxti. Minimal ostov daraxti. Ildiz daraxt.

      4.Daraxtlar haqidagi teoremalar

    Daraxt va o’monga misollar

    1-ta’rif. Agar G grafning u qirrasi kamida bitta tsiklga tegishli bo’lsa, u

    • 1-ta’rif. Agar G grafning u qirrasi kamida bitta tsiklga tegishli bo’lsa, u

      • tsiklik, aks holda atsiklik qirra deyiladi.

    • G graf uchun (G)  m(G)  n(G)  k(G)
    • (bu yerda m(G)-G ning qirralari soni, n(G) - uchlari coni va k(G) komponentalari soni) ifoda uning tsiklomatik soni deyiladi.

    Osongina ko’rsatish mumkinki:

    • Osongina ko’rsatish mumkinki:

    O’z-o’zidan ravshanki,

    O’z-o’zidan ravshanki,

    n(G\ u) = n(G), m(G\ u) = m(G) - 1,

    va faqat tsikllari bo’lmagan graf uchun .

    •  

    2-ta’rif. Barcha qirralari atsiklik bo’lgan bog’liqli graf daraxt deyiladi.

    2-ta’rif. Barcha qirralari atsiklik bo’lgan bog’liqli graf daraxt deyiladi.

    1. Daraxtda halqalar yoki bir nechta qirralar yo'q.

    2.Daraxtning istalgan ikkita uchlari yagona zanjir bilan bog’langandir.

    3Daraxtning istalgan uchini tanlab olib uning ildizi yoki nolinchi pog’onali uch deb ataymiz.

    4. Daraxt uchun quyidagi munosabat amal qiladi: p = q + 1 (*), bu erda p - uchlari soni, q - qirralarning soni.

    5. Daraxtdagi har qanday 2 ta v va w uchlari qirra bilan tutashgan bo‘lsa, u holda aynan bitta yopiq zanjir hosil bo‘ladi.

    •  

    ga qo’shni bo’lgan barcha uchlarni birinchi pog’ona uchlari deymiz va hokazo - pog’onadagi uchlarga qo’shni (boshqa pog’onalarga tegishli bo’lmagan) uchlarni pog’ona uchlari deb ataymiz

    • ga qo’shni bo’lgan barcha uchlarni birinchi pog’ona uchlari deymiz va hokazo - pog’onadagi uchlarga qo’shni (boshqa pog’onalarga tegishli bo’lmagan) uchlarni pog’ona uchlari deb ataymiz
    •  

    Download 3,11 Mb.
      1   2   3   4




    Download 3,11 Mb.