Էլեկտրական շղթայի Cutset Matrix հասկացությունը

Երբ խոսքը անցնում է գրաֆի տեսության կտրված բազմության մատրիցի մասին, ընդհանուր առմամբ խոսում ենք հիմնական կտրված բազմության մատրիցի մասին։ Կտրված բազմությունը այն նվազագույն ճյուղերի բազմությունն է մի կապակցված գրաֆի մեջ, որը երբ հեռացվում է գրաֆից, ապա գրաֆը բաժանվում է երկու լրացուցիչ մասերի, որոնք կոչվում են ենթագրաֆներ, և կտրված բազմության մատրիցը այն մատրիցն է, որը ստացվում է շարքով վերցնելով մեկ կտրված բազմություն ի հայտ։ Կտրված բազմության մատրիցը նշանակվում է [Qf] սիմվոլով։

Օրինակ կտրված բազմության մատրիցի շրջահայտի համար

Երկու ենթագրաֆներ ստացվում են գրաֆից ընտրելով կտրված բազմություններ, որոնք կազմված են ճյուղերից [1, 2, 5, 6]։ Այլ կերպ ասած, կարող ենք պնդել, որ տվյալ գրաֆի հիմնական կտրված բազմությունը հանդիսանում է մի կտրված բազմություն, որը կազմված է մեկ փող և մնացած հղումներով։ Փողերը են ծառի ճյուղերը, իսկ հղումները են կո-ծառի ճյուղերը։ Այսպիսով, կտրված բազմությունների քանակը հավասար է փողերի քանակին։ [Փողերի քանակը = N – 1] Որտեղ N-ը տվյալ գրաֆի կամ ծառի հանգույցների քանակն է։ Կտրված բազմության ուղղությունը նույնն է, ինչ փողի ուղղությունը, որը դիմաց է վերցվում դրական։

Կտրված բազմության մատրից գծելու համար կա որոշ քայլեր, որոնք պետք է հետևել։ Քայլերը հետևյալն են՝

1. Գծեք տվյալ ցանցի կամ շրջահայտի գրաֆը (եթե տրված է)։

2. Ապա գծեք դրա ծառը։ Ծառի ճյուղերը կլինեն փողերը։

3. Ապա գրաֆի մնացած ճյուղերը գծեք կետագծով։ Այդ ճյուղերը կլինեն հղումները։

4. Ծառի յուրաքանչյուր ճյուղ կամ փող կկազմի անկախ կտրված բազմություն։

5. Նշեք մատրիցը շարքերով որպես կտրված բազմություն և սյուներով որպես ճյուղեր։

n = կտրված բազմությունների քանակ։
b = ճյուղերի քանակ։

Կտրված բազմության մատրիցի ուղղությունը

Qij = 1; եթե ճյուղ J-ը կտրված բազմության մեջ է ու ուղղությունը նույնն է ծառի ճյուղի ուղղության հետ։
Qij = -1; եթե ճյուղ J-ը կտրված բազմության մեջ է ու ուղղությունը հակառակ է ծառի ճյուղի ուղղությանը։
Qij = 0; եթե ճյուղ J-ը կտրված բազմության մեջ չէ։
Օրինակ 1

Գծեք հետևյալ գրաֆի համար կտրված բազմության մատրիցը։
Պատասխան
Քայլ 1 Գծեք հետևյալ գրաֆի ծառը։

Քայլ 2 Այժմ նորից որոշեք կտրված բազմությունը։ Կտրված բազմությունը կլինի այն հանգույցը, որը կպարունակի միայն մեկ փող և ցանկացած քանակությամբ հղումներ։

Այստեղ C2, C3 և C