Лекция Графтарды қолдану Графтарда қуат және ток үшін Кирхгоф теңдеулері. Графтарда ішкі және сыртқы тұрақтылық. Графтарда транспорттық желілер
жүктеу/скачать 200,54 Kb.
|
14-лекция
| 16-анықтама. Егер кез келген υ Î V \ U үшін,
U ∩ D(υ) ≠ Ø (48) шарт орындалса, яғни U ға тиісті болмаған кез келген υÎ V төбе U дан алынған доғалар басталуының кемінде бір төбесіне байланысты болса, онда UÎ V жиын сырттан тұрақты жиын деп айтылады. Мысал-38. 38-сызбада берілген D бграф және U1={υ1}, U2={υ1,υ3}, U3={υ2,υ4}, U4={υ1, υ2}, U5={υ1,υ2,υ3} жиындардан U2,U3,U5 жиындар сырттан тұрақты болады. 17-анықтама. Егер UÎ V сырттан тұрақты жиыннан кез келген бір төбені алу нәтижесінде сырттан тұрақты болмаған жиын құралса, онда U минимал сырттан тұрақты жиын деп айтылады. Көбінесе практикалық мәселелерді шешу кезінде сырттан тұрақты жиындардың төбелері минимал санды болған жиынды табу өте қажет болып есептеледі. Ал олар минимал сырттан тұрақты жиын ішінен табылады. Мысал-39. 38-мысалдағы U2,U3 минимал сырттан тұрақты жиындар болып есептеледі. Ал U5 жиын минимал емес, себебі U5 жиыннан υ2 төбені алу нәтижесінде тағыда сырттан тұрақты болған U2 жиын құралады. ψ(D) арқылы D бграфтың барлық минимал сырттан тұрақты төбелер жиынын белгілейміз. Онда β ( D ) = min │ U │ UÎ ψ(D) сан D бграфтың сырттан тұрақтылық саны деп айтылады. Минимал сырттан тұрақты жиындар үйірін табудың Магу әдісі. Айталық V={υ1,…,υn} болған D=(V,X) бграф және D дан алынған кез келген UÎ V төбелер жиыны берілген болсын. Тағыда алдынғы тақырыпта қолданылған Y1,…,Yn бульдік айнымалыларға сәйкес <ε1,…,εn> бағалар тізімінен пайдаланамыз. Бұл жерде сырттан тұрақты U жиынның анықтамасындағы (48) шарт кез келген iÎ{1,2,…,n} үшін кемінде төмендегі шарттардың біреуіне теңдес екенін байқаймыз: υiÎ U U∩D(υi) ≠ Ø (яғни jÎ{1,2,…,n}:υj ÎU, υjÎD(υi)) және тағыда (41) шарт бойынша n n жүктеу/скачать 200,54 Kb. Достарыңызбен бөлісу:
|