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

آزاد انسائیکلوپیڈیا، وکیپیڈیا توں
اصطلاح 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 پڑھو     ریاضی علامات