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

آزاد دائرۃ المعارف، ویکیپیڈیا سے
(متصلیت (نظریہ مخطط) سے رجوع مکرر)
اصطلاح term

گراف
راس
کنارہ
کنارہ متصلیت
قطع مجموعہ
قمہ متصلیت
بے جوڑ کنارہ
بے جوڑ قمہ
علاحدہ

graph
vertex, vertices
edge
edge-connectivity
cutset
vertex-connectivity
edge-disjoint
vertex disjoint
separate

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

کنارہ متصلیت[ترمیم]

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

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

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

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

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

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

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

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

قِمہ متصلیت[ترمیم]

تصویر میں اگر قمہ d اور c کو ہٹا دیا جائے تو گراف نامتصل ہو جائے گا۔ جب قمہ ہٹایا جاتا ہے تو اس پر ورد کنارے بھی ہٹا دیے جاتے ہیں۔

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

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

تعریف:مکمل گراف کی متصلیت ہوتی ہے۔ جب تو گراف کو n-متصل کہتے ہیں۔

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

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

واضح رہے کہ گراف کی "قمہ متصلیت" قطع‌مجموعات میں کم از کم راس کی تعداد کے برابر ہوتی ہے۔

مسلئہ اثباتی[ترمیم]

اگر گراف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 پڑھیٔے     ریاضی علامات