数学的实践与认识
數學的實踐與認識
수학적실천여인식
MATHEMATICS IN PRACTICE AND THEORY
2010年
3期
151-154
,共4页
二分图%匹配%交错路
二分圖%匹配%交錯路
이분도%필배%교착로
设G是一个具有二分类(X1,X2)的简单偶图,|X1|=|X2|=n,如果对于给定的C>0,|N(S)|≥(1+c)|S|对任意满足|S|≤n/2的S()Xi(i=1,2)都成立,其中N(S)是S的邻集,则称G是(n,c)-扩张图.给出了(n,c)-扩张图的k-匹配数与完美匹配数之比的顺从界.
設G是一箇具有二分類(X1,X2)的簡單偶圖,|X1|=|X2|=n,如果對于給定的C>0,|N(S)|≥(1+c)|S|對任意滿足|S|≤n/2的S()Xi(i=1,2)都成立,其中N(S)是S的鄰集,則稱G是(n,c)-擴張圖.給齣瞭(n,c)-擴張圖的k-匹配數與完美匹配數之比的順從界.
설G시일개구유이분류(X1,X2)적간단우도,|X1|=|X2|=n,여과대우급정적C>0,|N(S)|≥(1+c)|S|대임의만족|S|≤n/2적S()Xi(i=1,2)도성립,기중N(S)시S적린집,칙칭G시(n,c)-확장도.급출료(n,c)-확장도적k-필배수여완미필배수지비적순종계.
