|
18. Takroriy o'rinlashtirish, o'rin almashtirish va guruhlashlar
Faraz qilaylik, qandaydir kortejning nta elementlari orasida bir xil (aynan bir xil) 1 n ta birinchi tur, bir xil 2 n ta ikkinchi tur, va hokazo, bir xil k n ta k- tur elementlar bo„lsin, bu yerda n1 , n2 ,… nk – hech bo„lmaganda bittasi 1dan farqli natural sonlar. Bu n ta elementlarning o„rinlarini imkoniyati boricha almashtirishlar natijasida hosil bo„lgan kortejlar (kombinatsiyalar) takrorlanuvchi elementlar qatnashgan o‘rin almashtirishlar (qisqacha, takrorli o‘rin almashtirishlar) deb ataladi.
1- teorema. Takrorli o‘rin almashtirishlar soni uchun
Takrorli o‘rinlashtirishlar. n ta elementlardan tashkil topgan to„plam berilgan bo„lsin. Bu elementlardan foydalanib, m ta elementdan tashkil topgan kortejlarni shunday tuzamizki, bu kortejlarga har bir element hohlagancha marta (albatta mdan oshmagan miqdorda) kirishi mumkin bo„lsin va bu kortejlar bir-biridan ularni tashkil etuvchi elementlar turlari bilan yoki bu elementlarning joylashishlari bilan farq qilishsin. Shunday usul bilan tuzilgan kortejlarning har biri n ta turli elementlardan takrorlanuvchi elementlar qatnashgan m tadan o‘rinlashtirish (qisqacha, takrorli o‘rinlashtirish) deb ataladi.
Takrorli gruppalashlar. Har bir elementi birlashmaga istalgancha marta kiritiladigan va turli nta elementlardan m tadan olinadigan hamda elementlar tartibi e‟tiborga olinmaydigan birlashmalarni (kortejlarni) qaraymiz. Bunaqa birlashmalar n ta turli elementlardan m tadan takrorlanuvchi elementlar qatnashgan gruppalashlar (qisqacha, takrorli gruppalashlar) deb ataladi.
19. Graflar nazariyasining asosiy tushunchalari.
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. XIX asrning o’rtalarida graflar nazariyasi bilan bog’liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo’ldi. “Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag’ishlangan dastlabki darslikda uchraydi.
Graf deb shunday juftlikga aytiladiki bu yerda V=∅ va U-< > ko’rinishidagi juftliklar korteji bo’lib , VxV to’plamning elementlaridan tuzilgandir.
G=(V,U) graf berilgan bo’lsin, V to’plamning elementlariga G grafning uchlari, V grafning o’ziga esa, grafning uchlari to’plami deyiladi. Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi.G =(V,U) graf elementlarining soni ( |V |+|U | )ga tengdir, bu yerda G grafning uchlari soni |V |≠ 0 va |U | bilan uning qirralari (yoylari) soni belgilangan. Agar grafda (a,b) qirra, yoki (a,b) yoy, yoki (b, a) yoy topillsa, u holda a va b uchlar tutashtirilgan deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy bor bo’lsa, u holda ular qo’shni uchlar deb, aks holda esa, qo’shni bo’lmagan uchlar deb aytiladi. Grafning ikkita uchi qo’shni bo’lsa, ular shu uchlarni tutashtiruvchi qirraga (yoyga) insident, o’z navbatida, qirra yoki yoy bu uchlarga insident deyiladi.
20.Graflarning ba’zi turlari.
Tarkibida parallel qirrasi bo’lgan graf multigraf deyiladi.
Tarkibida sirtmoq qirra bo’lgan graf psevdagraf deyiladi.
Agar grafning barcha qirralari yo’nalishga ega bo’lsa bunday graf oriyentrlangan graf deyiladi.
Hech bir qitrrasi yo’nalishga ega bo’lmasa oriyentrlanmagan graf deyiladi.
Ba’zi qirralarida yo’nalish bor, ba’zilarida y’q bo’lsa bunday garaf aralash graf deyiladi.
Faqat yakkalangan uchlardan iborat graf nol graf deyiladi.
Istalgan ikkita uchi qo’shni bo’lgan sirtmoqsiz karrali qirrasiz oriyentrlanmagan garf to’la graf deyiladi.
Agar grafning uchlariga qandaydir belgilar qo’yilgan bo’lsa, bunday graf belgilangan graf deyiladi.
Agar grafning barcha uchlari bir xil darajaga ega bo’lsa bunday graf darajali regulyar graf deyiladi.
O’zaro kesishmaydiga 2 ta to’plamga ajratish mumkin bo’lsaki , barcha qirralari 1-to’plamning qaysidir uchining, 2-to’plamning qaysidir uchiga tutashtiruvchi holatga uchrasa bunday graf 2 bo’lakli graf deyiladi.
Agar 2 bo’lakli grafning biror to’plamida bitta uch bo’lsa bunday graf yulduzchali graf deyiladi.
21. . Grafning berilish usullari.
Grafning berilish usullari: graf 3 xil usulda berilishi mumkin. Bular: geometrik usulda , maxsus ko`phad ko`rinishida, uchlar qo`shnilik yoki qirralar qo`shnilik matritsasi ko`rinishida berilishi mumkin. Lekin graf oriyentirilgan bo`lsa insidentlik matritsasidan foydalanish kerak. 1. grafning geometrik usulda berilishi bu biron bir shaklni chizmada ifodalash 2. Grafning maxsus turdagi ko‘phad yordamida berilishi.
3. Qo‘shnilik matritsalari. Endi grafning boshqa bir berilish usuli negizida yotuvchi graf uchlari qo‘shniligi matritsasi tushunchasini qarab chiqamiz.
G =(V,U) – uchlari soni m ga teng bo’lgan belgilangan, sirtmoqsiz va karrali qirralarsiz graf bo’lsin.
Elementlari
ko’rinishida aniqlangan matrisani grafning uchlari qo’shniligi matritsasi deb ataymiz.
Misol. Rasmda tasvirlangan grafgning uchlari qo’shniligi matritsasi
ko’rinishda bo’ladi.
Uchlari soni m ga teng bo’lgan belgilangan oriyentirlangan G = (V,U) grafning uchlari qo‘shniligi m×m-matritsasi deb elementlari
ko’rinishidagi matrisaga aytiladi.
Do'stlaringiz bilan baham: |
