15-ma’ruza. Mavzu: Graflarda erkin uchlarni tanlash, bo’yash. To’plamlarning to’plam ostilari aniqlash, birlashtirish. Reja

15-ma’ruza.
Mavzu: Graflarda erkin uchlarni tanlash, bo’yash. To’plamlarning to’plam ostilari aniqlash, birlashtirish.
Reja

1. 
   Graflarda erkin uchlarni tanlash
   
2. 
   To’plamlarning to’plam ostilari aniqlash
   
3. 
   To’plamning barcha to’plamostilarini toppish
   

Kalit so’zlar: Graflar, yo’naltirilgan graf, yo’naltirilmagan graf, kompyuter tarmog’i
Graflar haqidagi to'g'ridan-to'g'ri algoritmlarni o'rganishni boshlashdan oldin siz graflarning o'zi haqida asosiy bilimlarga ega bo'lishingiz, ularning kompyuterda qanday aks ettirilganligini tushunishingiz kerak.

• 
  Bir nechta misollar grafning yuzaki ko'rinishini beradi. Shunday qilib, odatiy graf bu metro xaritasi yoki boshqa yo'nalish. Xususan, kompyuter tarmog'I ham bizlarga graf haqidagi ma’lumotni beradi. Bu yerda keng tarqalgan - chiziqlar bilan bog'langan nuqtalarning mavjudligi. Shunday qilib, kompyuter tarmog'ida ulangan kompyuterlar va tarmoq kabellari grafni tashkil qiladi. Metroda birinchi stansiyalar, ikkinchisida ular o'rtasida tunnellar yotqizilgan. Graflar nazariyasida nuqta uchlari (tugunlar), chiziqlar esa qirralar (yoylar) deb nomlanadi. Shunday qilib, graf qirralarning bog'langan uchlari to'plamidir.
  

Kompyuter tarmog'iga qaytish. U ma'lum bir topologiyaga ega va ular bilan bir qator kompyuterlar va ularni bog'laydigan yo'llar sifatida tasvirlash mumkin. Quyidagi rasm misol sifatida to'liq bog'liq topologiyani ko'rsatadi.

• 
  Beshta kompyuter uchlari va ular orasidagi ulanishlar (signal uzatish yo'llari) chekka. Kompyuterlarni uchlari bilan almashtirsak, biz matematik ob'ektni olamiz - 10 qirralari va 5 uchlari bo'lgan grafik. Uchlardagi raqamlarni boshqalar bilan raqamlash mumkin va bu rasmda ko'rsatilgandek shart emas.
  

Graflar nazariyasida ishlatiladigan ba'zi muhim eslatmalar:
• G = (V, E), bu yerda G - graf, V - uning uchlari, E - qirralar;
• | V | - nuqtalar (qirralarning soni);
• | E | - yoylar (tomonlar soni).
Bizning holatda (1-rasm) | V | = 5, | E | = 10;
Boshqa har qanday uchdan har qanday uchga kirish imkoni mavjud bo'lganda, bunday graf yo'naltirilmagan ulangan graf deb nomlanadi.
Agar graf ulangan bo'lsa, lekin bu shart bajarilmasa, unda bunday graf yo'naltirilgan deb nomlanadi.

Yo'naltirilgan va yo'naltirilmagan graflar uch darajasi tushunchasiga ega. Bir uchning darajasi - uni boshqa uchlarga bog'laydigan qirralarning soni. Grafning barcha darajalari yig'indisi uning barcha qirralarining ikki baravariga teng. 2-rasm uchun barcha darajalarning yig'indisi 20 ga teng.

Rasmda, yo'naltirilmagan grafdan farqli o'laroq, chekka h dan chiqib, s ga kirganda, lekin aksincha emas, balki h uch dan s ga o'tish mumkin.
Yo'naltirilgan graflar quyidagi belgilarga ega:
G = (V, A), bu erda V uchlari, A yo'naltirilgan qirralar.
Grafning uchinchi turi aralash grafdir (3-rasm). Ular ikkala yo'naltirilgan va yo'naltirilmagan qirralarga ega. Rasmiy aralash graf quyidagicha yoziladi: G = (V, E, A), bu erda qavs ichidagi harflarning har biri ilgari unga bog'langan narsalarni ham anglatadi.
3-rasmdagi grafda ba'zi bir yoylar
[(e, a), (e, c), (a, b), (c, a), (d, b)],
boshqalari yo'naltirilmagan
[(e, d), (e, b), (d, c) ...].



Misol_uchun_A_={1,2,3,4}_to’plamning_barcha_to’plamostilarini_topamiz.__To’plamostilar_='>To’plamning barcha to’plamostilarini toppish

• 
  Misol uchun A ={1,2,3,4} to’plamning barcha to’plamostilarini topamiz.
  
• 
  To’plamostilar =
  
• 
  {}
  
• 
  {1}, {2}, {3}, {4},
  
• 
  {1,2}, {1,3}, {1,4}, {2,3},{2,4}, {3,4},
  
• 
  {1,2,3}, {2,3,4}, {1,3,4}, {1,2,4}
  
• 
  {1,2,3,4}
  
• 
  Agar to’plamda n ta element bo’lsa, uning to’plamostilari soni 2ⁿ ta bo’ladi.
  

To’plamosti

• 
  Agar A to’plamning barcha elementlari biror B to’plamga tegishli bo’lsa, A to’plam B ning qismto’plami deyiladi. A B deb yoziladi.
  
• 
  Misol
  

• 
  #include
  
• 
  using namespace std;
  
• 
   void barchaTuplamOstilar(int arr[], int n)
  
• 
  {
  
• 
  int count = pow(2, n);
  
• 
  for (int i = 0; i < count; i++) {
  
• 
  for (int j = 0; j < n; j++) {
  
• 
  if ((i & (1 << j)) != 0)
  
• 
  cout << arr[j] << " ";
  
• 
  }
  
• 
  cout << "\n";
  
• 
  } }
  
• 
  int main()
  
• 
  {
  
• 
  int n;
  
• 
  cout << "Tuplamning ulchamini kiriting\n";
  
• 
  cin >> n;
  
• 
  int arr[n];
  
• 
  cout << "Tuplam elementlarini kiriting\n";
  
• 
  for (int i = 0; i < n; i++)
  
• 
  cin >> arr[i];
  
• 
  barchaTuplamOstilar(arr, n);
  
• 
  return 0;
  
• 
  }
  

Mavzu yuzasidan savollar

1. 
   Graflarda erkin uchlarni tanlash algoritmlarini sanab o’ting
   
2. 
   To’plamlarning to’plam ostilari aniqlash algoritmini tushuntirib bering
   
3. 
   To’plamning barcha to’plamostilarini toppish dasturini tahlil qiling