متصلیت (نظریہ مخطط)

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
اصطلاح 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) \ge 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) \ge n

تو مخطط کو n-قمہ متصل کہیں گے۔

تعریف:مکمل مخطط K_m کی متصلیت m-1 ہوتی ہے۔ جب m-1 \ge n تو مخطط K_m کو n-متصل کہتے ہیں۔

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

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

واضح رہے کہ مخطط کی "قمہ متصلیت" \ \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 کے درمیان تمام رستے تباہ ہو جائیں۔

منجر مسلہ اثباتی (کنارہ)[ترمیم]

متصل مخطط کے دو اقمات 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 پڑھیٔے     ریاضی علامات