Toshkent viloyati Chirchiq Davlat pedagogika instituti Aniq fanlar fakulteti

Asosiy qism

Graflar nazariyasining dastlabki ma’lumotlari

Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi.

Grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar. Avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa ba’zi sodda tushunchalarni keltiramiz. V qandaydir bo‘shmas to‘plam bo‘lsin. Uning

v₁ V
va v₂ V
elementlaridan tuzilgan
 v₁, v₂ 
ko‘rinishdagi barcha juftliklar

(kortejlar) to‘plamini (V to‘plamning o‘z-o‘ziga Dekart ko‘paytmasini) V V

belgilaymiz.
bilan

Graf deb shunday
 V ,U 
juftlikka aytiladiki, bu yerda

V  
va U –

 v₁, v₂ 

( v₁ V ,


v₂ V ) ko‘rinishdagi juftliklar korteji bo‘lib,

V V
to‘plamning

elementlaridan tuzilgandir.

Bundan buyon grafni belgilashda
 V ,U 
yozuv o‘rniga

(V ,U )

yozuvdan

foydalanamiz. Grafning tashkil etuvchilarini ko‘rsatish muhim bo‘lmasa, u holda uni lotin alifbosining bitta harfi, masalan, G bilan belgilaymiz.

G  (V ,U )
graf berilgan bo‘lsin. V to‘plamning elementlariga G grafning