Osy termınderdiń qazaqshasy qalaı bolmaq?
1. backtracking perebor s vozvratom
2. inclusion-exclusion principle prınsıp vklúchenıı-ısklúchenıı
3. successor graph graf preemnıkov (successor paths pýt preemnıkov)
4. sink stok
5. source ıstochnık
6. scaling algorithm Algorıtm Tolyǵyraq ...masshtabırovanıaá potoka
7. general path cover Pokrytıe obshımı pýtámı
kontekstteri osyndaı:
1 rekýrsıaályq algorıtmmen baılanysty
2 yqtımaldyqytar teorıasy, vıenn dıagram
3 graftar teorıasy
4-7 graftar teorıasy, aǵyndar (potokı)
Defınısıaálary kelesideı:
1. Poısk s vozvratom, bektrekıng (angl. backtracking) — obshıı metod nahojdenıaá reshenıı zadachı, v kotoroı trebýetsá polnyı perebor vseh vozmojnyh varıantov v nekotorom mnojestve M. Kak pravılo, pozvoláet reshat zadachı, v kotoryh stavátsá voprosy tıpa: «Perechıslıte vse vozmojnye varıanty …», «Skolko sýshestvýet sposobov …», «Estlı sposob …», «Sýshestvýet lı obekt…» ı t. p.
2. Formýla vklúchenıı-ısklúchenıı (ılı prınsıp vklúchenıı-ısklúchenıı) — kombınatornaıa formýla, pozvoláúshaıa opredelıt moshnostobedınenıaá konechnogo chısla konechnyh mnojestv, kotorye v obshem slýchae mogýt peresekatsá drýg s drýgom. V teorıı veroıatnosteı analog prınsıpa vklúchenıı-ısklúchenıı ızvesten kak formýla Pýankare[1].
3. Eshe odın spesıalnyı klass orıentırovannyh grafov – grafy preemnıkov (successor graph), v kotoryh polýstepen ısqoda kajdoı vershıny
ravna 1, t. e. ý kajdoı vershıny vsego odın preemnık. Graf preemnıkov sostoıt ız odnoı ılı neskolkıh komponent sváznostı. Kajdaıa komponenta
soderjıt odın sıkl, v kotoryı mogýt vestı neskolko pýteı.
Grafy preemnıkov ınogda nazyvaıýt fýnksıonalnymı grafamı, potomý
chto lúbomý grafý preemnıkov sootvetstvýet fýnksıa succ(x), opredeláúshaıa rebra grafa. V kachestve parametra x vystýpaet vershına grafa, a znachenıem fýnksıı ıavláetsá preemnık etoı vershıny.
4,5. V zadache o maksımalnom potoke dan orıentırovannyı vzveshennyı graf, soderjashıı dve spesıalnye vershıny: ıstochnık,
v kotoryı ne vhodıt nı odno rebro, ı stok, ız kotorogo ne ısqodıt nı odno rebro.
6. Algorıtm masshtabırovanıaá propýsknoı sposobnostı2
prımenáet poısk v glýbıný dlá nahojdenıaá pýteı, dlá kotoryh ves kajdogo rebra ne menshe nekotorogo selochıslennogo poroga.
7. Pokrytıe obshımı pýtámı. Tak nazyvaetsá pokrytıe pýtámı, v kotorom dopýskaıýtsá vershıny, prınadlejashıe srazý neskolkım pýtám.
Eskertý! Habarlama qaldyrý úshin saıtqa kirý kerek.
Sarapshy mamandar
Graftar teorıasyndaǵy «polýstepen zahoda" jáne "polýstepen ısqoda» qalaı bolmaq?
Kiristiń jarty dárejesi, shyǵystyń jarty dárejesi. Salǵaraeva G.I. Graftar teorıasy: Almaty: JSHS «Dáýir», 2013. – 256-bet.
Raqmet!
Ескерту! Хабарлама қалдыру үшін сайтқа кіру керек.
Sala termınderiniń qazaq tilinde balamasy bolmaǵan jaǵdaıda termınderdiń qoldanys aıasyn, anyqtamasyn kórsete otyryp, Qazaqstan Respýblıkasy Ǵylym jáne joǵary bilim mınıstrliginiń Til saıasaty komıtetine hat joldap, bekitýdi surańyz.