“O’zbekiston temir yo’llari” daтk toshkent temir yo’l muhandislari instituti

    Ta’rif:  Aytaylik  G(V,  E)  –  graf  bo’lsin.  Uning  barcha  uchlari  va 

qirralaridan  o’tuvchi  sikl    eyler  sikli  deyilafi.  Eyler  sikli  mavjud bo’lgan 

graf eyler grafi deyiladi. 

    Teorema.  Bog’lamli  graf  eyler  garafi  bo’lishi  uchun  uning  har  bir 

uchining  darajasi juft bo’lishi zarur va etarlidir.  

     Bu teorema  grafda eyler siklining  mavjudligi  mezonidir.   

    Ta’rif:  Aytaylik  G(V,  E)  –  graf  bo’lsin.  Uning  barch  qirralaridan    bir 

marta    o’tuvchi  yo’l    eyler  yo’li  deyilafi.  Sikl  bo’lmagan  eyler  yo’li 

xususiy  eyler yo’li deyiladi. 

     Quyidagi  teorema  grafda xususiy  eyler yoli mavjudligi  mezonidir.   

    Teorema.  Graf  ,multigraf  yoki  psevdo  graf  xususiy  eyler  yo’liga  ega 

bo’lishi  uchun  uning  faqat  ikkita  uchi  toq  darajali  bo’lishi  zarur  va 

etarlidir. 

    Ta’rif:  Aytaylik  G(V,  E)  –  orgraf  bo’lsin.  Uning  barcha  uchlari  va 

yoylaridan  o’tuvchi  sikl    eyler  sikli  deyilafi.  Eyler  sikli  mavjud  bo’lgan 

orgraf eyler orgrafi deyiladi. 

    Teorema.  Bog’lamli  orgraf  eyler  orgarafi  bo’lishi  uchun  uning  har  bir 

uchining  kirish va chiqish yarim darajalari teng bo’lishi zarur va etarlidir.    

Ta’rif:  :  Aytaylik  G(V,  E)  –  graf  bo’lsin.  Uning  barcha  uchlari  o’tuvchi 

oddiy  yo’l      gamilton  yo’li  deyiladi.  Uning  barcha  uchlari  o’tuvchi  oddiy 

sikl  gamilton  sikli  deyiladi. 

      

      Masalalar.    1.G  orgrafning  bog’lamli  komponentlarini  qo’shnilik 

matritsalari yordami  toping:   

38 

 

 

 

 

a) 

b) 

d) 

2. G orgrafda masofa  ,diametr,radius markazini  toping:   

 

 

 

 

a) 

b) 

d) 

 

3. Vaznlashtirilgan  minimal  yo’lni toping:  

 

 

 

а) 

1

v

uchdan 

 

4

v

 uchgacha. 

б) 

4

v

 uchdan 

 

7

v

 uchgacha. 

в)

1

v

 uchdan 

5

v

 uchgacha. 

 

 

 

 

 

 

39 

 

4. Grafda eyler zanjirini toping.   

 

 

 

 

а) 

б) 

в) 

 

5. Vazinlashtirilgan  grafda minimal  asosiy daraxtni toping. 

 

a) 

b) 

d) 

 

 

 

6. Berilgan vaznlar matritsasi bo’yich  kommivoyadjor  masalasini yec 

 

 

1  2  3  4  5  6 

1 

  1

3 

7  5  2  9 

2  8 

  4  7  5  1

7 

3  8  4 

  3  6  2 

4  5  8  1 

  0  1 

5  2

1 

6  1  4 

  9 

6  1

0 

0  8  3  7 

 

Javob: 

1

 5 

3 

4

 6

 2 

 

1  2  3  4  5  6 

1 

  6  4  8  7  1

4 

2  6 

  7  1

1 

7  1

0 

3  4  7 

  4  3  1

0 

4  8  1

1 

4 

  5  1

1 

5  7  7  3  5 

  7 

6  1

4 

1

0 

1

0 

1

1 

7 

 

Javob: 

 

1  2  3  4  5  6 

1 

  2  2  3  3  3 

2  2 

  1  1  1  3 

3  2  1 

  3  3  3 

4  3  1  3 

  3  3 

5  3  1  3  3 

  1 

6  3  3  3  3  1 

 

Javob: 

1

 3 

2 

4

 6

 5 

1, 

masofa  11 ga teng. 

40 

 

1, 

masofa  15 ga teng. 

1

 2

6 

5

 4

 3 

1, 

masofa  36 ga teng. 

 

 

                                                     Adabiyotlar 

 

1.  Судоплатов  С.  В.,  Овчинникова  Е.  В.  Элементы  дискретной  

математики – М.: «Инфра-М», 2002 г. 

2.  Асеев  Г.Г.,  Абрамов  О.М.,  Ситников  Д.Э.  Дискретная 

математика. – Ростов – на-Дону, «Феникс», 2003 г. 

3.  Кулабухов  С.Ю.    Дискретная  математика  –  Таганрогский 

радиотехнический университет, Таганрог, 2001 г. 

4.  Гаврилов  Г.П.  ,  Сапожченко  А.А.  Задачи  и  упражнения  по 

дискретной математики.М.:Наука.2005. 

5.  Еруссалимский  Я.М.  Дискретная  математика  теория  ,  задачи  , 

приложения.- М. «Вузовская книга» , 2002 г. 

6.  Шапорев  С.Д.  Дискретная  математика.  Курс  лекций  и 

пратических занятий.  Санкт-Петербург «БХВ- Петербург» 2009 

г. 

7.  Internet  sahifalari: 

                      www.estudu.uz, 

                      www.tuit.uz, 

                      www.Math.uz, 

                      www.ZN.uz. 

 

                                           

 

 

 

  Mundarija 

   Kirish………………………………………….. 

1-§.to’plamlar  nazariyasi  elementlari.…………………..  

2-§. Kombinatorika…………………….. 

3-§.Matematik mantiq  elementlari.………… 

4-§. Gdaflar nazariyasi  elementlari.………. 

  Adabiyotlar…………………. 

 

 

 

 

 

 

41 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Redaktor: 

Chop etishga  qo’l qo’yildi : 

Bosma  t.: 1 

Qog'oz  formati: 60х84/16 

Tiraj: 

ekz. 

Buyurtma  № 

Tosh.TMI  bosmaxonasiToshkent  shahri,Odilxo'jayev ko'chasi,  1

 

 

 

 

 

 

 

 

 

 

 

Yegamberdiev Baxtiyar,   

Fazlitdin Ramizovich  Nuriddinov 

 

DISKRET  MATEMATIKA 

 

42 

 

(Bakalavriatning  “telekommunikatsiya”  yo’nalishini  2-kurs  talabalari 

uchun  uslubiy  qo’llanma) 

 

 

 

 

 

 

 

 

 

 

 

 

 

                       

 

 

 

 

 

 

 

                       © Toshkent  temir yo’l muhandislari  instituti,   2013 г.