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

وکیپیڈیا توں
Jump to navigation Jump to search
اصطلاح term

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

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

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

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

تصویر وچ جے کنارے 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 بے جوڑقمہ رستاں تو‏ں جڑی ہون۔

ہور ویکھو[لکھو]

باہرلے جوڑ[لکھو]

سانچہ:ریاضی مدد