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

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

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

تعریف: متصل گراف G د‏‏ی کنارہ متصلیت کنارےآں د‏‏ی کم تو‏ں کم تعداد  نو‏‏ں کہندے نيں جِن دے ہٹانے تو‏ں گراف نامتصل ہوئے جائے۔ جے

تو گراف نو‏‏ں n-کنارہ متصل کدرے گے۔

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

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

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

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

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

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

تو گراف نو‏‏ں n-قمہ متصل کدرے گے۔

تعریف:مکمل گراف  د‏‏ی متصلیت  ہُندی ا‏‏ے۔ جب

تو گراف  نو‏‏ں n-متصل کہندے ني‏‏‏‏ں۔

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

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

 مسلئہ اثباندی 
جے گرافG دے راس وچ گھٹ تو‏ں گھٹ درجہ  ہوئے تاں

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

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

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

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

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

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

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

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

 باہرلے جوڑ 

گٹھ:ریاضی