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

اصطلاح	term
گراف راس کنارہ کنارہ متصلیت قطع مجموعہ قمہ متصلیت بےجوڑ کنارہ بےجوڑ قمہ علاحدہ	graph vertex, vertices edge edge-connectivity cutset vertex-connectivity edge-disjoint vertex disjoint separate

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

کنارہ متصلیت

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

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

$\ \lambda (G)\geq n$

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

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

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

تعریف: قطع‌مجموعہ متصل گراف دے کنارےآں دا ایسا مجموعہ اے جس دے درجہ ذیل خوائص ہاں:

1. مجموعہ دے تمام کنارےآں نو‏‏ں ہٹانے تو‏ں گراف نامتصل ہوئے جائے
2. مجموعہ دے کچھ کنارےآں (مگر تمام نئيں) نو‏‏ں ہٹانے تو‏ں گراف نامتصل نہ ہوئے۔

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

قِمہ متصلیت

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

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

$\ \kappa (G)\geq n$

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

تعریف:مکمل گراف $K_{m}$ د‏‏ی متصلیت $m-1$ ہُندی ا‏‏ے۔ جب $m-1\geq n$ تو گراف $K_{m}$ نو‏‏ں n-متصل کہندے ني‏‏‏‏ں۔

تعریف: قطع‌مجموعہ متصل گراف دے راس دا ایسا مجموعہ اے جس دے درجہ ذیل خوائص ہاں:

1. مجموعہ دے تمام راسنو‏ں ہٹانے تو‏ں گراف نامتصل ہوئے جائے
2. مجموعہ دے کچھ راس (مگر تمام نئيں) نو‏‏ں ہٹانے تو‏ں گراف نامتصل نہ ہوئے۔

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

مسلئہ اثباندی

جے گرافG دے راس وچ گھٹ تو‏ں گھٹ درجہ $\ d(G)$ ہوئے تاں

$\ \kappa (G)\leq \lambda (G)\leq d(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 بے جوڑقمہ رستاں تو‏ں جڑی ہون۔

ہور ویکھو

• سانچہ:وصل

باہرلے جوڑ

E=mc2     پنجابی ویکیپیڈیا اُتے ریاضی مساوات نو‏‏ں کھبے تو‏ں سجے LTR پڑھو     ریاضی علامات