Chromatic polynomial
کرومیٹک کثیر الجہتی ایک گراف کثیر الجہتی ہے جس کا مطالعہ الجبرائی گراف تھیوری میں کیا جاتا ہے، جو ریاضی کی ایک شاخ ہے۔ یہ گراف کے رنگوں کی تعداد کو رنگوں کی تعداد کے فنکشن کے طور پر شمار کرتا ہے اور اصل میں جارج ڈیوڈ برخوف نے چار رنگوں کے مسئلے کا مطالعہ کرنے کے لیے اس کی تعریف کی تھی۔ اسے ہاسلر وٹنی اور ڈبلیو ٹی ٹوٹے نے ٹوٹے کثیر الجہتی میں عام کیا تھا، اور اسے شماریاتی طبیعیات کے پوٹس ماڈل سے جوڑا تھا۔ تاریخ جارج ڈیوڈ برخوف نے 1912 میں کرومیٹک کثیر الجہتی متعارف کرایا، جس میں چار رنگوں کے نظریہ کو ثابت کرنے کی کوشش میں اسے صرف پلانر گراف کے لیے بیان کیا گیا۔ اگر G کی k رنگوں کے ساتھ مناسب رنگوں کی تعداد کی نشاندہی کی جائے تو کوئی بھی تمام پلینر گراف G کو دکھا کر چار رنگوں کا نظریہ قائم کر سکتا ہے۔ اس طرح وہ کثیر الجہتی کی جڑوں کا مطالعہ کرنے کے لیے تجزیہ اور الجبرا کے طاقتور ٹولز کو مشترکہ رنگ کے مسئلے پر لاگو کرنے کی امید کرتا ہے۔ ہیسلر وٹنی نے 1932 میں برخوف کے کثیر الجہتی کو پلانر کیس سے لے کر عمومی گراف تک عام کیا۔ 1968 میں، رونالڈ سی ریڈ نے پوچھا کہ کون سے کثیر الجہتی کسی گراف کے کرومیٹک کثیر الجہتی ہیں، ایک ایسا سوال جو کھلا رہتا ہے، اور کرومیٹک طور پر مساوی گراف کے تصور کو متعارف کرایا۔ آج، کرومیٹک کثیر الجہتی الجبرائی گراف تھیوری کے مرکزی مقاصد میں سے ایک ہیں۔ تعریف گراف G کے لیے، اس کے (مناسب) ورٹیکس k-رنگوں کی تعداد شمار کرتا ہے۔ دیگر عام طور پر استعمال ہونے والے اشاروں میں شامل ہیں، یا۔ ایک منفرد کثیر الجہتی ہے جس کا اندازہ کسی بھی عدد k ≤ 0 پر ہوتا ہے۔ اسے G کا کرومیٹک کثیر الجہتی کہا جاتا ہے۔ مثال کے طور پر، راستے کے گراف کو 3 عمودی پر k رنگوں سے رنگنے کے لیے، کوئی بھی پہلے عمودی کے لیے کسی بھی k رنگ کا انتخاب کر سکتا ہے، دوسرے عمودی کے لیے باقی رنگوں میں سے کوئی بھی، اور آخر میں تیسرے عمودی کے لیے، کوئی بھی رنگ جو دوسرے عمودی کے انتخاب سے مختلف ہو۔ لہذا، کے رنگوں کی تعداد ہے۔ متغیر x (لازمی طور پر عدد نہیں) کے لیے، اس طرح ہمارے پاس ہے۔ (وہ رنگ جو صرف رنگوں کو تبدیل کرنے یا G کے آٹومورفزم سے مختلف ہوتے ہیں، اب بھی مختلف شمار کیے جاتے ہیں۔) حذف کرنا-سکڑنا یہ حقیقت کہ k رنگوں کی تعداد k میں ایک کثیر الجہتی ہے، ایک تکرار کے تعلق سے ملتی ہے جسے حذف کرنا-سکڑنا تکرار یا بنیادی تخفیف نظریہ کہا جاتا ہے۔ یہ کنارے کے سکڑنے پر مبنی ہے: عمودی کے ایک جوڑے کے لیے اور گراف دونوں عمودی کو ضم کر کے اور ان کے درمیان کسی بھی کنارے کو ہٹا کر حاصل کیا جاتا ہے۔ اگر اور G میں ملحقہ ہیں، تو کنارے کو ہٹا کر حاصل کردہ گراف کو ظاہر کریں۔ پھر ان گرافوں کے کے رنگوں کی تعداد مطمئن کرتی ہے: مساوی طور پر، اگر اور جی میں ملحقہ نہیں ہیں اور کنارے کے ساتھ گراف شامل کیا گیا ہے، تو یہ اس مشاہدے سے ہوتا ہے کہ جی کا ہر کے رنگ یا تو اور، یا ایک ہی رنگ کو مختلف رنگ دیتا ہے۔ پہلی صورت میں یہ (مناسب) کے-رنگ دیتا ہے، جبکہ دوسری صورت میں یہ کا رنگ دیتا ہے۔ اس کے برعکس، G کا ہر k-رنگ منفرد طور پر k-رنگ سے حاصل کیا جا سکتا ہے یا (اگر اور G میں ملحقہ نہیں ہیں)۔ اس لیے کرومیٹک کثیر الجہتی کو بار بار اس طرح بیان کیا جا سکتا ہے جیسے کہ n عمودی پر کنارے کے بغیر گراف کے لیے، اور ایک کنارے کے ساتھ گراف G کے لیے (من مانی طور پر منتخب کیا گیا)۔ چونکہ کنارے کے بغیر گراف کے k-رنگوں کی تعداد درحقیقت ہے، اس لیے یہ کناروں کی تعداد پر انڈکشن کے بعد آتا ہے کہ تمام G کے لیے، کثیرالجہتی ہر عدد نقطہ x = k پر k-رنگوں کی تعداد کے ساتھ موافق ہوتا ہے۔ خاص طور پر، رنگین کثیرالجہتی ان نکات کے ذریعے زیادہ سے زیادہ n پر ڈگری کا منفرد انٹرپولیٹنگ کثیرالجہتی ہے جس کے بارے میں دوسرے گراف کے غیر متغیرات نے اس طرح کے تکرار کو مطمئن کیا جس کی وجہ سے وہ رنگین کثیرالجہتی، ٹوٹے کثیرالجہتی کی دو متغیر عمومی شکل کو دریافت کرنے پر مجبور ہوا۔ مثال کی خصوصیات n عمودی پر فکسڈ G کے لیے، کرومیٹک کثیر الجہتی بالکل n ڈگری کا ایک مونیک کثیر الجہتی ہے، جس میں انٹیجر کوفیشنٹس ہوتے ہیں۔ کرومیٹک کثیر الجہتی میں کم از کم G کی رنگینیت کے بارے میں اتنی ہی معلومات شامل ہوتی ہیں جتنی کہ کرومیٹک نمبر میں ہوتی ہے۔ درحقیقت، کرومیٹک نمبر سب سے چھوٹا مثبت عدد ہے جو کرومیٹک کثیر الجہتی کا صفر نہیں ہے، جس کثیر الجہتی کا جائزہ لیا جاتا ہے، یعنی، G کی ایسیکلک سمتوں کی تعداد سے گنا زیادہ حاصل ہوتا ہے۔ 1 پر تشخیص شدہ مشتق، علامت تک کرومیٹک غیر متغیر کے برابر ہوتا ہے۔ اگر G میں n عمودی اور c اجزاء ہیں، تو ان کے کوفیشنٹس صفر ہیں۔ کے کوفیشنٹس تمام غیر صفر اور علامتوں میں متبادل ہیں۔ کا گتانک 1 ہے (کثیر الجہتی مونیک ہے)۔ کا گتانک ہے۔ ہم اسے عمودی اور کناروں کے ساتھ ایک سادہ گراف G پر کناروں کی تعداد پر انڈکشن کے ذریعے ثابت کرتے ہیں۔ کب، G ایک خالی گراف ہے۔ اس لیے تعریف کے مطابق۔ تو کا گتانک ہے، جس کا مطلب ہے کہ بیان خالی گراف کے لیے درست ہے۔ جب، جیسا کہ G میں صرف ایک کنارے ہوتا ہے،۔ اس طرح کا گتانک ہے۔ تو بیان k = 1 کے لیے ہے۔ مضبوط انڈکشن کا استعمال کرتے ہوئے فرض کریں کہ بیان درست ہے۔ G کو کنارے ہونے دیں۔ سنکچن-ڈیلیشن اصول کے مطابق، لیٹ، اور۔ لہذا۔ چونکہ G سے صرف ایک کنارے e کو ہٹانے سے حاصل کیا جاتا ہے، لہذا اور اس طرح یہ بیان k کے لیے درست ہے۔ کا گتانک ایک مخصوص، من مانی طور پر منتخب کردہ ورٹیکس پر ایک منفرد سنک والے ایسائکلک سمتوں کی تعداد کا گنا ہے۔ ہر کرومیٹک کثیر الجہتی کے کوفیشنٹس کی مطلق اقدار ایک لاگ کنکیو ترتیب بناتی ہیں۔ آخری خاصیت کو اس حقیقت سے عام کیا جاتا ہے کہ اگر G ایک k-کلک-مجموعہ ہے اور (یعنی، ایک گراف جو k عمودی پر ایک کلیک پر دونوں کو چپکانے سے حاصل ہوتا ہے)، تو n عمودی کے ساتھ A گراف G ایک درخت ہے اگر اور صرف اس صورت میں جب کرومیٹک مساوات دو گرافوں کو کرومیٹک طور پر مساوی کہا جاتا ہے اگر ان میں ایک ہی کرومیٹک کثیر الجہتی ہو۔ آئسومورفک گرافوں میں ایک ہی کرومیٹک کثیر الجہتی ہوتے ہیں، لیکن غیر آئسومورفک گراف کرومیٹک طور پر مساوی ہو سکتے ہیں۔ مثال کے طور پر، n عمودی پر تمام درختوں میں ایک ہی رنگین کثیر الجہتی ہوتا ہے۔ خاص طور پر، پنجے کے گراف اور 4 عمودی راستوں پر راستے کے گراف دونوں کا کرومیٹک کثیر الجہتی ہے۔ گراف کرومیٹک طور پر منفرد ہوتا ہے اگر اس کا تعین اس کے کرومیٹک کثیر الجہتی سے ہوتا ہے، آئسومورفزم تک۔ دوسرے لفظوں میں، G کرومیٹک طور پر منفرد ہے، پھر اس کا مطلب یہ ہوگا کہ G اور H آئسومورفک ہیں۔ تمام سائیکل گراف کرومیٹک طور پر منفرد ہیں۔ کرومیٹک جڑیں کرومیٹک کثیر الجہتی کی جڑ (یا صفر)، جسے "کرومیٹک جڑ" کہا جاتا ہے، ایک قدر x ہے جہاں۔ کرومیٹک جڑوں کا بہت اچھی طرح سے مطالعہ کیا گیا ہے، در حقیقت، کرومیٹک کثیر الجہتی کی وضاحت کے لیے برخوف کا اصل محرک یہ ظاہر کرنا تھا کہ طیارہ گراف کے لیے، x ≤ 4 کے لیے۔ اس سے چار رنگوں کا نظریہ قائم ہوتا۔ کوئی گراف 0 رنگ کا نہیں ہو سکتا، اس لیے 0 ہمیشہ ایک رنگین جڑ ہوتا ہے۔ صرف کنارے کے بغیر گراف 1 رنگ کے ہو سکتے ہیں، اس لیے 1 کم از کم ایک کنارے کے ساتھ ہر گراف کا کرومیٹک جڑ ہے۔ دوسری طرف، ان دو نکات کے علاوہ، کسی بھی گراف میں کسی حقیقی نمبر پر کرومیٹک جڑ نہیں ہو سکتی جو 32/27 سے چھوٹی یا اس کے برابر ہو۔ ٹوٹے کا نتیجہ سنہری تناسب کو رنگین جڑوں کے مطالعہ سے جوڑتا ہے، جس سے یہ ظاہر ہوتا ہے کہ رنگین جڑیں اس کے بہت قریب موجود ہیں: اگر کسی دائرے کا طیارہ مثلث ہے تو جب کہ حقیقی لکیر میں اس طرح کے بڑے حصے ہوتے ہیں جن میں کسی بھی گراف کے لیے رنگین جڑیں نہیں ہوتی ہیں، پیچیدہ سطح کا ہر نقطہ من مانی طور پر رنگین جڑ کے قریب ہوتا ہے اس معنی میں کہ گراف کا ایک لامحدود خاندان موجود ہے جس کی رنگین جڑیں پیچیدہ سطح میں گھنے ہوتی ہیں۔ تمام رنگوں کا استعمال کرتے ہوئے رنگ n چوٹیوں پر گراف G کے لیے، رنگوں کے نام تبدیل کرنے تک بالکل k رنگوں کا استعمال کرتے ہوئے رنگوں کی تعداد کو ظاہر کرتے ہیں (لہذا رنگوں کو جو رنگوں کو ایک دوسرے سے حاصل کیا جا سکتا ہے اسے ایک کے طور پر شمار کیا جاتا ہے ؛ G کے آٹومورفزم کے ذریعے حاصل کردہ رنگ اب بھی الگ سے شمار کیے جاتے ہیں)۔ دوسرے لفظوں میں، k (غیر خالی) آزاد سیٹوں میں سیٹ کردہ ورٹیکس کی پارٹیشنوں کی تعداد کو شمار کرتا ہے۔ پھر بالکل k رنگوں (ممتاز رنگوں کے ساتھ) کا استعمال کرتے ہوئے رنگوں کی تعداد شمار کرتا ہے۔ ایک عدد x کے لیے، G کے تمام x رنگوں کو منفرد طور پر ایک عدد k ≤ x کا انتخاب کرکے، دستیاب x میں سے استعمال ہونے والے k رنگوں کا انتخاب کرکے، اور بالکل ان k (امتیازی) رنگوں کا استعمال کرتے ہوئے رنگ حاصل کیا جا سکتا ہے۔ لہذا:، جہاں گرنے والے فیکٹوریئل کی نشاندہی کرتا ہے۔ اس طرح اعداد گرنے والے فیکٹوریئلز کی بنیاد پر کثیر الجہتی کے گتانک ہوتے ہیں۔ معیاری بنیاد کا k-th گتانک ہونے دیں، یعنی: سٹرلنگ نمبر معیاری بنیاد اور گرنے والے فیکٹوریئلز کی بنیاد کے درمیان بنیاد کی تبدیلی دیتے ہیں۔ اس کا مطلب ہے: اور۔ درجہ بندی کرومیٹک کثیر الجہتی کو ہومیولوجی تھیوری کے ذریعہ درجہ بندی کیا گیا ہے جس کا کھوانوف ہومیولوجی سے گہرا تعلق ہے۔ الگورتھم کرومیٹک کثیر الجہتی سے وابستہ کمپیوٹیشنل مسائل میں دیئے گئے گراف G کے کرومیٹک کثیر الجہتی کو تلاش کرنا شامل ہے۔ دیئے گئے G کے لیے ایک مقررہ x پر اندازہ لگانا۔ پہلا مسئلہ زیادہ عام ہے کیونکہ اگر ہم کے کوفیشنٹس کو جانتے تو ہم کثیر الجہتی وقت میں کسی بھی مقام پر اس کا اندازہ لگا سکتے ہیں کیونکہ ڈگری n ہے۔ دوسری قسم کے مسئلے کی مشکل کا انحصار x کی قدر پر مضبوطی سے ہوتا ہے اور کمپیوٹیشنل پیچیدگی میں اس کا گہرائی سے مطالعہ کیا گیا ہے۔ جب x ایک قدرتی عدد ہے، تو اس مسئلے کو عام طور پر دیئے گئے گراف کے x رنگوں کی تعداد کا حساب لگانے کے طور پر دیکھا جاتا ہے۔ مثال کے طور پر، اس میں 3 رنگوں کی تعداد کی گنتی کا مسئلہ #3-رنگ، گنتی کی پیچیدگی کے مطالعہ میں ایک کینونکل مسئلہ شامل ہے، جو گنتی کلاس #P کے لیے مکمل ہے۔ موثر الگورتھم کچھ بنیادی گراف کلاسوں کے لیے، کرومیٹک کثیرالجہتی کے لیے بند فارمولے معلوم ہیں۔ مثال کے طور پر یہ درختوں اور گروہوں کے لیے درست ہے، جیسا کہ اوپر دیے گئے جدول میں درج ہے۔ کثیر الجہتی وقت کے الگورتھم گراف کی وسیع تر کلاسوں کے لیے کرومیٹک کثیر الجہتی کی کمپیوٹنگ کے لیے جانے جاتے ہیں، بشمول کورڈل گراف اور باؤنڈڈ کلک چوڑائی کے گراف۔ مؤخر الذکر کلاس میں بائنڈڈ ٹری چوڑائی کے گراف اور گراف شامل ہیں، جیسے کہ آؤٹر پلینر گراف۔ حذف کرنا-سکڑنا حذف کرنا-سکڑنا تکرار کرومیٹک کثیر الجہتی کا حساب لگانے کا ایک طریقہ فراہم کرتا ہے، جسے حذف کرنا-سکڑنا الگورتھم کہا جاتا ہے۔ پہلی شکل میں (مائنس کے ساتھ)، تکرار خالی گرافوں کے مجموعے میں ختم ہوتا ہے۔ دوسری شکل میں (پلس کے ساتھ)، یہ مکمل گراف کے مجموعے میں ختم ہوتا ہے۔ یہ گراف کلرنگ کے لیے بہت سے الگورتھم کی بنیاد بناتا ہے۔ کمپیوٹر الجبرا سسٹم میتھمیٹکا کے کمبینٹوریکا پیکیج میں کرومیٹک پولینومیل فنکشن دوسری تکرار کا استعمال کرتا ہے اگر گراف گھنے ہو، اور پہلی تکرار اگر گراف کم ہو۔ کسی بھی فارمولے کا بدترین صورت میں چلنے کا وقت اسی تکرار کے تعلق کو مطمئن کرتا ہے جیسا کہ فبونیکی نمبرز، لہذا بدترین صورت میں، الگورتھم وقت کے ساتھ ساتھ n عمودی اور m کناروں والے گراف کے کثیر عنصر کے اندر چلتا ہے۔ تجزیہ کو ان پٹ گراف کے پھیلے ہوئے درختوں کی تعداد کے کثیر عنصر کے اندر بہتر بنایا جا سکتا ہے۔ عملی طور پر، برانچ اور باؤنڈ حکمت عملی اور گراف آئسومورفزم مسترد کرنے کو کچھ تکراری کالوں سے بچنے کے لیے استعمال کیا جاتا ہے، چلانے کا وقت ورٹیکس جوڑے کو چننے کے لیے استعمال ہونے والے ہیورسٹک پر منحصر ہوتا ہے۔ کیوب کا طریقہ گراف کے رنگوں پر ایک قدرتی ہندسی نقطہ نظر یہ مشاہدہ کرتے ہوئے ہے کہ، ہر سرے پر قدرتی اعداد کی تفویض کے طور پر، گراف کا رنگ انٹیجر لیٹس میں ایک ویکٹر ہے۔ چونکہ دو عمودی اور ایک ہی رنگ دیا جانا رنگین ویکٹر میں 'th اور' th کوآرڈینیٹ کے برابر ہونے کے برابر ہے، اس لیے ہر کنارے کو شکل کے ہائپرپلین سے جوڑا جا سکتا ہے۔ کسی دیئے گئے گراف کے لیے اس طرح کے ہائپرپلین کا مجموعہ اس کی گرافک ترتیب کہلاتا ہے۔ گراف کے مناسب رنگ وہ جالی کے نکات ہوتے ہیں جو ممنوعہ ہائپرپلین سے بچتے ہیں۔ رنگوں کے ایک سیٹ تک محدود، جالی کے نکات مکعب میں موجود ہوتے ہیں۔ اس تناظر میں کرومیٹک کثیر الجہتی-مکعب میں جالی کے نکات کی تعداد کو شمار کرتا ہے جو گرافک ترتیب سے بچتے ہیں۔ کمپیوٹیشنل پیچیدگی کسی دیئے گئے گراف کے 3 رنگوں کی تعداد کو کمپیوٹ کرنے کا مسئلہ #P-مکمل مسئلے کی ایک مستند مثال ہے، لہذا کرومیٹک کثیر الجہتی کے کوفیشنٹس کو کمپیوٹ کرنے کا مسئلہ #P-سخت ہے۔ اسی طرح، دیئے گئے G کا اندازہ لگانا #P-مکمل ہے۔ دوسری طرف، کیونکہ اس کا حساب لگانا آسان ہے، اس لیے متعلقہ مسائل کثیر الجہتی وقت کے قابل ہیں۔ انٹیجرز کے لیے مسئلہ #P-سخت ہے، جو کیس کی طرح قائم کیا گیا ہے۔ درحقیقت، یہ معلوم ہے کہ تین "آسان نکات" کے علاوہ تمام x (بشمول منفی عدد اور یہاں تک کہ تمام پیچیدہ اعداد) کے لیے #P-مشکل ہے۔ اس طرح، #P-سختی کے نقطہ نظر سے، کرومیٹک کثیر الجہتی کی گنتی کی پیچیدگی کو مکمل طور پر سمجھا جاتا ہے۔ توسیع میں گتانک ہمیشہ 1 کے برابر ہوتا ہے، اور گتانک کی کئی دیگر خصوصیات معلوم ہوتی ہیں۔ اس سے یہ سوال پیدا ہوتا ہے کہ کیا کچھ کوفیشنٹس کا حساب لگانا آسان ہے۔ تاہم ایک مقررہ r ≤ 1 اور دیئے گئے گراف G کے لیے ar کی کمپیوٹنگ کا کمپیوٹیشنل مسئلہ #P-سخت ہے، یہاں تک کہ دو طرفہ پلانر گراف کے لیے بھی۔ کمپیوٹنگ کے لیے کوئی تخمینہ الگورتھم کسی بھی x کے لیے نہیں جانا جاتا سوائے تین آسان نکات کے۔ انٹیجر پوائنٹس پر، یہ فیصلہ کرنے کا متعلقہ فیصلہ مسئلہ کہ آیا دیا گیا گراف کے رنگ کا ہو سکتا ہے، این پی ہارڈ ہے۔ اس طرح کے مسائل کو باؤنڈڈ ایرر پروبیبلسٹک الگورتھم کے ذریعے کسی بھی ضرب عنصر کے قریب نہیں کیا جا سکتا جب تک کہ NP = RP نہ ہو، کیونکہ کوئی بھی ضرب کا تخمینہ 0 اور 1 کی اقدار میں فرق کرے گا، مؤثر طریقے سے باؤنڈڈ ایرر پروبیبلسٹک کثیر الجہتی وقت میں فیصلہ ورژن کو حل کرے گا۔ خاص طور پر، اسی مفروضے کے تحت، یہ مکمل طور پر کثیر الجہتی وقت بے ترتیب تخمینہ اسکیم (ایف پی آر اے ایس) کے امکان کو مسترد کرتا ہے۔ دیگر نکات کے لیے، زیادہ پیچیدہ دلائل کی ضرورت ہے، اور سوال فعال تحقیق کا مرکز ہے۔ یہ معلوم ہے کہ کسی بھی x> 2 کے لیے کمپیوٹنگ کے لیے کوئی FPRAS نہیں ہے، جب تک کہ NP = RP برقرار نہ رہے۔ حوالہ جات نوٹ کریں۔ بیرونی روابط پلینیٹ میتھ کرومیٹک کثیر الجہتی کوڈ برائے کمپیوٹنگ ٹوٹے، کرومیٹک اور فلو کثیر الجہتی بذریعہ گیری ہیگارڈ، ڈیوڈ جے پیئرس اور گورڈن روئل: گراف غیر متغیر گراف کلرنگ