بررسی یالهای درختی بر پایه برش کمینه

برای یک گراف ظرفیت دار (V,E)=G، درخت (V,E(T)) = T را یک درخت گوموری – هوگوییمهر گاه برای هر یال set [عینا همانند مقاله] E(T) مجموعه یالهای (W) [عینا همانند مقاله] یک s,t برش کمینه در G باشد، که W یک مولفه از T-st است. در این مقاله نشان می دهیم که هر زوج را سیاز V در T لزوماً مجاور نیستند و شرایط کافی برای اینکه یک جفت راس، مجاور نباشند ارائه می دهیم.

کلیدواژه ها:

درخت گوموری - هو ، برش کمینه ، راس برشی