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

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

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

فائل:Connectivity graph theory.svg

کنارہ متصلیت

تصویر میں اگر کنارے 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 پڑھیٔے     ریاضی علامات