9-mavzu: Graflar nazariyasining asosiy tushunchalari. Graflarning ba’zi turlari. Graflarning berilish usullari. Qo`shnilik va insidentlik matritsalari. Graflarning izomorfligi. Qoshnilik. Insidentlik. Uchning darajasi

9-mavzu: Graflar nazariyasining asosiy tushunchalari. Graflarning ba’zi turlari. Graflarning berilish usullari. Qo`shnilik va insidentlik matritsalari. Graflarning izomorfligi.

Qoshnilik. Insidentlik. Uchning darajasi

Graflar nazariyasi hozirgi zamon matematikasining asosiy qismlaridan biridir. Keyingi vaqtlarda turli xil diskret xususiyatlariga ega bo`lgan hisoblash qurilmalarini loyihalashda graflarning ahamiyati yanada oshdi.

Umumiy holda graf bu – ma’lum bir holatdagi chiziqlar bilan (to`g`ri bo`lishi shart emas) tutashtirilgan nuqtalar to`plamidir va to`plam nuqtalari graf uchlari, ularni tutashtiruvchi chiziqlar graf qirralari deyiladi. Odatda, graf uchlari natural sonlar bilan, qirralarini ular tutashtirgan uchlar belgilandan sonlarning tartiblanmagan juftliklari bilan belgilanadi.

Agar har qaysi 2 ta uch faqat 1 ta qirra bilan tutashtirilgan bo`lsa va har bir qirra har xil uchlarni tutashtirsa, bunday grafga sodda graf deyiladi

1. 
   rasm
   

Graflarni faqat faqat rasm ko`rinishda emas, analitik ko`rinishida ham tasvirlash mumkin.

Masalan: V = {1,2,3,4,5,6,7},

E= {{1,2}, {1,3}, {1,4}, {1,7}, {2,5}, {2,6}, {2,7}, {3,4}, {3,6}, {4,5}, {4,6}, {5,7}}.

E to`plam V to`plamning 2 elementli to`plam ostilar to`plami bo`lib, uning har bir elementi qirrani ifodalaydi.