Электр схемаси учун кесим матрицаси концепцияси
Graf teoriyasida kesim to'plam matritsasi haqida gaplashganda, umumiy holda asosiy kesim to'plam matritsasi haqida gaplashamiz. Kesim to'plam bu, ulangan grafning minimal qismi bo'lib, bu qismni grafdan o'chirib tashlaganda, graf 2 ta alohida qismga, ya'ni sub-grafga ajraladi va kesim to'plam matritsasi shu kesim to'plamlarni qatorlar orqali olingan matritsadir. Kesim to'plam matritsasi [Qf] belgisi bilan belgilanadi.
Kesim to'plam matritsasi misol
Grafni [1, 2, 5, 6] tartib raqamlariga ega bo'lgan kesim to'plamlarni tanlab o'chirish orqali 2 ta sub-graf hosil qilinadi.
Boshqacha qilib aytganda, berilgan grafga nisbatan daraxtga nisbatan asosiy kesim to'plam - bu bitta chagilla va qolgan havolalar bilan tuzilgan kesim to'plamdir. Chagillar - bu daraxtning qismi, havolalar esa ko-daraxtning qismi.
Shunday qilib, kesim to'plamlarning soni chagillarning soniga teng.
[Chagillar soni = N – 1]
Bu yerda, N - berilgan grafdagi yoki chizilgan daraxtdagi tugunlar soni.
Kesim to'plamning yo'nalishi chagillarning yo'nalishi bilan bir xil bo'lib, bu musbat deb hisoblanadi.
Kesim to'plam matritsasini chizish uchun quyidagi qadamlarni bajaring. Qadamlar quyidagilar:
Berilgan tarmoq yoki shema (agar berilgan bo'lsa) grafikasini chizing.
Keyin uning daraxtini chizing. Daraxtning qismi chagillar bo'ladi.
Keyin grafning qolgan qismini nuqtali chiziq bilan chizing. Bu qism havolalar bo'ladi.
Daraxtning har bir qismi yoki chagillari mustaqil kesim to'plam tashkil etadi.
Matritsaning qatorlarini kesim to'plamlar, ustunlarini esa qism bilan yozing.
| Branchase ⇒ | 1 | 2 | 3 | . | . | b | |
| Cutsets | |||||||
| C1 | |||||||
| C2 | |||||||
| C3 | |||||||
| . | |||||||
| . | |||||||
| Cn | |||||||
n = kesishlar soni.
b = qirg'achlar soni.
Kesish to'plam matritsasidagi yo'nlanish
Qij = 1; agar qirg'ach J kesish to'plamida bo'lsa va daraxt qirg'achining bir xil yo'nlanishi bo'lsa.
Qij = -1; agar qirg'ach J kesish to'plamida bo'lsa va daraxt qirg'achining teskari yo'nlanishi bo'lsa.
Qij = 0; agar qirg'ach J kesish to'plamda bo'lmasa.
Misollar 1
Quyidagi grafik uchun kesish to'plam matritsasini chizing.
Javob:
Qadam 1: Quyidagi grafik uchun daraxtni chizing.
Qadam 2: Endi kesish to'plamni aniqlang. Kesish to'plam faqat bitta qirg'ach va istalgan miqdordagi bog'liqlarni o'z ichiga oladigan nod bo'lishi kerak.
Bu yerda C2, C3 va C4 kesish to'plamlar.
Qadam 3: Endi matritsaning chizilishini boshlang.
| Filiallar ⇒ | 1 | 2 | 3 | 4 | 5 | 6 | |
| Kesimlar | |||||||
| C2 | +1 | +1 | 0 | 0 | -1 | 0 | |
| C3 | 0 | 0 | +1 | 0 | +1 | -1 | |
| C4 | -1 | 0 | 0 | +1 | 0 | +1 |
|
Bu talabga javob beradigan matritsa.
Misollar 2:
Berilgan grafik uchun kesishni chizing.
Javob:
Yana bu savolda oldingi savolga qilingan kabi bir xil qadamlarni takrorlashimiz kerak.
Qadam 1: Quyidagi grafik uchun daraxtni chizing.
Qadam 2: Endi kesishni aniqlang. Kesish faqat bitta tiv va istalgan miqdordagi bog'lamlarni o'z ichiga oladigan nod bo'ladi.
Bu yerda C1 va C5 kesishlar.
Qadam 3: Endi matritsani chizing.
| Filial ⇒ | 1 | 2 | 3 | 4 | 5 | |
| Qismotma-qatorlar | ||||||
| C1 | +1 | +1 | -1 | -1 | 0 | |
| C5 | 0 | -1 | 0 | -1 | +1 | |
Bu talab etilgan matritsa.
Eslanish uchun nuqtalar
Eslanish kerak bo'lgan ba'zi muhim nuqtalar mavjud. Ular quyidagilar:
kesim matritsasida, chetvichka yoki dalga (twig) musbat yo'nalishda olingan.
Har bir kesim faqat bitta chetvichka (twig)ni o'z ichiga oladi.
Kesim istalgancha bog'lamlar (links) bilan ta'minlanishi mumkin.
Kesim matritsasi va Kirxof tok qonuni (KCL) orasidagi munosabat shundaki
Manba: Electrical4u.
Qisqa ma'lumot: Asl manbadan hurmat bilan, yaxshi maqolalar ulashuvchi, agar huquqlarga zid bo'lsa, iltimos, o'chirish uchun bog'laning.
