Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib

4. Qoshnilik. Insidentlik. Uchning darajasi 

 

            G  grafning V- uchlar to’plamidan olingan  v

i

€V va v

j

€V uchlar qirra bilan 

birlashtirilgan bo`lsa, bunday uchlar qo`shni uchlar deyiladi. 

Masalan : 4.1- rasmda 3 va 4, 3 va 6, 4 va 6 va boshqalar qo`shni uchlar bo`ladi. 

           2 ta qirra qo`shni deyiladi agar ular umumiy uchga ega bo`lsa. 

           4.1- rasmda qo`shni qirralar {3,4}, {3,6}, {4,5}, {2,5} va boshqalar. 

           Agar uch biror qirraning oxiri bo`lsa shu uch va qirra  insident deyiladi. 

           4.1- rasmda {3,4}  qirra 3 uchga insident bu qirra 4- uchga ham insident. 

         Berilgan uchga insident  bo`lgan qirralar soni shu uchning darajasi deyiladi. 

Masalan, 4.1- rasmdagi grafda 3 uchning darajasi 2 ga 4- ucning darajasi 3 ga teng. 

Yakkalangan uchning darajasi 1 ga teng. 

          Grafning  barcha  uchlari  darajalari    yig`indisi  juft  son  bo`lib,  bu  sonning 

yarmi grafning qirralari soniga teng (bu xossa barch graflar uchun o`rinli). 

         

---

7

 

 

 

 

 

 

 Masalan: 

 

 

 

 

 

4.1- rasm 

 

         4.4.1-rasmdagi grafning uchlari darajalari yig`indisi  

ρ(1)+ρ(2)+ρ(3)+…..ρ(7) = 0+2+2+3+2+3+0 = 12 ga teng. 

           Agar uchning darajasi juft bo`lsa, u juft, darajasi toq bo`lsa, u toq uch 

deyiladi. 

           Har qanday grafda toq uchlar soni juft bo`ladi. Graflarda juft uchlar soni juft 

bo`lishi ham, toq bo`lishi ham mumkin.