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
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.
Do'stlaringiz bilan baham: |
