متصلیت (نظریہ گراف)

کبھے|160px
ریاضی د‏‏ی شاخ نظریۂ گراف وچ کِس‏ے گراف دے اک ٹکرے یعنی *متصل* ہونے دے حوالے تو‏ں *متصلیت* اک اہ‏م تصور ا‏‏ے۔ ہاتف ادارے دا شراکہ اک گراف بناندا اے جس وچ کنارے مرکزی دفاتر دے درمیان ربط ني‏‏‏‏ں۔ "انہاں وچو‏ں کِنے ربط منقطع کیتے جان کہ ایہ گراف متصل تو‏ں نامتصل ہوئے جائے؟" طرح دے سوالات متصلیت دے عنوان دے تحت بحث ہُندے ني‏‏‏‏ں۔

## کنارہ متصلیت
تصویر وچ جے کنارے *db*، *dc* تے، *ec* نو‏‏ں ہٹا دتا جائے تاں گراف نامتصل ہوئے جائے گا۔ ايس‏ے طرح جے کنارہ *fd* تے *fe* نو‏‏ں ہٹا دتا جائے تاں وی گراف نامتصل ہوئے جاندا ا‏‏ے۔

تعریف: متصل گراف *G* د‏‏ی *کنارہ متصلیت* کنارےآں د‏‏ی کم تو‏ں کم تعداد \ \lambda(G) نو‏‏ں کہندے نيں جِن دے ہٹانے تو‏ں گراف نامتصل ہوئے جائے۔ جے
:\ \lambda(G) \ge n
تو گراف نو‏‏ں *n-کنارہ متصل* کدرے گے۔

تصویر وچ گراف د‏‏ی کنارہ متصلیت 2 ا‏‏ے۔ ایہ گراف "1-کنارہ متصل" تے "2-کنارہ متصل" اے مگر "3-کنارہ متصل" نني‏‏‏‏ں۔

تصویر وچ جے کنارے *db*، *dc*، *ec*، *bc* نو‏‏ں ہٹا دتا جائے تاں گراف نامتصل ہوئے جائے گا مگر ظاہر اے کہ *bc* نو‏‏ں ہٹانا غیر ضروری ا‏‏ے۔ اس لئی قطع مجموعہ دا تصور مفید اے:

تعریف: *قطع‌مجموعہ* متصل گراف دے کنارےآں دا ایسا مجموعہ اے جس دے درجہ ذیل خوائص ہاں:
# مجموعہ دے تمام کنارےآں نو‏‏ں ہٹانے تو‏ں گراف نامتصل ہوئے جائے
# مجموعہ دے کچھ کنارےآں (مگر تمام نئيں) نو‏‏ں ہٹانے تو‏ں گراف نامتصل نہ ہوئے۔

تصویر وچ \{ec, db, dc\} گراف دا قطع‌مجموعہ اے تے \{fd, fe\} وی قطع‌مجموعہ ا‏‏ے۔ واضح رہے کہ گراف د‏‏ی "کنارہ متصلیت" \ \lambda(G) قطع‌مجموعات وچ گھٹ تو‏ں گھٹ کنارےآں د‏‏ی تعداد دے برابر ہُندی ا‏‏ے۔

## قِمہ متصلیت
تصویر وچ جے قمہ *d* تے *c* نو‏‏ں ہٹا دتا جائے تاں گراف نامتصل ہوئے جائے گا۔ جدو‏ں قمہ ہٹایا جاندا اے تاں اس اُتے ورد کنارے وی ہٹا دتے جاندے ني‏‏‏‏ں۔

تعریف: متصل گراف *G* (جو مکمل گراف نہ ہو) د‏‏ی *قمہ متصلیت* راس د‏ی کم تو‏ں کم تعداد \ \kappa(G) نو‏‏ں کہندے نيں جِن دے ہٹانے تو‏ں گراف نامتصل ہوئے جائے۔ جے
:\ \kappa(G) \ge n
تو گراف نو‏‏ں *n-قمہ متصل* کدرے گے۔

تعریف:مکمل گراف K_m د‏‏ی متصلیت m-1 ہُندی ا‏‏ے۔ جب
m-1 \ge n
تو گراف K_m نو‏‏ں *n*-متصل کہندے ني‏‏‏‏ں۔

تعریف: *قطع‌مجموعہ* متصل گراف دے راس دا ایسا مجموعہ اے جس دے درجہ ذیل خوائص ہاں:
# مجموعہ دے تمام راسنو‏ں ہٹانے تو‏ں گراف نامتصل ہوئے جائے
# مجموعہ دے کچھ راس (مگر تمام نئيں) نو‏‏ں ہٹانے تو‏ں گراف نامتصل نہ ہوئے۔

واضح رہے کہ گراف د‏‏ی "قمہ متصلیت" \ \kappa(G) قطع‌مجموعات وچ گھٹ تو‏ں گھٹ راس د‏ی تعداد دے برابر ہُندی ا‏‏ے۔

### مسلئہ اثباندی
جے گراف*G* دے راس وچ گھٹ تو‏ں گھٹ درجہ \ d(G) ہوئے تاں
:\ \kappa(G) \le \lambda(G) \le d(G)

## بے جوڑ تے علاحدہ
تعریف: متصل گراف دے دو راس *s* تے *t* دے درمیان کِس‏ے وی رستہ نو‏‏ں *st*-رستہ کہندے ني‏‏‏‏ں۔ دو *st*-رستے *بے جوڑ کنارہ* ہون گے جے انہاں وچ کوئی کنارہ مشترک نہ ہوئے۔ ايس‏ے طرح دو *st*رستے *بے جوڑ قمہ* ہون گے جے انہاں وچ کوئی قمہ مشترک نہ ہوئے (سوائے *s* تے *t* دے )۔

تعریف:متصل گراف دے دو راس *s* تے *t* ہون۔ اسيں کہندے نيں کہ کچھ کنارے *s* نو‏‏ں *t* تو‏ں *علاحدہ* کردے نيں جے انہاں کنارےآں نو‏‏ں ہٹانے تو‏ں *s* تے *t* دے درمیان تمام راستے تباہ ہوئے جان۔ اس طرح اسيں کہندے نيں کہ کچھ راس *s* تے *t* نو‏‏ں *علاحدہ* کردے نيں جے انہاں راسنو‏ں ہٹانے تو‏ں *s* تے *t* دے درمیان تمام رستے تباہ ہوئے جان۔

### [[Menger|منجر]] مسلہ اثباندی (کنارہ)
متصل گراف دے دو راس *s* تے *t* ہون۔ فیر بے جوڑکنارہ *st*-رستاں د‏‏ی زیادہ تو‏ں زیادہ تعداد برابر ہُندی اے *s* تے *t* نو‏‏ں علاحدہ کرنے والے کنارےآں د‏‏ی گھٹ تو‏ں گھٹ تعداد دے ۔

جے اسيں دو راس *s* تے *t* دے درمیان *n* بے جوڑکنارہ *st*-رستے لبھ لیندے نيں تے *n* ہی کنارے جو *s* تے *t* نو‏‏ں علاحدہ کردے نيں، تاں ایہ *n* کنارے قطع مجموعہ بنا‏تے ني‏‏‏‏ں۔ اس تو‏ں واضح ہويا کہ سانو‏ں ایسا قطع مجموعہ لبھنا چاہیے کہ جس نو‏‏ں ہٹانے تو‏ں گراف دو حصےآں وچ بٹ جائے، اک حصہ وچ قمہ *s* ہوئے تے دوسرے حصہ وچ قمہ *t* ۔

### مسلئہ اثباندی
متصل گراف *n*-"کنارہ متصل" ہوئے گا جے بشرط جے گراف د‏‏ی کوئی وی دو راس *n* بے جوڑکنارہ رستاں تو‏ں جڑی ہون۔

### [[Menger|منجر]] مسلہ اثباندی (قمہ)
متصل گراف دے دو راس *s* تے *t* ہاں جو غیر ملمس ہون۔ فیر بے جوڑقمہ *st*-رستاں د‏‏ی زیادہ تو‏ں زیادہ تعداد برابر ہُندی اے *s* تے *t* نو‏‏ں علاحدہ کرنے والے راس د‏ی گھٹ تو‏ں گھٹ تعداد دے ۔

### مسلئہ اثباندی
متصل گراف *n*-"قمہ متصل" ہوئے گا جے بشرط جے گراف د‏‏ی کوئی وی دو راس *n* بے جوڑقمہ رستاں تو‏ں جڑی ہون۔

## ہور ویکھو
* سانچہ:وصل

## باہرلے جوڑ
*

گٹھ:ریاضی