Flag algebra
فلیگ الجیبرا گراف تھیوری کے میدان میں ایک اہم کمپیوٹیشنل ٹول ہے جس میں ہومومورفزم ڈینسٹی اور متعلقہ موضوعات میں وسیع پیمانے پر استعمال ہوتے ہیں۔ تقریبا، وہ ہومومورفزم کی کثافت کو شامل کرنے اور ضرب دینے کے تصور کو باقاعدہ بناتے ہیں اور کمپیوٹر کے ساتھ گراف ہومومورفزم کی عدم مساوات کو سیمیڈفائنٹ پروگرامنگ کے مسائل تک کم کرکے حل کرنے کے لیے ایک فریم ورک قائم کرتے ہیں۔ اصل میں الیگزینڈر رازبوروف نے 2007 کے ایک مقالے میں متعارف کرایا تھا، اس کے بعد سے یہ طریقہ متعدد مشکل، پہلے حل نہ ہونے والے گراف نظریاتی سوالات کو حل کرنے کے لیے آیا ہے۔ ان میں قابل عمل کنارے کی کثافت کے علاقے، مثلث کثافت کے جوڑوں اور مثلث فری گراف میں پینٹاگون کی زیادہ سے زیادہ تعداد کے بارے میں سوال شامل ہیں۔ تحریک فلیگ الجیبراس کے نظریہ کی تحریک کا سہرا جان ایڈرین بونڈی اور کیسٹیٹا-ہیگکوسٹ قیاس آرائی پر ان کے کام کو جاتا ہے، جہاں انہوں نے اپنے اہم خیالات کو گراف ہومومورفزم کے ذریعے بیان کیا جو مینٹل کے نظریہ کے ذائقہ دار ثبوت ہیں۔ یہ ثبوت دوہری گنتی کے ذریعے مینٹل کے روایتی ثبوت پر ایک موافقت ہے، سوائے گراف ہومومورفزم کثافت کے لحاظ سے وضع کردہ اور یہ ظاہر کرتا ہے کہ صرف کثافت کے تعلقات کے ساتھ کتنی معلومات کو انکوڈ کیا جا سکتا ہے۔ نظریہ (مینٹل): مثلث سے پاک گراف میں کنارے کی کثافت زیادہ سے زیادہ ہوتی ہے۔ دوسرے لفظوں میں، چونکہ گراف مثلث سے پاک ہے، 3 عمودی حصوں کے درمیان، وہ یا تو ایک آزاد سیٹ، ایک واحد محرک کنارے، یا لمبائی 2 کا راستہ تشکیل دے سکتے ہیں۔ میں ذیلی گراف کی محرک کثافت کے طور پر اشارہ کرتے ہوئے، دوہری گنتی سے پتہ چلتا ہے: بدیہی طور پر، چونکہ a صرف دو s پر مشتمل ہوتا ہے جو ایک ساتھ جڑے ہوتے ہیں، اور 3 پوائنٹس کے سیٹ کے درمیان مشترکہ ورٹیکس کو لیبل کرنے کے 3 طریقے ہیں۔ در حقیقت، یہ محرک s کی تعداد کو دوگنا گن کر سختی سے ثابت کیا جا سکتا ہے۔ لیٹنگ سے عمودی کی تعداد کی نشاندہی ہوتی ہے، ہمارے پاس: لمبائی 2 کا راستہ کہاں ہے جس کے درمیانی سرے پر لیبل لگا ہوا ہے، اور اس رکاوٹ کے تابع s کی کثافت کی نمائندگی کرتا ہے کہ لیبل شدہ سرے کا استعمال کیا جاتا ہے، اور اسے مناسب محرک ذیلی گراف کے طور پر تب شمار کیا جاتا ہے جب اس کا لیبل والا سرے کے ساتھ موافق ہو۔ اب، نوٹ کریں کہ چونکہ دو s کو منتخب کرنے کا امکان چھوٹا ہے جہاں غیر لیبل شدہ عمودی مماثلت رکھتے ہیں (سخت ہونے کے لیے، ایک حد جیسا کہ لیا جانا چاہیے، اس لیے بڑے اور بڑے گرافوں کی ترتیب پر ایک حد فنکشن کے طور پر کام کرتا ہے۔ یہ خیال فلیگ الجیبراز کی اصل تعریف کے لیے اہم ہوگا۔) ختم کرنے کے لیے، کاچی-شوارز عدم مساوات کو لاگو کریں تاکہ اسے ہمارے اصل رشتے میں واپس لایا جا سکے جو بدیہی طور پر قیاس کیا گیا تھا۔ آخر میں، نوٹ کریں کہ اس ثبوت کے اہم خیالات جو کہ فلیگ الجیبرا کے نظریہ میں عام کیے جائیں گے، وہ متبادل ہیں جیسے کہ لیبل شدہ گراف کی کثافت کا استعمال، کثافت کے صرف "لمٹ کیس" پر غور کرنا، اور معنی خیز نتیجہ حاصل کرنے کے لیے آخر میں کاچی کا اطلاق کرنا۔ تعریف ممنوعہ ذیلی گرافوں کا مجموعہ طے کریں اور آزاد گرافوں کے گرافوں کے سیٹ پر غور کریں۔ اب، سائز کی ایک قسم کو لیبل شدہ عمودی کے ساتھ گراف کے طور پر بیان کریں۔ سائز 0 کی قسم کو عام طور پر اس طرح ظاہر کیا جاتا ہے۔ سب سے پہلے، ہم ایک-پرچم، ایک جزوی طور پر لیبل شدہ گراف کی وضاحت کرتے ہیں جو فلیگ الجیبرا کے نظریہ کے لیے اہم ہوگا: تعریف: ایک-پرچم ایک جوڑا ہے جہاں ایک بنیادی، غیر لیبل شدہ، آزاد گراف ہے، جبکہ عمودی طور پر سرایت شدہ لیبل شدہ گراف کی وضاحت کرتا ہے۔ جھنڈوں کے سیٹ کو ظاہر کریں اور سائز کے جھنڈوں کے سیٹ کو ظاہر کریں۔ مثال کے طور پر، مینٹل کے نظریہ کے ثبوت سے اوپر ایک-پرچم ہے جہاں سائز 1 کی ایک قسم ہے جو ایک واحد سرے سے مطابقت رکھتی ہے۔ جھنڈوں کو مطمئن کرنے کے لیے، ہم بنیادی گراف پر جھنڈوں کی کثافت کو درج ذیل طریقے سے بیان کر سکتے ہیں: تعریف: جھنڈوں کی کثافت کو تصادفی طور پر کامیابی سے اس طرح سرایت کرنے کے امکان کے طور پر بیان کیا گیا ہے کہ وہ غیر باہم مربوط ہوں اور سب پر بالکل اسی طرح لیبل لگا ہوا ہو جیسا کہ آن ہے۔ مزید واضح طور پر، بے ترتیب طور پر جوڑی کے لحاظ سے اختلاط کا انتخاب کریں اور اس امکان کی وضاحت کریں کہ-پرچم سب کے لیے آئسومورفک ہے۔ نوٹ کریں کہ،-پرچم کہاں ہیں، میں سرایت کرتے وقت، یہ پہلے سائز کے-پرچم میں سرایت کرکے اور پھر اس میں سرایت کرکے کیا جا سکتا ہے، جس سے فارمولا ملتا ہے: اسے جھنڈوں کے سیٹوں تک توسیع دینے سے سلسلہ قاعدہ ملتا ہے: نظریہ (سلسلہ قاعدہ): اگر جھنڈے ہیں، تو وہ قدرتی ہیں جو فٹ ہوتے ہیں، سائز کے جھنڈے میں فٹ ہوتے ہیں، اور سائز کا جھنڈا فٹ ہونے کے ساتھ مل جاتا ہے۔ یاد رکھیں کہ مینٹل کے پچھلے ثبوت میں فارم کی اصطلاحات کے لکیری امتزاج شامل تھے۔ متعلقہ خیالات لامحدود کی طرف مائل ہونے کے ساتھ قدرے غیر واضح تھے، لیکن واضح طور پر ایک ایسی ترتیب ہے جو سب کے لیے کچھ میں ضم ہو جاتی ہے، جہاں اسے لمٹ فنکشنل کہا جاتا ہے۔ اس طرح، تمام حوالہ جات واقعی حد فنکشنل کا حوالہ دیتے ہیں۔ اب، گراف ہومومورفزم کی عدم مساوات کو مختلف s کے ساتھ لکیری امتزاج کے طور پر لکھا جا سکتا ہے، لیکن انہیں ایک ہی اصطلاح کے طور پر ظاہر کرنا آسان ہوگا۔ یہ-پرچموں کے رسمی لکیری امتزاج کے سیٹ کی وضاحت کرنے کی ترغیب دیتا ہے، اور اب اسے لکیری فنکشن تک بڑھایا جا سکتا ہے۔ تاہم، صرف محدود افعال کی تحقیقات کرتے وقت پوری جگہ کا استعمال فضول ہے، کیونکہ بعض جھنڈوں کی کثافت کے درمیان غیر معمولی تعلقات موجود ہیں۔ خاص طور پر، چین رول سے پتہ چلتا ہے کہ یہ ہمیشہ درست ہوتا ہے۔ دانا کے ان تمام عناصر سے نمٹنے کے بجائے، مندرجہ بالا فارم کے تاثرات کے سیٹ کو (یعنی۔ وہ جو چین رول سے ایک ہی جھنڈے کے ساتھ حاصل کیے گئے ہیں) اور ہمارے حتمی تجزیے میں ان کا حوالہ دیتے ہیں۔ یہ خیالات فلیگ الجبرا کی تعریف تشکیل دینے کے لیے یکجا ہوتے ہیں: تعریف (فلیگ الجیبرا): فلیگ الجبرا کی تعریف-پرچموں کے لکیری امتزاج کی جگہ پر کی جاتی ہے جو دو لکیری آپریٹر سے لیس ہوتے ہیں اور کسی بھی قدرتی جیسے سائز کے-پرچم میں فٹ ہوتے ہیں، آپریٹر کو لکیری طور پر توسیع دیتے ہیں۔ یہ چیک کرنا باقی ہے کہ کسی جوڑے کے لیے کے انتخاب سے کوئی فرق نہیں پڑتا ہے بشرطیکہ یہ کافی بڑا ہو (یہ چین رول کے ساتھ ثابت کیا جا سکتا ہے) نیز اگر ایسا ہے، تو اس کا مطلب یہ ہے کہ آپریٹر حصص کا احترام کرتا ہے اور اس طرح مطلوبہ جگہ پر ایک اچھی طرح سے طے شدہ الجبرا تشکیل دیتا ہے۔ آپریٹر کے لیے اس تعریف کا ایک اہم نتیجہ یہ ہے کہ حد کے افعال پر ضرب کا احترام کیا جاتا ہے۔ خاص طور پر، ایک حد فعال کے لیے، شناخت درست ہے۔ مثال کے طور پر، یہ دکھایا گیا تھا کہ مینٹل کے لیے ہمارے ثبوت میں، اور یہ نتیجہ صرف اس بیان کا ایک نتیجہ ہے۔ زیادہ عام طور پر، حقیقت یہ ہے کہ ضرب کا مطلب یہ ہے کہ تمام حد کے افعال اور کے درمیان الجبرا ہومومورفزم ہیں۔ نیچے کی طرف آپریٹر اوپر کی تعریف-جھنڈوں سے نمٹنے کے لیے ایک فریم ورک فراہم کرتی ہے، جو جزوی طور پر لیبل والے گراف ہوتے ہیں۔ تاہم، زیادہ تر وقت، غیر لیبل شدہ گراف، یا-پرچم، سب سے زیادہ دلچسپی کے حامل ہوتے ہیں۔ سابقہ سے مؤخر الذکر تک پہنچنے کے لیے، نیچے کی طرف آپریٹر کی وضاحت کریں۔ نیچے کی طرف آپریٹر کو انتہائی قدرتی انداز میں بیان کیا گیا ہے: ایک-پرچم دیا گیا ہے، اسے تفویض کردہ لیبلز کو بھول جانے کے نتیجے میں-پرچم ہونے دیں۔ اب،-پرچموں اور غیر لیبل شدہ گرافوں کے درمیان قدرتی نقشہ سازی کی وضاحت کرنے کے لیے، اس بات کا امکان ہونے دیں کہ بے ترتیب طور پر لیے گئے انجیکشن نقشے میں امیج آئسومورفک ہے، اور اس کی وضاحت کی گئی ہے۔ لکیری طور پر توسیع کرنے سے ایک درست لکیری نقشہ ملتا ہے جو غیر لیبل والے جھنڈوں کے امتزاج کو-جھنڈوں کا مجموعہ بھیجتا ہے۔ سب سے اہم نتیجہ اس کی اوسط خصوصیات سے متعلق ہے۔ خاص طور پر، ایک-پرچم اور غیر لیبل شدہ گراف کو ٹھیک کریں، پھر بے ترتیب متغیر کی وضاحت کرتا ہے۔ یہ دکھایا جا سکتا ہے کہ فلیگ الجبرا کے ساتھ آپٹیمائزیشن تمام لکیری فنکشنلز الجبرا ہومومورفزم ہیں۔ مزید برآں، تعریف کے مطابق، کسی بھی پرچم کے لیے چونکہ کثافت کی حد کی نمائندگی کرتا ہے۔ اس طرح، کہیں کہ ہومومورفزم مثبت ہے اگر اور صرف اس صورت میں، اور مثبت ہومومورفزم کا مجموعہ ہونے دیں۔ کوئی یہ دکھا سکتا ہے کہ لمٹ فنکشنلز کا سیٹ بالکل مثبت ہومومورفزمز کا سیٹ ہے، لہذا یہ سیٹ کی مؤخر الذکر تعریف کو سمجھنے کے لیے کافی ہے۔ ایک لکیری امتزاج کے لیے درست گراف ہومومورفزم عدم مساوات حاصل کرنے کے لیے، اسے تمام ممکنہ لکیری افعال پر غیر منفی ہونے کی ضرورت ہے، جس کا مطلب یہ ہوگا کہ یہ تمام گرافوں کے لیے درست ہے۔ اس بات کو ذہن میں رکھتے ہوئے، قسم کے سیمنٹک کون کی وضاحت کریں، ایک ایسا سیٹ جو ایک بار پھر، سب سے زیادہ دلچسپی کا معاملہ ہے، جو غیر لیبل شدہ گراف کے معاملے سے مطابقت رکھتا ہے۔ تاہم، نیچے کی طرف آپریٹر کے پاس نقشہ سازی کی خاصیت ہوتی ہے، اور یہ دکھایا جا سکتا ہے کہ نیچے کی تصویر کا ایک ذیلی سیٹ ہے، جس کا مطلب ہے کہ سیمنٹک شنک کی قسم پر کوئی بھی نتیجہ آسانی سے غیر لیبل شدہ گرافوں میں بھی عام ہو جاتا ہے۔ صرف بے وقوفانہ طور پر عناصر میں ہیرا پھیری کرکے، سیمنٹک شنک کے متعدد عناصر پیدا کیے جا سکتے ہیں۔ مثال کے طور پر، چونکہ کے عناصر-جھنڈوں کے لیے غیر منفی ہیں، اس لیے کے عناصر کا کوئی بھی مخروطی مجموعہ کا عنصر حاصل کرے گا۔ شاید زیادہ غیر معمولی طور پر، عناصر کے مربعوں کا کوئی بھی مخروطی مجموعہ بھی سیمنٹک شنک کا ایک عنصر حاصل کرے گا۔ اگرچہ کسی کو جھنڈوں کے مربع مل سکتے ہیں جو دستی طور پر غیر معمولی نتائج کا مجموعہ ہیں، لیکن اس عمل کو خودکار بنانا اکثر آسان ہوتا ہے۔ خاص طور پر، کثیر الجہتی کے لیے مجموعے کے مربع کی اصلاح میں خیالات کو فلیگ الجبرا میں ڈھالنا ممکن ہے۔ ویکٹر کی ڈگری کو توسیع میں غیر صفر گتانک کے ساتھ سب سے بڑا پرچم قرار دیں، اور اس کی ڈگری کو تمام انتخاب پر ویکٹر کی کم از کم ڈگری ہونے دیں۔ نیز، سب کے لیے خود کو بھیجنے والے کینونکل ایمبیڈنگ کے طور پر بیان کریں۔ یہ تعریفیں مندرجہ ذیل فلیگ-الجبرا اینالاگ کو جنم دیتی ہیں: نظریہ: دیا گیا ہے، پھر کچھ کے لیے تب ہی موجود ہوتا ہے جب اس طرح کا مثبت سیمیڈفائنٹ میٹرکس موجود ہو۔ اس تھیوریم کے ساتھ، گراف ہومومورفزم کے مسائل کو اب سیمی ڈفائنٹ پروگرامنگ میں منتقل کیا جا سکتا ہے جسے کمپیوٹر کے ذریعے حل کیا جا سکتا ہے۔ مثال کے طور پر، مینٹل کے نظریہ کو اس طرح کے سب سے چھوٹے کو تلاش کرنے کے طور پر دوبارہ بیان کیا جا سکتا ہے۔ جیسا کہ ناقص طور پر سمجھا جاتا ہے، اس شکل میں سوال پر پیش رفت کرنا مشکل ہے، لیکن نوٹ کریں کہ-جھنڈوں اور ویکٹروں کے مربعوں کے مخروطی امتزاج میں ہوتے ہیں، لہذا اس کے بجائے نیم حد تک نرمی کریں۔ خاص طور پر، اس رکاوٹ کے تحت کم سے کم کریں کہ-پرچموں کا مخروطی مجموعہ کہاں ہے اور مثبت نیم یقینی ہے۔ اصلاح کے اس نئے مسئلے کو سیمی ڈفائنٹ پروگرامنگ کے مسئلے میں تبدیل کیا جا سکتا ہے جسے پھر معیاری الگورتھم کے ساتھ حل کیا جا سکتا ہے۔ عامیاں فلیگ الجیبرا کا طریقہ آسانی سے متعدد گراف جیسی تعمیرات کو عام کر دیتا ہے۔ جیسا کہ رازبوروف نے اپنے اصل مقالے میں لکھا ہے، جھنڈوں کو اس کے بجائے محدود ماڈل تھیوری کے ساتھ بیان کیا جا سکتا ہے۔ گراف کے بجائے، صرف پیش گوئی کی علامتوں کے ساتھ ایک محدود رشتہ دار دستخط میں مساوات کے ساتھ کچھ غیر تخلیق شدہ یونیورسل فرسٹ آرڈر تھیوری کے ماڈل استعمال کیے جا سکتے ہیں۔ ایک ماڈل، جو گراف کے ہمارے پچھلے تصور کی جگہ لے لیتا ہے، اس میں گراؤنڈ سیٹ ہوتا ہے، جس کے عناصر کو عمودی کہا جاتا ہے۔ اب، ذیلی ماڈلز اور ماڈل کے سرایت کو ذیلی گراف اور گراف کے سرایت کے مترادف انداز میں بیان کرتے ہوئے، مذکورہ بالا تمام تعریفیں اور نظریات کا تقریبا براہ راست ماڈل تھیوری کی زبان میں ترجمہ کیا جا سکتا ہے۔ حقیقت یہ ہے کہ فلیگ الجیبراز کا نظریہ اچھی طرح سے عام ہوتا ہے اس کا مطلب یہ ہے کہ اسے نہ صرف سادہ گرافوں میں مسائل کو حل کرنے کے لیے استعمال کیا جا سکتا ہے، بلکہ اسی طرح کی تعمیرات جیسے کہ ہدایت شدہ گراف اور ہائپر گراف تک محدود نہیں۔ حوالہ جات گراف تھیوری