Kantorning diagonal usuli. Oqim miqdori tushunchasi. Yig’indi va qatorlar algoritmlarining tahlili

Isbot (diagonal usuldan foydalangan holda): To'plamning son-sanoqsizligini isbotlash uchun, uning ba'zi bir qismining hisobsizligini isbotlash uchun etarli. Fi (x) shaklidagi bitta o'zgaruvchining funktsiyalarini ko'rib chiqamiz. Bitta o'zgaruvchining funktsiyalarining sanab bo'ladigan to'plami bo'lsin, ya'ni. ularni qayta nomlash mumkin. FO (x), E1 (x), F2 (x), ... b (x) = E (x) +1 funktsiyasini tuzamiz. Bu diagonali deb ataladigan funktsiya G (0) = Eo (0) +1, G (1) = X1 (1) +1, b (2) = E2 (2) +1 va boshqalar. 6-sanab o'tilgan barcha funktsiyalardan farq qiladi, chunki u har bir funktsiyadan kamida bitta nuqtada farq qiladi. U E0 (x) funktsiyadan x = 0 nuqtada, F1 (x) funktsiyadan x = 1 nuqtada va hokazo bilan farq qiladi. Biroq, qurilish bo'yicha G (x) bitta o'zgaruvchining arifmetik funktsiyalari to'plamiga tegishli, shuning uchun u ro'yxatda bo'lishi kerak, ya'ni. ushbu funktsiyalardan biriga mos

Bizda qarama-qarshilik bor, shuning uchun boshlang'ich taxmin noto'g'ri va bitta o'zgaruvchining son-sanoqsiz funktsiyalari mavjud. Shunday qilib, n o'zgaruvchilarning barcha funktsiyalari son-sanoqsizdir.

2. Oqim miqdori tushunchasi.
Oqim miqdori

Biz tarmog'imizdagi ikkita uchni tanlaymiz – s manba, va t drenaj(stok) t (s  t).

S tarmog'idagi s dan t gacha bo'lgan oqim orqali biz f: E  R shaklidagi quyidagi shartlarni bajaruvch ixtiyoriy funktsiyani nazarda tutamiz

f(u, v)  с(и, v) xar bir qirra u, v  Е (o’tkazuvchanlik qobiliyatini chegarasi),

f(u, v) = — f (v, u) (антисимметриklik)

va

Div f (v) = 0 xar bir uch v  V \{s, t} (oqimni saqlash).

W(f) = Div f (s)-miqdorni f oqimning miqdori deb ataymiz.

S tarmoqning А  V (А  , А  V) qism to’plamiga mos Р(А) kesim deb , u, v  Е, u  А и v  V\A , kabi qirralar to’plamini tushunamiz.

• 
  S tarmog'idagi ixtiyoriy f oqim uchun, P(A) kesim orqali oqim tabiiy ravishda quyidagicha aniqlanadi:
  

Лемма 1.Agar s  А va t  V\A, u holda S dagi ixtiyoriy f oqim uchun t da W(f) = f(A, V\A) — f(V\A, A) bo’ladi.

Isbot. Hamma A. uchun Divf (v) = 0 tenglamalarni umumlashtiramiz. Bu yig'indisi p (ortiqcha) va minus belgisi bilan berilgan bir qator atamalardan iborat va hech bo'lmaganda bitta vertikal, v esa A ga tegishli bo'lsa. A ga tegishli, keyin f (u, v) Divf (u) ga ortiqcha ishora bilan va Divf (v) da minus belgisi bilan paydo bo'ladi (va Divf (r) ifodasida va v dan boshqa har qanday r uchun ko'rinmaydi), F (u, v) va  A, v  V \ A shartlarining har biri aniq bir marta Divf (u) belgisi bilan paydo bo'ladi, bu esa f (A, V \ A) ni beradi. ) F (u, v) va  V \ A, v  A o'xshash atamalar f (V \ A, A) atamasi uchun javobgardir. Boshqa tomondan, bizning yig'indimiz Divf (s) = W (f), chunki har bir v  A \ {s} uchun Divf (v) = 0. A A = V \ {t} ni olsak, ushbu holatda Lemma 1-dan olamiz

Divf(s) = W(f) = f(V\{t}, {t}) – f({t}, V\{t}) =

= – (f({t}, V\{t}) – f(V\{t}, {t})) = – Divf(t),

bu intuitiv haqiqatni ifoda etadi: manbadan keladigan oqim miqdori aniq drenajga kiradi. Umumiy holda, Lemma 1 oqimning umumiy miqdorini s ni t dan ajratadigan ixtiyoriy bo'limda o'lchash mumkinligini aytadi.

P (A) kesimning o'tkazuvchanligini aniqlang: