Raqamli kutubxona Kibernetikadan matematik masalalar

§ 4, 4-banddagi tasvirlar, bu erda 9-teoremaning T to'plami
kubning o'rta qatlamidan foydalangan.
Chov vektorlari identifikatsiyalashning qulay vositasidir
chegara funktsiyalari va ularni jadval qilish uchun ishlatiladi. Chov vektori
ixtiyoriy mantiqiy funktsiya, printsipial jihatdan, yagona bo'lishi mumkin
chegara ekanligini aniqlang va agar shunday bo'lsa, yozing
uni belgilaydigan tengsizlik (1). Biroq, hal qilish uchun samarali algoritmlar
bu vazifa noma'lum.
Chow parametrlariga qiziqarli yondashuv Dertouzos tomonidan taklif qilingan [55].
Shuningdek, u olishning taxminiy algoritmlarini ishlab chiqdi
Chou vektoridagi chiziqli tengsizlik. Winder [120] amalga oshirildi
bunday olishning turli yondashuvlarini eksperimental o'rganish
yaqinlashishlar. Nazariy masalalarning eng to'liq yoritilishi,
Chow parametrlari bilan bog'liq bo'lgan Winder qog'ozida topish mumkin [122].
Xulosa qilib shuni ta'kidlash kerakki, ixtiyoriy mantiqiy funktsiya uchun
j (x 1, ..., xn) uning (n + 1) o'lchovli Chow vektorining har bir koordinatasi S (f)
faqat 0 dan 2P gacha bo'lgan butun sonlarni qabul qilishi mumkin. Shuning uchun, jami
ko'pi bilan (2n + l) n + 1 Chow vektorlari va shuning uchun ko'pi bor
(2n + l) n + 1 chegara funksiyalari [68], bu ham n2 ning yuqori chegarasini beradi.
chegara funktsiyalari sonining logarifmining asimptotikasi uchun.
3. Chegara o‘zgarishi usuli. Eshik funktsiyasi (1) n ga bog'liq
og'irliklar va chegaralar va juda murakkab ob'ekt. Sekinroq
uning o'zgarishini faqat uning chegarasini b o'zgartirish orqali kuzatib boring, ya'ni parallel ravishda
giperplanni En fazoda siljitish. Keyingi natija yaxshi
ma'lum va intuitiv ravishda aniq.
Teorema 10. T nuqtalar ixtiyoriy chekli to'plami bo'lsin
E '\ L da: a \ X \ + ... + anxn = 6 - bu orqali o'tmaydigan giperplan.
to'plamning nuqtalari T. Keyin giperplanning istalgan parallel siljishi
T to'plamining ko'pi bilan bitta nuqtasini o'z ichiga oladi yoki bunga erishish mumkin
a \, ..., an qiymatlarini ajratishni o'zgartirmasdan o'zgartirish orqali
G to'plam nuqtalarining giper tekisligi.

16-bet

MATQIY FUNKSIYALARNING EOS FUNKSIYALARI VA BOSHQA FUNKSIYALARI 19.
Isbot. Parametr maydonida (a \, ..., an)
Biz markazi giperplanning pozitsiyasi bilan berilgan d o'lchamli to'pni olamiz,
radius shunchalik kichikki, giperplanning har qanday pozitsiyasi uchun,
to'p ichidagi nuqta (ai, ..., a) va b ning oldingi qiymati bilan berilgan, undagi
to'plamning nuqtalari T. Ikki ixtiyoriy ti nuqtasi uchun t2 * = T
parametr qiymatlari to'plami (ui, ..., an) uchun
b ni o'zgartirib, ikkala nuqtani giper tekislikka joylashtirish mumkin,
shart bilan berilgan
(ha, •••> cin) ^ - (t2 - ti),
ya'ni, bu giperplandir. Teoremaning tasdiqlanishi shundan kelib chiqadi
Bunday gipertekisliklarning chekli soni (n - 1 o'lchamdagi) mumkin emas
z o'lchamli to'pni yoping.
10-teorema darhol har bir chegarani nazarda tutadi
n o'zgaruvchining funktsiyalarini faqat chegarani o'zgartirish orqali olish mumkin
2p + 1 xil funktsiyalar, kubning 0 dan 2P gacha cho'qqilarini kesib tashlash {0, 1} p.
Endi b chegarasi emas, balki og'irlikdan biri o'zgarmasin
koeffitsientlar, masalan, ap. Biz {0, 1}?R kubini ikkita pastki kubga ajratamiz: xn = 0 va
xn = 1. Har ikkala pastki kubda (1) funktsiya chegara funktsiyasidir. Podkubda
xn - 0 tengsizlik bilan beriladi
a \ X [+ ... + anxn ^ b (9)
va o'zgaruvchan ap bilan o'zgarishsiz qoladi. Pastki kubda xn = 1 she
tengsizlik bilan berilgan
a \ X \ + ... + an- \ xn- \ ^ b - an,
a o'zgaruvchan bo'lsa, bu erda 2rj “1 + 1 turli funktsiyalar paydo bo'ladi.
Shunday qilib, n - 1 o'zgaruvchining har bir chegara funktsiyasidan (9),
ap koeffitsientiga turli qiymatlarni belgilash orqali olish mumkin
2a ~ i _f_ n o‘zgaruvchining 1 funksiyasi, ya’ni,
Nn> (2n - '+ l) Nn-1 [44, 124]. (o'n)
(10) dan foydalanib, biz olamiz
LG "> D 2 '= 2P (P" 1) / 2,
Bu (6) da pastki chegarani beradi.
Aslida, (10) da har doim qat'iy tengsizlik mavjud, shuning uchun
dagi funktsiyani o'zgartirmaydigan (9) dagi og'irliklarning kichik o'zgarishi sifatida
subkubi xn = 0 bo'lsa, biz xn = 1 subkubidagi b ning o'zgarishi bilan bunga erishishimiz mumkin.
ba'zi yangi xususiyatlar paydo bo'ldi. Biroq, asimptotikani yaxshilang
(6) dagi pastki chegaraning logarifmi shu tarzda muvaffaqiyatsizlikka uchradi [124].
3-bo'limda olish uchun chegara o'zgarishi usuli qo'llaniladi
berilgan kardinallikning chegara to'plamlari sonining taxminlari, shuningdek
bilan chegara funktsiyalarining keng sinfi mavjudligini isbotlash
eksponensial murakkablik d. va. f.
4. Mantiqiy funksiyalarning boshqa sinflari bilan bog‘lanish. Chegara funktsiyasi
(1) manfiy bo'lmagan og'irliklar bilan monotonlik aniq. Agar
ammo a \, ..., an og'irliklari orasida manfiy og'irliklar mavjud, keyin x \ -> • o'rniga
1 - Xi undan monotonni olishingiz mumkin. O'rnini bosuvchi funksiya
ularning inkori bo'yicha ba'zi o'zgaruvchilar o'zgartirilishi mumkin
monotonga aylanadi, bir hil deyiladi. Chegara funktsiyalari:
Shunday qilib, bir hil va monoton polning Nn soni
funksiyalar munosabat bilan chegara funktsiyalarining umumiy soniga bog'liq
Nn

17-bet

Yu. A. Zuev
yigirma
Monoton kabi, qisqartirilgan dn. f. bir hil funktsiyalar
uning yagona boshi berk ko'cha, eng qisqa va minimal d. n. f ..
Har bir harf ushbu dnga kiritilishi mumkin. f. yoki faqat inkor etmasdan,
yoki faqat inkor qilish bilan. f ~ l (0) va / -1 (1) to'plamlar bir hil
funktsiyalari / bog'langan, ya'ni ularning har birini o'tish orqali chetlab o'tish mumkin
har safar qo'shni cho'qqiga va to'plam chegaralaridan chiqmasdan. bu
chegara funksiyalari uchun ham amal qiladi.
Bayonot 3 [68]. To'plamlar / _1 (0) va (1) chegara
f funksiyalari ulanadi.
Endi biz ^ -qiyoslanadigan funksiyaning umumiy tushunchasiga murojaat qilamiz.
f (x 1, ..., xn) mantiqiy funktsiya, bb ..., xn) ixtiyoriy bo'lsin.
uning o'zgaruvchilari to'plamining kichik to'plami. Bir oz to'plam bo'lsin
G dan o'zgaruvchilar qiymatlari, biz (G = a) / - funktsiyasi bilan belgilaymiz
n - \ G \ o'zgaruvchilar {x \, ..., xn) \ G ni tayinlash orqali / dan olingan
Ruxsat etilgan qiymatlar to'plamining G to'plamining o'zgaruvchilari a.
Eshik funksiyalarini o‘rganishda quyidagi tushuncha muhim rol o‘ynadi.
Har qanday G, \ G \ = k bo'lsa, / funksiyasi k-qiyoslanadigan deb ataladi.
2k funksiya (C = a ") /, i = 1, 2, ..., 2 \ tayinlash orqali olingan
barcha mumkin bo'lgan qiymatlarning G to'plamining o'zgaruvchilari chiziqli tartiblangan,
ya'ni har qanday i uchun j munosabatlarning kamida bittasi (G = a) / ^
^ (& = "*) / Yoki (G = Oi) / ^ (G = ai) /. Bu aniq (k + 1 solishtirish mumkin
funktsiya / c bilan solishtirish mumkin.
Endi bir hil funktsiyani 1-taqqoslash mumkin, deb belgilash mumkin,
a / r bilan taqqoslanadigan funksiya to'liq taqqoslanadigan deb ataladi.
To'liq taqqoslash [ft / 2] - taqqoslanuvchanlik [116] dan kelib chiqishini ko'rsatish oson.
Uinder texnik jihatdan ancha qiyin natijani isbotladi.
1 (k - 1) - taqqoslanadigan funktsiyalar sinfining o'ziga xos kichik sinfidir.
Chegara funktsiyalari aniq taqqoslanadi,
o'zgaruvchilarning ma'lum bir kichik to'plamiga tayinlashdan beri har xil
qiymatlar to'plami faqat farq qiladigan chegara funktsiyalariga olib keladi
chegara qiymatlari. Elliginchi yillarning o'rtalarida bor edi
to'liq solishtirish sharti pol uchun etarli degan gipoteza
bolalar. Bu 1957 yilda E. F. Mur tomonidan rad etilgan edi
12 o'zgaruvchili funktsiyaga misol, uni butunlay solishtirish mumkin, ammo emas
chegara (qarang [2, 86]). Keyinchalik kompyuter yordamida hammasi aniqlandi
8 ta oʻzgaruvchini oʻz ichiga olgan holda toʻliq taqqoslanadigan funksiyalar mavjud
ostona va Gabelman [60] to'liq misol keltirdi
9 ta o'zgaruvchining taqqoslanadigan funktsiyasi, bu chegara emas. Chunki
chegara funktsiyalari sinfi yig'ilmaydigan funktsiyalar sinfiga to'g'ri keladi, keyin
quyidagi teorema, Elgot tufayli, Win natijalari bilan birga
Dera shartning noadekvatligi haqida / bo'sag'a uchun c-summability
sinfga o'zlarining chegara funktsiyalarini to'liq joylashtirishlarini ko'rsatish
solishtirish mumkin.
11-teorema [57]. To'liq taqqoslanadigan funktsiyalar sinfi bir xil
2 ta yig'ilmaydigan funktsiyalar sinfi bilan.
Isbot. To'liq solishtirish mumkin bo'lmasin.
Keyin qiymatlar to'plami va ba'zi bir kichik U mavjud
o'zgaruvchilar va ikki xil qiymatlar to'plami y va e ostida uni to'ldiradi
shunday o'rnatadi
/ (u, v) = 1;
/ (u, v) = 0;
/ (u, e) = 0;
/ (u, e) = 1.
(11) va (12) dan (U = u) / (U = u) / va dan kelib chiqadi.
(VA)
(12)
(13)
(o'n to'rt)
(13) va (14)

18-bet

MATQIY FUNKSIYALARNING EOS FUNKSIYALARI VA BOSHQA FUNKSIYALARI 21.
(t / = u) / «(- [/ = u) /, bu funksiyalarning solishtirilmasligini (U ~ u) f i ifodalaydi.
(^ / Vektor sifatida juftlarni qo'shish to'plamlar (11), (14) va in
(12), (13), biz bir xil summalarni olamiz
(u, v) + (u, e) = (u, v) + (u, e),
ya'ni funktsiya / 2-summable. Shunday qilib, 2-sinf aqldan ozgan dunyo emas
funktsiyalar to'liq taqqoslanadiganlar sinfiga kiradi.
Faraz qilaylik, aksincha, / funksiyasi 2-summable. Keyin
shunday x, y, z, h to'plamlar mavjud
/ (x) = 1,
/ (Y) = 0,
I z) = o,
/ (h) -1
va
x + h = y + z. 5)
(15) shartga ko'ra x, y, z, h to'plamlarda faqat shular
jadval ustunlarida yozilgan ix koordinatalari qiymatlarining kombinatsiyasi. 1.
Koordinatalarni tanlang,
qadriyatlar kombinatsiyasiga ega
birinchi yoki ikkinchisida bo'lgani kabi
jadval ustunlari. Kichik toʻplam
bu koordinatalarning qiymatlari
x to'plami va bilan belgilanadi.
Keyin z to'plamida bu
pastki to'plam ham va ga teng bo'ladi,
a_x va y to'plamlarida u teng
va. To'ldiruvchini belgilash orqali
uning x to'plamlardagi kichik to'plami
va y dan v gacha, va z va h dan e gacha bo'lgan to'plamlarda (II) - - (14) tenglikni olamiz,
ya'ni taqqoslanmaslik shartlari. Shunday qilib, u ham sodir bo'ladi
teskari inklyuziya va butunlay taqqoslanadigan funktsiyalar sinfiga tegishli
sinf 2-summable emas, ya'ni bu sinflar mos keladi. Teorema
isbotlangan.
Mantiqiy funktsiyalarning ichki o'rnatilgan sinflari tizimi sxematikdir
rasmda ko'rsatilgan. 6.
Keling, 2-qiyoslanadigan funktsiyalarning muhim sinfini batafsil ko'rib chiqaylik.
Avval f (xi, ..., xn) ixtiyoriy mantiqiy funktsiya bo'lsin. Menga
/
bir xil o'zgaruvchilarda (x \, ..., xn) biz "^" munosabatini quyidagicha kiritamiz
yo'l:
/
X \ Xj (xi - - 1, Xj g_ ~ 0) / fa ~ 0, Xj = 1) /.
12-teorema [84, 116]. Ixtiyoriy mantiqiy funktsiya uchun
f (xi, ..., xn) "U" munosabati o'zgaruvchilar to'plamida o'tishli
{xi xn}.
o'n bir
Isbot. nz Xj xh quyidagi ekanligini ko'rsatish kerak
em Xi = ^ xk. Umumiylikni yo'qotmasdan, biz i = 1, j = 2, k = 3, deb faraz qilamiz,
x a {n - 3) bilan belgilaymiz - o'lchovli mantiqiy to'plam. Aloqa ta'rifidan
/
Bizda "= ^" mavjud
/
x \ = /
x2 x3 <=> / (a! Ox) ^ / (a01x).
1-jadval
X
1
0
1
0
1
0
bor
0
1
1
0
1
0
Z
1
0
0
1
1
0
h
0
1
0
1
1
0
(in)
(17)

19-bet

22
Yu A, Zuev
Ko'rsatish kerakki, / (1 [} 0x) / (110x) ^ / (011x). (16) va (17) ni qo'llash orqali biz olamiz
/ (100x) / (110x) Teorema isbotlangan.
/
a = ph> munosabati antisimmetrik emas, shuning uchun qat'iy
gapirganda, uni qisman tartib deb atash mumkin emas. Ammo kirsangiz
ekvivalentlik munosabati
/ 1 /
Xi ~ Xj <=> Xi Xj & Xj Xi,
keyin ekvivalentlik sinflari to'plamida qisman tartiblanish paydo bo'ladi.
Funktsiya / har bir sinfdagi o'zgaruvchilarga nisbatan simmetrikdir
ekvivalentlik.
Guruch. 6
Agar f (x 1, .., xn) 2-qiyoslanadigan funksiya bo'lsa, uning har bir juftligi uchun
/ 1
o'zgaruvchilar, munosabatlarning kamida bittasi 24 = ^ Xj yoki £ j = ^ £ i tutadi.
Shuning uchun, o'zgaruvchilarni qayta tartibga solish orqali munosabatlarning bajarilishiga erishish mumkin
1 111
xn xn-r x2 = ^ xb shunday qilib birlikning "ahamiyati" bo'ladi
qanchalik baland bo'lsa, u tezroq sodir bo'ladi.
Monoton 2-qiyoslanadigan funksiya f (xi, ..., xn), uning o'zgaruvchilari
/ 111
to'da xn xn_1 munosabatda bo'ladi x1r deyiladi
muntazam.
Muntazam funktsiyani quyidagi ma'no bilan tavsiflash mumkin:
birliklarni to'g'riroq pozitsiyalarga ko'chirishda yoki ularning mulki
funktsiya qiymatini o'chirish oshmaydi. Shuning uchun bo'lishi mumkin
aksini aniqlang, kubning cho'qqilari to'plamiga (0, 1} n deb ataladigan narsani kiriting.
kanonik qisman tartib.
X, y ^ {0, 1} n uchlari munosabatda deymiz
Kimga
kanonik tartibdagi x n tengsizliklar amal qiladi
taxminan 7
2 ^ Jfii / “1? 2, 71,
i = li = X

20-bet

BOSH FUNKSIYALARI VA BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 23
E'tibor bering, x y x y ni bildiradi, ya'ni "= s (" munosabati o'z ichiga oladi
munosabat "= <". Endi oddiy Mantiqiy funksiya / bo'lishi mumkin
kanonik tartibni saqlash sifatida belgilang:
x = Muntazam funktsiyalar 60-yillarda Weedeh tomonidan ko'rib chiqilgan
rum [116, 117], Xu [68] va keyinroq boshqa mualliflar tomonidan (qarang: havolalar
[53]). {0, 1} n dagi kanonik tartib ko'p marta ko'rib chiqilgan
turli vaziyatlarda matematiklar. Qisman buyurtma qilingan
kanonik tartib to'plam (O, 1} va darajali, funktsiya
daraja shaklga ega
r (x) \ u003d PX1 + (n - 1) X2 + ... + 2xn- \ + xn.
Agar y cho'qqi x cho'qqini qoplasa, g (y) = g (x) +1, ya'ni x.
y dan ba'zi birliklarni bir pozitsiyani o'ngga siljitish orqali olinadi, yoki
oxirgi birlikni o'chirish. Keyinchalik, [98, 107] dan kelib chiqqan holda, bu
qisman tartiblangan to'plam - Sperperian, ya'ni.
uning antizanjirning maksimal kuchi maksimal quvvatga to'g'ri keladi
bir xil darajadagi to'plamlar. Ketma-ketligi bir xil tartiblangan
kuchlar A (r), r = 0, 1, ..., n (n + 1) / 2, bu koeffitsientlarga to'g'ri keladi
polinom (1 + q) (1 + g2) ... (1 + <7P), simmetrik va unimodaldir. Uning
maksimal r = [n {n + 1) / 4] da erishiladi va asimptotik ravishda tengdir.
(2/3) 1/2ft “3/22n [88]. Demak, muntazam funksiyalarning Rn soni uchun
[92] logi?n ^ (2 / 3l) 1/2 n ~ 22n ni olamiz.
Bu yerda I bilan muntazam funksiyalarning Rn (l) soni uchun ekanligini ham qayd etamiz
pastroq bo'lganlar, [13] da isbotlangan quyidagi taxminni tasdiqlaydi:
Jn (/ K (/ r + 1) *. (18)
5. Chegaraviy grafiklar. Ushbu bo'lim faqat qamrab oladi
oddiy yo'naltirilmagan grafiklar G = (V, E) bir nechta qirralari va halqalarisiz,
Bu yerda V - cho'qqilar to'plami, E - qirralar to'plami. Har qanday V '^ V uchun
G / = (V /, E ') grafigi G grafigining induksiyalangan pastki grafigi deb ataladi,
agar G 'dagi ikkita cho'qqi qo'shni bo'lsa, agar ular qo'shni bo'lsa
da G. Grafikning cho'qqilari kichik to'plami mustaqil deyiladi if
undagi cho'qqilar juft-juft qo'shni emas, ya'ni induksiyalangan pastki grafigi bo'sh. Bo'ylab
I (u) k ga tutashgan cho'qqilar to'plamini, darajani bildiradi
uchlari deg u = \ I {v) i. Agar v cho'qqisi dominant deb ataladi
qolganlarning hammasiga qo'shni, ya'ni deg v = \ V \ - 1. Agar qo'shimcha ravishda
grafikning dominant cho'qqisiga to'g'ri kelmaydigan qirralari yo'q, keyin u
yulduz deb ataladi.
Monoton mantiqiy funktsiyani ko'rib chiqaylik ph: {0, 1} n - * ■ {0, 1}, hammasi
ikki harfdan iborat oddiy implikatsiyalar, ya'ni pastki
ph funksiyaning birliklari 2-qatlamda yotadi. U bilan G (ph) = (7, E) grafigini boglaymiz,
V yakka-birda joylashgan uchlari to'plami
o'zgaruvchilar to'plami bilan yozishmalar {x, ..., xj, va qirralarning to'plami - bilan
oddiy pmplikantlar to'plami, ya'ni implikant x-xx $ chetiga mos keladi
(i, y) e E. Bu birma-bir yozishmalarni o'rnatadi
grafiklar va monoton mantiqiy funktsiyalar o'rtasida, hammasi pastroq
2-qatlamda yotadi. Shuning uchun bunday funksiyalar deyiladi
grafik. Agar ph chegaraviy grafik funktsiya bo'lsa, unda mos keladigan uchun
uning grafigi, bu chiziqli tengsizlik mavjudligini anglatadi (1),
cho'qqilarning mustaqil kichik to'plamlarini qaramlardan ajratish. Bunday grafiklar
chegara deb ataladi. Xvatal va Hammer [49] tomonidan kiritilgan, ular
o'rganish uchun juda samarali ob'ekt bo'lib chiqdi: biri bilan
boshqa tomondan, ularning sinfi juda vakili; boshqa tomondan, ular topadilar

21-bet

24
10. A. ZUEV
grafik nazariyasida yuzaga keladigan deyarli hamma narsaga keng qamrovli yechim
savollar. Ular allaqachon [49] da chuqur o'rganilgan. Keyinchalik
keyin nashrlar oqimida biz asarlarni [64, 65], shuningdek, monografiyani qayd etamiz.
[62], bu masalalarni batafsil ko'rib chiqish. Ularni tavsiflash
asosiy xususiyatlarni [5] va undan to'liqroq topish mumkin
Bibliografiyaga qarang [38].
Chegaraviy grafiklar uchun yuqoriga ko'tariladigan ko'plab xarakteristikalar ma'lum
asosan [49] ga. Keling, eng qiziqarlisini teorema shaklida tuzamiz
ushbu ko'rib chiqish kontekstida.
Teorema 13. G = (V, E) grafik uchun quyidagi shartlar.
ga teng:
1) xarakteristikani ajratuvchi chiziqli tengsizlik mavjud
bog'liqdan mustaqil to'plamlar vektorlari;
2) Ca, Pa G grafigining induksiyalangan subgraflari orasida mavjud emas
va 2K <2 (7-rasm);
-yy
'hl
> <
, rn T 'i
xr
Guruch. 7
3) bir cho'qqili grafikdan G grafigini olish mumkin
ajratilgan yoki dominant cho'qqilarning ketma-ket qo'shilishi;
4) har qanday u, v e V uchlari uchun kamida bittasi
munosabatlar: I (u) \ v ^ I (v) yoki I (v) \ u ^ I (u);
5) shunday a1, ..., an va b haqiqiy sonlar mavjud
(r, /) ^ E - <=> - a, i + aj> b.
Biz dalilning asosini [49] dan keyin keltiramiz
Quyidagi ikkita oson tasdiqlanadigan bayonot: a) har qanday induktsiya
pol grafigining pastki grafigi pol va b) olingan grafik
izolyatsiya qilingan yoki dominant cho'qqini qo'shish orqali chegaradan,
chegara hisoblanadi. a) dan chegara grafigi mumkin emasligi kelib chiqadi
C ±, Pa yoki 2K2 induktsiyali subgraflarni o'z ichiga oladi, chunki
Tegishli grafik funktsiyalar 2 ta yig'iladigan va,
shuning uchun chegara emas. Shuning uchun 2-shart) zarur
chegara va 3-shart) b) ga ko'ra etarli. Ko'rsatish qiyin emas
Bundan tashqari, ixtiyoriy grafikda izolyatsiya qilingan yoki mavjud
dominant cho'qqisi yoki uning induktsiyalangan pastki grafigi bor,
izomorf C4, Pa yoki 2Kb Haqiqatan ham, izolyatsiya qilingan bo'lsa ham va
dominant cho'qqilar mavjud emas. Agar x \ maksimal darajali cho'qqi bo'lsa,
xb & 1 (x1), xa ^ 1 (x3), keyin deg ^ i ^ deg ^ sharti nazarda tutiladi.
X2 cho'qqisining mavjudligi X2 '> 1 (x \) va X2 & 1 (xa) va bu shuni anglatadiki,
x, x2, x3, xa uchlari tomonidan induktsiya qilingan pastki grafik bittaga izomorf
rasmda keltirilganlardan. 7 ta grafik. Shuning uchun, rekursiyadan foydalanib,
agar 2) shart bajarilsa, biz 3) shartda talab qilinadigan narsani olamiz.
cho'qqilarning tartiblanishi va shuning uchun pol. Bu isbotlaydi
shartlarning ekvivalentligi 1) –3).
4) shart 3) dan kelib chiqadi va 4) 2) ni nazarda tutadi. Va nihoyat,
5) shartning chegaraga ekvivalentligi isbotlanganidan kelib chiqadi
Shartning grafik funksiyasi uchun ekvivalentlik bayonoti 2
2-qatlamda yig'ilmasligi va yig'ilmasligi. Bu isbotni to'ldiradi.

22-bet

BOSH FUNKSIYALARI VA BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 25
13-teoremaning 2) -5) shartlaridan istalgan biri bilan tekshirish mumkin
polinom vaqti, shuning uchun grafik chegarasini tanib olish muammosi
polinom echilishi mumkin. Bundan tashqari, barcha subgraflar ajratilgan
2-shart) 2-summable funksiyalarga mos keladi, shuning uchun
2-jamlanmaylik shartdan grafik funksiyaning chegarasi uchun yetarli
4) bundan kelib chiqadiki, hatto 2-qiyoslash ham yetarli. Nihoyat, 3 dan)
shundan kelib chiqadiki, aniq 2n_1 izomorf bo'lmagan chegara grafiklari mavjud,
Belgilangan chegara grafiklari n \ 2n_1 dan kichik, bu ahamiyatsiz
umumiy sonining bir qismi 2n (n-1) / n etiketli uchlari bilan 2 ta grafik.
Garchi chegaraviy grafiklar kam bo'lsa-da, har qanday G grafigi mumkin
uning har bir chetiga kirib borishi uchun ostonaga parchalanadi
parchalanish grafiklaridan kamida bittasiga. Minimal chegaralar soni
Bunday parchalanishdagi grafiklar G grafigining chegara soni t (G) deb ataladi.
Shunday qilib, chegaraviy grafiklar chegara soni 1 ga teng bo'lgan grafiklardir.
Grafikning pol dekompozitsiyasi muammosi polga ekvivalentdir
mos keladigan grafik funksiyaning tasviri, ularning chegara raqamlari
mos.
14-teorema [49]. Ixtiyoriy n-cho'qqilarning chegara soni uchun
G grafigi t (G) ^ n - a (G) bahosini qanoatlantiradi, bunda a (G) -
mustaqil to'plamning maksimal kardinalligi va agar G grafigida bo'lmasa
uchburchaklar, keyin tenglik belgisi smetada joy oladi.
Isbot. G = (Vn, E), k = n - a (G) bo'lsin. Bo'lsin,
bundan keyin 5 - mustaqil kardinallik to'plami a (G), Vn \ S = {vi, ..., vh}.
Har bir y -, p = 1, 2, ..., k uchun E {kesilgan qirralarni belgilaymiz.
Vu U holda har bir grafik Gt = (Fn, Et) yulduzdir va shuning uchun
13-teorema bo'yicha, chegara grafigi. G * grafiklarini pol sifatida qabul qilish
G grafigining parchalanishi, biz kerakli taxminni olamiz.
Endi G grafigida uchburchaklar bo‘lmasin. Keling, chegarani olaylik
G ning pol grafiklarining t = t (G) ga parchalanishi Gi = (Vn, E {). Qanday oson
13-teoremadan kelib chiqadiki, uchburchaklarsiz har bir chegara grafigi kerak
yulduz bo'l, shuning uchun G { yulduzdir. {ui, ..., vt} cho'qqilari bo'lsin
bu yulduzlarning markazlari. Keyin hodisa qirralari to'plami mos keladi
G grafikning barcha qirralarining E to‘plami va F „\ cho‘qqilar to‘plami (z; i, ..., vt)
mustaqildir. Demak, a (G) ^ n - t (G) dan kelib chiqadi
tenglik o‘rnatiladi.
14-teorema ikkita muhim natijaga ega.
Xulosa 1.max t (G) ~ n, n ~> oo,
G = (Vn, E)
Xulosa 2. Grafikning chegara sonini aniqlash masalasi
NP-qattiq.
Xulosa 1 Erdsning [58] mavjudligi haqidagi natijasidan kelib chiqadi
a (G) = o (n), n ° o bo'lgan uchburchaklarsiz G = (Vn, E) grafiklari.
Natija 2 Polyakning muammoning UR-qattiqligi bo'yicha [95] natijasidan kelib chiqadi.
uchburchaksiz grafiklar sinfida (G) ni topish.
Chegaraviy grafiklar va gipergraflar qo'llanilishini topdi
parallel dastur bajarilishini nazorat qilishda dasturlash (qarang [62,
67, 90]). Samarali parallel tashkil etish talab qilinsin
n ta dasturning bajarilishi va bir qator cheklovlardan iborat
ba'zi bir juft dasturlarni bajarib bo'lmaydi
bir vaqtning o'zida (masalan, xotira cheklovlari tufayli). Keyin, agar grafik
taqiqlar - bu chegara, keyin hisoblash jarayonini nazorat qilish
"semafor" deb nomlangan o'zgaruvchi yordamida qulay tarzda tashkil etilgan.
Uning joriy qiymati chegaradan bajarilgan og'irliklar yig'indisiga teng
topshiriqlar vaqtida. Ba'zi bir vazifaning oxirida uning og'irligi
"semafor"ga qo'shiladi, yangisi qo'shilsa, ayiriladi.
Nazorat dasturi "semafor" qiymati har doim bo'lishini ta'minlaydi
salbiy bo'lmagan.

23-bet

26
Yu. A. Zuev
Agar taqiqlash grafigi chegara bo'lmasa, uni qabul qilish mumkin
ostona dekompozitsiyasi, bir nechta "semaforlar" dan foydalaning. Nihoyat,
agar taqiqlar juftlikda emas, balki yuqori quvvatda ko'rsatilgan bo'lsa
pastki to'plamlar, keyin gipergrafiya nuqtai nazaridan tasvirlangan ushbu muammoga,
xuddi shunday tartib amal qiladi [62]. Aslida, bu erda umumiy muammo bor
monoton mantiqiy funktsiyaning chegaraviy ifodasi, pastroq
ularning birliklari minimal taqiqlangan kichik to'plamlar tomonidan berilgan
dasturlari. E'tibor bering, r> 3 uchun r-regular gipergraflar uchun
4) yoki 5) turdagi shartlar endi chegara uchun etarli emas
sti [102].
Grafikdan tashqari, monotonning yana bir kichik toifasi mavjud
Birma-bir qo'yish mumkin bo'lgan mantiqiy funktsiyalar
chegara funktsiyalari mos kelishi uchun grafiklar bilan yozishmalar
chegara grafiklari. Bular 2-taklifda ko'rib chiqilgan monoton funktsiyalardir,
barcha yuqori nollari 2-qatlamda joylashgan. Agar ph (o? b ..., xn) shunday bo‘lsa.
funksiya bo'lsa, uning grafigi quyidagicha aniqlanadi. Hali ham
Grafikning uchlari o'zgaruvchilarga mos keladi va chekka (i, /) E ga tegishli.
agar mantiqiy to‘plam i-chi va i-chi o‘rinlarda bo‘lsa
pozitsiyalar funktsiyaning yuqori noli bo'lib, qarang. kabi funktsiya uchun
grafik uchun, 2-bandga muvofiq yig'ilmaslik
2-qatlamdagi yig‘ilmasligiga ekvivalent. Demak, ph funksiyasi chegara funksiyasidir.
agar va faqat chegara mos keladigan bo'lsa
£? (ph) grafigi va 13-teorema shunday xarakteristikalar beradi
ikkinchi qatlam ichida yotadigan chiziqli bo'linadigan to'plamlar. Bunday
xarakteristikasi keyingi kichik bo'limda shakllantiriladi va