Bipartite dimension
گراف تھیوری اور مشترکہ اصلاح کے ریاضیاتی شعبوں میں، گراف G = (V، E) کا دو طرفہ طول و عرض یا دو طرفہ کور نمبر دو طرفہ اشکال کی کم از کم تعداد ہے (جو کہ مکمل دو طرفہ ذیلی اشکال ہے)، جو E میں تمام کناروں کو ڈھانپنے کے لیے درکار ہوتی ہے۔ G میں تمام کناروں کو ڈھانپنے والے دو طرفہ اشکال کے مجموعے کو دو طرفہ اشکال کا احاطہ، یا بعض اوقات دو طرفہ اشکال کہا جاتا ہے۔ G کے دو طرفہ طول و عرض کو اکثر علامت d (G) سے ظاہر کیا جاتا ہے۔ مثال بکلک ایج کور کی ایک مثال درج ذیل خاکے میں دی گئی ہے: کچھ گرافوں کے لیے بپارٹائٹ طول و عرض کے فارمولے n-vertex مکمل گراف کا بپارٹائٹ طول و عرض ہے۔ 2n-vertex تاج گراف کا دو طرفہ طول و عرض برابر ہوتا ہے، جہاں مرکزی بائنومیل گتانک کا الٹا فعل ہوتا ہے۔ جالی گراف کا دو طرفہ طول و عرض ہے، اگر برابر ہے اور کچھ انٹیجرز کے لیے ؛ اور دوسری صورت میں ہے۔ کچھ خاص گرافوں کے لیے دو طرفہ طول و عرض کا تعین کریں۔ مثال کے طور پر، راستہ ہے اور سائیکل ہے۔ دو طرفہ جہت کا حساب لگانا کسی دیئے گئے گراف G کے لیے دو طرفہ جہت کا تعین کرنے کا کمپیوٹیشنل کام ایک اصلاح کا مسئلہ ہے۔ دو طرفہ جہت کے لیے فیصلہ کا مسئلہ اس طرح بیان کیا جا سکتا ہے: فوری: ایک گراف اور ایک مثبت عدد۔ سوال: کیا جی زیادہ تر بائیکلکس پر مشتمل بائیکلک ایج کور کو تسلیم کرتا ہے؟ یہ مسئلہ گیری اور جانسن کی این پی مکمل ہونے پر کلاسیکی کتاب میں مسئلہ جی ٹی 18 کے طور پر ظاہر ہوتا ہے، اور یہ محدود سیٹوں کے خاندانوں پر ایک اور فیصلہ سازی کے مسئلے کی سیدھی سیدھی اصلاح ہے۔ گیری اینڈ جانسن کی کتاب میں سیٹ بیس کا مسئلہ ایس پی 7 کے طور پر ظاہر ہوتا ہے۔ یہاں، ایک محدود سیٹ کے ذیلی سیٹوں کے خاندان کے لیے، ایک سیٹ بیس ان کے ذیلی سیٹوں کا ایک اور خاندان ہے، جیسے کہ ہر سیٹ کو کچھ بنیادی عناصر کے اتحاد کے طور پر بیان کیا جا سکتا ہے۔ سیٹ بیس کا مسئلہ اب اس طرح دیا گیا ہے: فوری: ایک محدود سیٹ، کے ذیلی سیٹوں کا ایک خاندان، اور ایک مثبت عدد k۔ سوال: کیا زیادہ سے زیادہ سائز کی کوئی سیٹ بیس موجود ہے؟ اس کی سابقہ تشکیل میں، مسئلہ این پی مکمل ثابت ہوا، یہاں تک کہ دو طرفہ گراف کے لیے بھی۔ ایک مقررہ بنیاد کے مسئلے کے طور پر تشکیل پہلے این پی مکمل ثابت ہوئی تھی۔ مسئلہ NP-سخت رہتا ہے یہاں تک کہ اگر ہم اپنی توجہ دو طرفہ گرافوں تک محدود رکھتے ہیں جن کی دو طرفہ جہت زیادہ سے زیادہ ہونے کی ضمانت ہے، جس میں n دیئے گئے مسئلے کی مثال کے سائز کو ظاہر کرتا ہے۔ مثبت پہلو پر، مسئلہ دو طرفہ ڈومینو فری گراف پر کثیر الجہتی وقت میں حل کرنے کے قابل ہے۔ تخمینہ الگورتھم کے وجود کے حوالے سے، یہ ثابت ہوا کہ مسئلہ کا اچھی طرح سے تخمینہ نہیں لگایا جا سکتا (فرض کرتے ہوئے کہ P § NP)۔ درحقیقت، پہلے سے ہی دو طرفہ گراف کے لیے، دو طرفہ طول و عرض ہر مقررہ کے لیے این پی-مشکل سے لگ بھگ ہے۔ اس کے برعکس، یہ ثابت کرنا کہ مسئلہ فکسڈ پیرامیٹر ٹریک ایبل ہے، کرنلائزیشن الگورتھم کو ڈیزائن کرنے کی ایک مشق ہے، جو نصابی کتاب میں اس طرح ظاہر ہوتا ہے۔ نتیجے میں آنے والے دانے کے سائز پر ایک کنکریٹ باؤنڈ بھی فراہم کرتا ہے، جسے اس دوران بہتر بنایا گیا ہے۔ در حقیقت، n عمودی پر دیئے گئے دو طرفہ گراف کے لیے، وقت کے ساتھ یہ فیصلہ کیا جا سکتا ہے کہ آیا اس کا دو طرفہ طول و عرض زیادہ سے زیادہ k ایپلی کیشنز ہے۔ گراف کے دو طرفہ طول و عرض کا تعین کرنے کا مسئلہ کمپیوٹنگ کے مختلف سیاق و سباق میں ظاہر ہوتا ہے۔ مثال کے طور پر، کمپیوٹر سسٹمز میں، سسٹم کے مختلف صارفین کو مختلف وسائل تک رسائی کی اجازت یا اجازت نہیں دی جا سکتی ہے۔ کردار پر مبنی رسائی کنٹرول سسٹم میں، ایک کردار وسائل کے ایک سیٹ تک رسائی کے حقوق فراہم کرتا ہے۔ ایک صارف متعدد کرداروں کا مالک ہو سکتا ہے، اور اسے اپنے کچھ کرداروں کے ذریعہ فراہم کردہ تمام وسائل تک رسائی حاصل کرنے کی اجازت ہے۔ اس کے علاوہ، ایک کردار متعدد صارفین کے پاس ہو سکتا ہے۔ رول مائننگ کا مسئلہ کرداروں کا کم سے کم مجموعہ تلاش کرنا ہے، جیسے کہ ہر صارف کے لیے، اس کے کرداروں کو مل کر تمام مخصوص وسائل تک رسائی فراہم کی جائے۔ سسٹم میں وسائل کے سیٹ کے ساتھ مل کر صارفین کا سیٹ قدرتی طور پر ایک دو طرفہ گراف کو جنم دیتا ہے، جس کے کنارے اجازت ہوتے ہیں۔ اس گراف میں ہر بائیکلک ایک ممکنہ کردار ہے، اور کردار کان کنی کے مسئلے کا زیادہ سے زیادہ حل بالکل کم از کم بائیکلک ایج کور ہیں۔ اسی طرح کا منظر نامہ کمپیوٹر سیکیورٹی میں جانا جاتا ہے، خاص طور پر محفوظ نشریات میں۔ اس سیٹ اپ میں، ایک غیر محفوظ چینل پر، وصول کنندگان کے ایک سیٹ کو کئی پیغامات بھیجنے کی ضرورت ہوتی ہے۔ ہر پیغام کو کچھ کرپٹوگرافک کلید کا استعمال کرتے ہوئے خفیہ کرنا پڑتا ہے جو صرف مطلوبہ وصول کنندگان کو معلوم ہوتا ہے۔ ہر وصول کنندہ کے پاس متعدد خفیہ کاری کی چابیاں ہوسکتی ہیں، اور ہر کلید کو متعدد وصول کنندگان میں تقسیم کیا جائے گا۔ سب سے زیادہ کلیدی نسل کا مسئلہ محفوظ ترسیل کو یقینی بنانے کے لیے خفیہ کاری کیز کا کم از کم سیٹ تلاش کرنا ہے۔ جیسا کہ اوپر بتایا گیا ہے، مسئلہ کو دو طرفہ گراف کا استعمال کرتے ہوئے ماڈل کیا جا سکتا ہے جس کے کم از کم بائیکلک ایج کورز زیادہ سے زیادہ کلیدی نسل کے مسئلے کے حل کے ساتھ موافق ہوتے ہیں۔ ایک مختلف اطلاق حیاتیات میں ہے، جہاں کم از کم بائیکلک ایج کور انسانی لیوکوسائٹ اینٹیجن (ایچ ایل اے) سیرولوجی کے ریاضیاتی ماڈلز میں استعمال ہوتے ہیں۔ این پی مکمل مسائل کی فہرست بھی دیکھیں انٹرسیکشن نمبر (گراف تھیوری)، گراف حوالہ جات کے کناروں کا احاطہ کرنے کے لیے درکار کلکس کی کم از کم تعداد۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ بیرونی لنکس دو طرفہ طول و عرض کے بارے میں بلاگ اندراج بذریعہ ڈیوڈ ایپسٹین این پی-مکمل مسائل گراف غیر متغیر دو طرفہ گراف مسائل کا احاطہ کرتے ہیں