Graph labeling
گراف تھیوری کے ریاضیاتی شعبے میں، گراف لیبلنگ لیبلز کی تفویض ہے، جسے روایتی طور پر انٹیجرز کے ذریعے دکھایا جاتا ہے، کسی گراف کے کناروں اور/یا عمودی حصوں پر۔ رسمی طور پر، گراف کو دیکھتے ہوئے، ورٹیکس لیبلنگ لیبلز کے ایک سیٹ کا فنکشن ہے۔ اس طرح کے فنکشن کے ساتھ گراف کی وضاحت کو ورٹیکس لیبلڈ گراف کہا جاتا ہے۔ اسی طرح، ایج لیبلنگ لیبلز کے ایک سیٹ کا فنکشن ہے۔ اس صورت میں، گراف کو ایج لیبلڈ گراف کہا جاتا ہے۔ جب کنارے کے لیبل ایک ترتیب شدہ سیٹ کے ممبر ہوتے ہیں (مثال کے طور پر، حقیقی نمبر)، تو اسے ویٹڈ گراف کہا جا سکتا ہے۔ جب اہلیت کے بغیر استعمال کیا جاتا ہے، تو لیبل شدہ گراف کی اصطلاح عام طور پر تمام لیبلز کے ساتھ ایک ورٹیکس لیبل والے گراف کی طرف اشارہ کرتی ہے۔ اس طرح کے گراف کو مساوی طور پر مسلسل انٹیجرز کے ذریعے لیبل کیا جا سکتا ہے، جہاں گراف میں عمودی حصوں کی تعداد ہے۔ بہت سی ایپلی کیشنز کے لیے، کناروں یا عمودی حصوں کو ایسے لیبل دیے جاتے ہیں جو متعلقہ ڈومین میں معنی خیز ہوتے ہیں۔ مثال کے طور پر، کناروں کو وزن تفویض کیا جا سکتا ہے جو واقعے کے عمودی حصوں کے درمیان گزرنے کی "لاگت" کی نمائندگی کرتا ہے۔ مندرجہ بالا تعریف میں گراف کو ایک محدود غیر ہدایت شدہ سادہ گراف سمجھا جاتا ہے۔ تاہم، لیبلنگ کا تصور گراف کی تمام توسیعات اور عمومی کاریوں پر لاگو کیا جا سکتا ہے۔ مثال کے طور پر، آٹومیٹا تھیوری اور رسمی زبان کے نظریہ میں لیبل والے ملٹی گراف پر غور کرنا آسان ہے، یعنی عمودی حصوں کا ایک جوڑا کئی لیبل والے کناروں سے جڑا ہو سکتا ہے۔ زیادہ تر گراف لیبلنگ کی ابتدا الیگزینڈر روزا کے 1967 کے مقالے میں پیش کردہ لیبلنگ سے ہوتی ہے۔ روزا نے تین قسم کے لیبلنگ کی نشاندہی کی، جسے انہوں نے -، -، اور-لیبلنگ کہا۔ - لیبلنگ کا نام بعد میں سولومن گولمب نے "خوبصورت" رکھ دیا، اور یہ نام تب سے مقبول ہے۔ خاص صورتوں میں گریس فل لیبلنگ ایک گراف کو گریس فل کہا جاتا ہے جب اس کے عمودی حصوں کو 0 سے گراف کے سائز تک لیبل کیا جاتا ہے، اور یہ لیبلنگ 1 سے ایج لیبلنگ کو جنم دیتی ہے۔ کسی بھی کنارے کے لیے، کا لیبل دو عمودی واقعات کے درمیان مثبت فرق ہے۔ دوسرے لفظوں میں، اگر لیبل والے عمودی حصوں کے ساتھ واقع ہے اور، لیبل کیا جائے گا۔ اس طرح، ایک گراف خوبصورت ہوتا ہے اگر اور صرف اس صورت میں جب کوئی انجکشن موجود ہو جو مثبت انٹیجرز سے لے کر مثبت انٹیجرز تک بائیجیکشن کو جنم دیتا ہے۔ اپنے اصل مقالے میں، روزا نے ثابت کیا کہ 1 یا 2 (موڈ 4) کے مساوی سائز والے تمام یولیرین گراف خوبصورت نہیں ہیں۔ گراف کے کچھ خاندان خوبصورت ہیں یا نہیں، یہ وسیع مطالعہ کے تحت گراف تھیوری کا ایک شعبہ ہے۔ بلا شبہ، گراف لیبلنگ میں سب سے بڑا غیر مصدقہ قیاس رنگل-کوٹزگ قیاس ہے، جو قیاس کرتا ہے کہ تمام درخت خوبصورت ہیں۔ یہ تمام راستوں، کیٹرپلرز، اور درختوں کے بہت سے دوسرے لامحدود خاندانوں کے لیے ثابت ہوا ہے۔ انٹون کوٹزگ نے خود اس قیاس کو ثابت کرنے کی کوشش کو "بیماری" قرار دیا ہے۔ کناروں اور کناروں پر کناروں یا متعدد کناروں کے بغیر ایک سادہ گراف پر کناروں اور کناروں اور کناروں پر ایک کناروں پر ایک عمدہ لیبلنگ کناروں کی الگ الگ انٹیجرز کے ذریعہ اس طرح کی لیبلنگ ہے کہ کناروں پر لیبلنگ ایک ورٹیکس کو لیبلنگ کے ذریعے متاثر ہوتی ہے۔ ماڈیولو میں لیے گئے واقعے کے کناروں کے مجموعے کے ساتھ 0 سے لے کر عمودی تک تمام اقدار تفویض کرتا ہے۔ ایک گراف کو "ایج-گریس فل" کہا جاتا ہے اگر یہ ایج-گریس فل لیبلنگ کو تسلیم کرتا ہے۔ ایج-گریس فل لیبلنگ سب سے پہلے 1985 میں شینگ-پنگ لو نے متعارف کروائی تھی۔ گراف کے کنج گریس فل ہونے کے لیے ایک ضروری شرط "لو کی حالت" ہے: ہم آہنگ لیبلنگ ایک گراف پر "ہم آہنگ لیبلنگ" انٹیجرز ماڈیولو کے گروپ کے عمودی حصوں سے ایک انجکشن ہے، جہاں کناروں کی تعداد ہے، جو کناروں اور نمبروں کے ماڈیولو کے درمیان ایک بیجکشن کو جنم دیتا ہے۔ "ہم آہنگ گراف" وہ ہوتا ہے جس میں ہم آہنگ لیبلنگ ہوتی ہے۔ عجیب سائیکل ہم آہنگ ہوتے ہیں، جیسا کہ پیٹرسن گراف ہیں۔ یہ قیاس کیا جاتا ہے کہ اگر ایک ورٹیکس لیبل کو دوبارہ استعمال کرنے کی اجازت دی جائے تو تمام درخت ہم آہنگ ہوتے ہیں۔ سات صفحات پر مشتمل کتاب کا گراف ایک ایسے گراف کی مثال فراہم کرتا ہے جو ہم آہنگ نہیں ہے۔ گراف کلرنگ گراف لیبلنگ کا ایک ذیلی زمرہ ہے۔ ورٹیکس رنگ ملحقہ عمودی حصوں کو مختلف لیبل تفویض کرتے ہیں، جبکہ کنارے کے رنگ ملحقہ کناروں کو مختلف لیبل تفویض کرتے ہیں۔ لکی لیبلنگ گراف کی لکی لیبلنگ اس طرح کے عمودی حصوں پر مثبت انٹیجرز کی ایک تفویض ہے کہ اگر پڑوسیوں پر موجود لیبلز کے مجموعے کو ظاہر کرتا ہے، تو اس کا ورٹیکس رنگ ہے۔ کا "خوش قسمت نمبر" سب سے کم ایسا ہوتا ہے جس میں انٹیجرز حوالہ جات کی توسیع اور گراف کی عمومی کاری کے ساتھ خوش قسمت لیبلنگ ہوتی ہے۔