17-dars: Graf nima

3-darajaOltin — graflar17–24 darslar

HayotdaSinf

Doskaga sinfdoshlaringizning ismini yozib, do’st bo’lganlarini chiziq bilan bog’lang. Bir necha daqiqadan keyin doskada chalkash tarmoq paydo bo’ladi — va siz undan yangi narsalarni o’qiy boshlaysiz: kim eng ko’p do’stga ega, kimlar alohida guruh, kimdan kimga xabar yetib boradi.

Bu darsdan keyin siz

• graf, uch, qirra va daraja tushunchalarini ishlatasiz
• qo’shnilar ro’yxatini quryasiz va nega matritsa emasligini asoslaysiz
• masalada graf yashiringanini taniysiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·guruh bilan·Doska yoki katta qog'oz

Sakkiz kishining ismini qog’ozga aylana qilib joylashtiring va do’stliklarni chiziq bilan bog’lang — kamida o’nta chiziq bo’lsin.

Endi uchta savolga chizmadan javob bering. Kimda eng ko’p chiziq bor? Hech kim bilan bog’lanmagan odam bormi? A dan B ga faqat do’stlar orqali xabar yetib boradimi?

Nimani sezishingiz kerak

Uchala savol ham chizmaga qarab javob berildi — hech qanday hisob kerak bo’lmadi. Kompyuterga esa shu chizmani yozib berish kerak, va buning eng qulay usuli bor.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Atamalar

grafgraph

Uchlar to’plami va ularni bog’lovchi qirralar to’plami. Uch — odam, shahar, katak, holat; qirra — ular orasidagi bog’lanish.

darajadegree

Uchga tegib turgan qirralar soni. Odam misolida — do’stlar soni.

Graf juda ko’p joyda yashiringan: yo’llar xaritasi, veb-sahifalar havolalari, kurslar tartibi, hatto panjaradagi labirint. Uchinchi darajaning asosiy ko’nikmasi — masalada grafni ko’ra bilish.

Sekin yechim

Grafni saqlashning birinchi va eng tabiiy usuli — katta jadval. bor[a][b] katagi a va b bog’langanmi degan savolga javob beradi.

sekin.pyNusxalash

1n = 42qirralar = [(1, 2), (2, 3), (1, 2), (4, 1)]3bor = [[False] * (n + 1) for _ in range(n + 1)]4for a, b in qirralar:5  bor[a][b] = True6  bor[b][a] = True7for i in range(1, n + 1):8  print(i, [j for j in range(1, n + 1) if bor[i][j]])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 42qirralar = [(1, 2), (2, 3), (1, 2), (4, 1)]3bor = [[False] * (n + 1) for _ in range(n + 1)]4for a, b in qirralar:5  bor[a][b] = True6  bor[b][a] = True7for i in range(1, n + 1):8  print(i, [j for j in range(1, n + 1) if bor[i][j]])

Sizning bashoratingizTekshirish

Javobni ko'rish

1 [2, 4]
2 [1, 3]
3 [2]
4 [1]

1 2 juftligi ikki marta berilgan, lekin jadvalda bir katak — takror o'z-o'zidan yo'qoladi. Yechim to'g'ri va o'qish oson.

Nega sekin

Bu yerda muammo vaqtda emas, xotirada. Jadval n × n katakdan iborat, ya’ni uchlar soni ikki barobar oshsa xotira to’rt barobar o’sadi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 100 000
Qo‘shnilik matritsasi (katak)n^2	10⁶sig‘adi	10¹⁰sig‘maydi
Qo‘shnilar ro‘yxati (yozuv)n	1 000sig‘adi	100 000sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

n = 100000 da matritsa 10¹⁰ katak talab qiladi — hech qanday kompyuterga sig’maydi. Va u deyarli butunlay bo’sh bo’ladi: qirralar soni bor-yo’g’i 200 ming.

Tez yechim

Har uch uchun faqat uning qo’shnilari saqlanadi. Xotira n + 2m: har qirra ikkita ro’yxatda bir martadan turadi.

tez.pyNusxalash

1n = 42qirralar = [(1, 2), (2, 3), (1, 2), (4, 1)]3qoshni = [set() for _ in range(n + 1)]4for a, b in qirralar:5  qoshni[a].add(b)6  qoshni[b].add(a)7for i in range(1, n + 1):8  print(i, sorted(qoshni[i]))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 42qirralar = [(1, 2), (2, 3), (1, 2), (4, 1)]3qoshni = [set() for _ in range(n + 1)]4for a, b in qirralar:5  qoshni[a].add(b)6  qoshni[b].add(a)7for i in range(1, n + 1):8  print(i, sorted(qoshni[i]))

Sizning bashoratingizTekshirish

Javobni ko'rish

1 [2, 4]
2 [1, 3]
3 [2]
4 [1]

Javob bir xil, xotira esa butunlay boshqa. To'plam takrorni ham o'zi yo'qotadi — 9-darsdagi asbob shu yerda ish beradi.

◆Asosiy g'oya

Amalda takror bo’lmasligi kafolatlangan bo’lsa, set() o’rniga oddiy ro’yxat olinadi — u tezroq va kamroq joy egallaydi. To’plam faqat takrorni yo’qotish kerak bo’lganda.

Ikki tomonlamami yoki bir tomonlama

Do’stlik ikki tomonlama: a b ning do’sti bo’lsa, b ham a ning do’sti. Shuning uchun har qirra ikkita ro’yxatga yoziladi.

Lekin har bog’lanish ham shunday emas. «Bu kursni undan oldin o’qish kerak» yoki «bu sahifadan u sahifaga havola bor» — bir tomonlama. Unda faqat bitta ro’yxatga yoziladi, va bu 22-darsning mavzusi.

Sinab ko’r

Vizualda har uchning qo’shnilari navbat bilan yonadi. Uch ustidagi son — uning darajasi.

Graf va qo'shnilar ro'yxati

Har uch ustidagi son — uning darajasi, ya'ni qo'shnilari soni.

Har uch uchun uning qo'shnilari ro'yxati saqlanadi; ro'yxat uzunligi — uchning darajasi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Graf — uchlar va ularni bog'lovchi qirralar. Bu grafda oltita uch va yettita qirra bor.
2. A uchining qo'shnilari: B, D. Demak uning darajasi 2.
3. B uchining qo'shnilari: A, C, E. Demak uning darajasi 3.
4. C uchining qo'shnilari: B, F. Demak uning darajasi 2.
5. D uchining qo'shnilari: A, E. Demak uning darajasi 2.
6. E uchining qo'shnilari: B, D, F. Demak uning darajasi 3.
7. F uchining qo'shnilari: C, E. Demak uning darajasi 2.
8. Yozuvlar yig'indisi 14 — bu qirralar sonining ikki barobari. Har qirra ikki uchning ro'yxatida turadi, shuning uchun ikki marta sanaladi.

Graf — uchlar va ularni bog'lovchi qirralar. Bu grafda oltita uch va yettita qirra bor.

Yozuv0

OrqagaO‘ynatishOldinga1/8Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

17 / 40

Masalan ≤ 100000 uchli grafda har uchning qo'shnilarini saqlang.

Taklif qilingan yechim

1. 1Qo‘shnilik matritsasi tuzamiz: n x n jadval.
2. 2Har qirra uchun ikkita katakni belgilaymiz.
3. 3Uchning qo‘shnilarini bilish uchun uning qatorini o‘qiymiz.
4. 4Har amal o‘zgarmas vaqtda bajariladi, demak yechim samarali.

Bu javobning 1-qismi noto'g'ri. Matritsa n² katak talab qiladi: n = 100000 da bu 10¹⁰ — xotiraga sig'maydi va programma umuman ishga tushmaydi. Uchinchi qadam ham qimmat: bitta uchning qo'shnilarini bilish uchun n ta katak o'qiladi, garchi qo'shnisi ikkita bo'lsa ham.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Grafda darajalar yig'indisi nimaga teng?

Javobni ko'rish

Qirralar sonining ikki barobariga. Har qirra ikkita uchning ro’yxatida turadi, shuning uchun ikki marta sanaladi.

2Qachon qo'shnilik matritsasi ma'qul bo'ladi?

Javobni ko'rish

Uchlar kam (masalan n ≤ 1000) va «a bilan b bog’langanmi?» degan so’rov juda ko’p bo’lganda. Ro’yxatda bu savol qo’shnilar soniga proporsional vaqt oladi, matritsada esa bitta o’qish.

3Qo'shnilar ro'yxati qancha xotira oladi?

Javobni ko'rish

n + 2m: har uch uchun bitta ro’yxat va har qirra uchun ikkita yozuv. n = 100000, m = 200000 da bu yarim million yozuv — bemalol sig’adi.

4Bir tomonlama bog'lanish qanday saqlanadi?

Javobni ko'rish

Faqat bitta ro’yxatga yoziladi: qoshni[a].append(b), teskarisi emas. Kurslar tartibi va veb-havolalar shunday.

5«Bu masala graf haqida» degan belgi nima?

Javobni ko'rish

Masalada narsalar va ular orasidagi bog’lanish bo’lsa: kimdir kimgadir ulanadi, qayerdandir qayergadir borish mumkin, nimadir nimadan keyin keladi. Panjara ham graf: qo’shni kataklar bog’langan.

Masalalar

Masalalar

3 ta

• PartyCodeforces 115Aoson

  Har xodim uchun boshliqlar zanjiri uzunligini toping. Bu daraxtdagi chuqurlik.

• Building RoadsCSES 1666o'rta

  Avval nechta alohida guruh borligini toping, keyin ularni ketma-ket ulang.

• Building TeamsCSES 1668o'rta

  Har uchni ikki rangdan biriga bo‘yang, qo‘shnilar har xil rangda bo‘lsin. Qachon imkonsiz?

Lokal mashq: mashqlar/17-qoshnilar/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Sinfdoshlaringizdan sakkiztasini olib, ular orasidagi do’stlik grafini chizing. Keyin har birining darajasini yozing va darajalar yig’indisini qirralar soni bilan solishtiring — nisbat qanday chiqdi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

17-qoshnilar masalasini yeching. sekin.py ni n = 100000 bilan yurgizishga urinib ko’ring va nima bo’lganini yozib qo’ying.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Atrofingizdagi uchta narsani graf sifatida yozing: metro tarmog’i, oilangiz shajarasi va telefoningizdagi ilovalar orasidagi «ulashish» imkoniyatlari. Har biri uchun ayting: uchlar nima, qirralar nima, bog’lanish ikki tomonlamami?

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim