Nizomiy nomidagi toshkent davlat pedagogika universiteti tabiiy fanlar fakulteti

Teorema 1.2. Chekli grafda toq darajali uchlar soni juft sonda bo’ladi.
Agar grafning barcha uchlari bir xil –darajaga ega bo’lsa, u holda bunday graf darajali regulyar graf deb ataladi: .
Regulyar graflarga misol sifatida beshta muntazam ko’pyoqlar: tetraedr, kub, oktaedr, dodokaedr va ikosaedrlarni keltirish mumkin. Ma’lumki, regulyar grafning har bir uchidan bir hil sondagi qirralar chiqadi, demak (1.4) formulaga ko’ra bo’ladi, bu erda uchlar soni. Demak, darajali ta uchga ega regulyar grafda ta qirra bo’ladi. Bunda agar, toq bo’lsa, juft sonda ishtirok etadi. Chunki, va uchlarni tutashtiruvchi bitta qirra ham uchda ham uchda hisoblanadi.
Masalan. Tetraedrni olaylik. Unda lokal darajasi 3(toq)ga teng, undagi uchlar soni 4 ga teng. U holda qirralar soni . Oktaedrda lokal darajasi 4 ga, uchlar soni 6 ga teng. U holda qirralar soni ga teng bo’ladi.

• 
  Graf uchlari
  

Uchlar to’plami va qirralar to’plami bo’lgan yo’naltirilmagan graf berilgan bo’lsin. Bu grafdagi ikkita qo’shni va qirralari umumiy uchga ega

ko’rinishdagi chekli yoki cheksiz ketma-ketlikka marshrut deb ataladi. Ikkita qo’shni qirraning umumiy uchga egaligidan uni quyiddagicha ham yozish mumkin:

Shuni ta’kidlash lozimki, marshrutda bitta qirra bir necha marta ishtirok etishi mumkin (3.1–rasm).

3.1– rasm.

Agar (3.1) marshrutda qirradan oldin hech qanday qirra mavjud bo’lmasa u holda, uch marshrutning boshlang’ich uchi, agar qirradan keyin hech bir qirra mavjud bo’lmasa u holda, uch oxirgi uchi deyiladi. Ikkita qo’shni va qirralarga tegishli bo’lgan ixtiyoriy uch ichki uch deyiladi. Ko’rinib turibdiki marshrutda qirralar va uchlar takrorlanishi mumkin, shu bilan birga ichki uch ham boshlang’ich yoki oxirgi uch sifatida ishtirok etishi mumkin.
Tabiiiyki, marshrut:

• 
  boshlang’ich uchga ega bo’lib, oxirgi uchga ega bo’lmasligi, yoki, aksincha, oxirgi uchga ega bo’lib, boshlang’ich uchga ega bo’lmasligi mumkin. Bunday marshrut bir tomonlama cheksiz marshrut deyiladi;
  
• 
  boshlang’ich uchga ham, oxirgi uchga ham ega bo’lmasligi mumkin. Bunday marshrut ikki tomonlama cheksiz marshrut deyiladi.
  
• 
  Birorta ham qirraga ega bo’lmasligi mumkin. Bunday marshrut trivial marshrut deyiladi.
  
• 
  Faqatgina yagona qirradan iborat marshrut bo’lishi mumkin. Bunday marshrut nol marshrut yoki notrivial marshrut deyiladi.
  
• 
  Agar marshrut boshlang’ich uchga va oxirgi uchga ega bo’lsa, u holda uni
  
• 
  
  
• 
  kabi yoziladi. (3.3) kabi belgilangan marshrutning uzunligi deb va uchlarni tutashtiruvchi qirralar soniga aytiladi. (3.1–rasm) keltirilgan marshrutning uzunligi 7 ga teng. Marshrutning ikkita va uchlaridan tuzilgan marshrut marshrutning qismi deyiladi. Marshrutning oxirgi va boshlang’ich uchlari ustma–ust tushsa, ya’ni, bunday marshrut tsiklik marshrut deyiladi.
  

•