Hadwiger number
گراف تھیوری میں، غیر ہدایت شدہ گراف کا ہاڈوگر نمبر سب سے بڑے مکمل گراف کا سائز ہے جسے کناروں کو سکڑ کر حاصل کیا جا سکتا ہے۔ مساوی طور پر، ہاڈوگر نمبر سب سے بڑا نمبر ہے جس کے لیے مکمل گراف معمولی ہے، ایک چھوٹا گراف جو کنارے کے سکڑنے اور سرے اور کنارے کے حذف ہونے سے حاصل کیا جاتا ہے۔ ہاڈوگر نمبر کو سنکچن کلک نمبر یا ہومومورفزم ڈگری کے نام سے بھی جانا جاتا ہے۔ اس کا نام ہیوگو ہاڈویگر کے نام پر رکھا گیا ہے، جس نے اسے 1943 میں ہاڈویگر قیاس کے ساتھ مل کر متعارف کرایا تھا، جس میں کہا گیا ہے کہ ہاڈویگر نمبر ہمیشہ کم از کم اتنا ہی بڑا ہوتا ہے جتنا کہ کرومیٹک نمبر۔ جن گرافوں میں ہاڈوگر نمبر زیادہ سے زیادہ چار ہے ان کی خصوصیت یہ ہے: ہاڈوگر نمبر پر کسی بھی محدود باؤنڈ والے گراف کم ہوتے ہیں، اور ان کا کرومیٹک نمبر چھوٹا ہوتا ہے۔ گراف کے ہاڈوگر نمبر کا تعین کرنا این پی سخت لیکن فکسڈ پیرامیٹر ٹریک ایبل ہے۔ چھوٹے ہاڈوگر نمبر والے گراف A گراف میں ہاڈوگر نمبر زیادہ سے زیادہ دو ہوتا ہے اگر اور صرف اس صورت میں جب یہ جنگل ہو، تین ورٹیکس کے لیے مکمل نابالغ صرف ایک سائیکل کو معاہدہ کرکے تشکیل دیا جا سکتا ہے۔ ایک گراف میں ہاڈوگر نمبر زیادہ سے زیادہ تین ہوتا ہے اگر اور صرف اس صورت میں جب اس کی تین چوڑائی زیادہ سے زیادہ دو ہو، جو اس صورت میں درست ہے جب اس کے دو جڑے ہوئے اجزاء میں سے ہر ایک سیریز متوازی گراف ہو۔ ویگنر کا نظریہ، جو پلانر گراف کو ان کے ممنوعہ نابالغوں کی طرف سے نمایاں کرتا ہے، اس سے یہ ظاہر ہوتا ہے کہ پلانر گراف میں زیادہ سے زیادہ چار ہاڈوگر نمبر ہوتے ہیں۔ اسی مقالے میں جس نے اس نظریہ کو ثابت کیا، ہیڈویگر نمبر کے ساتھ گراف کو بھی زیادہ سے زیادہ چار زیادہ واضح طور پر نمایاں کیا: وہ گراف ہیں جو کلک-سم آپریشنز کے ذریعے بنائے جا سکتے ہیں جو آٹھ ورٹیکس ویگنر گراف کے ساتھ پلانر گراف کو جوڑتے ہیں۔ زیادہ سے زیادہ پانچ ہاڈوگر نمبر والے گرافوں میں اپیکس گراف اور لنک لیس ایمبیڈ ایبل گراف شامل ہیں، ان دونوں میں ان کے ممنوعہ نابالغوں کے درمیان مکمل گراف ہے۔ عمودی اور ہاڈوگر نمبر والے ہر گراف کے کنارے ہوتے ہیں۔ یہ باؤنڈ تنگ ہے: ہر ایک کے لیے، ہاڈوگر نمبر کے ساتھ گراف موجود ہیں جن کے کنارے ہوتے ہیں۔ اگر کسی گراف میں ہاڈوگر نمبر ہے، تو اس کے تمام ذیلی گرافوں میں بھی زیادہ سے زیادہ ہاڈوگر نمبر ہوتا ہے، اور اس کے بعد اس میں انحطاط ہونا ضروری ہے۔ لہذا، باؤنڈڈ ہاڈوگر نمبر والے گراف بہت کم گراف ہوتے ہیں۔ کلرنگ دی ہاڈویگر قیاس میں کہا گیا ہے کہ ہاڈویگر نمبر ہمیشہ کم از کم اتنا ہی بڑا ہوتا ہے جتنا کہ کرومیٹک نمبر۔ یعنی، ہیڈویگر نمبر والے ہر گراف میں زیادہ تر رنگوں کے ساتھ گراف کا رنگ ہونا چاہیے۔ یہ معاملہ (ویگنر کی طرف سے اس ہاڈویگر نمبر کے ساتھ گرافوں کی خصوصیت سے) پلینر گرافوں کے رنگوں پر چار رنگوں کے نظریہ کے مساوی ہے، اور قیاس بھی ثابت ہوا ہے، لیکن اس کی بڑی اقدار کے لیے غیر ثابت ہے۔ ان کی کم انحطاط کی وجہ سے، زیادہ سے زیادہ ہاڈوگر نمبر والے گراف کو رنگوں کا استعمال کرتے ہوئے لالچی رنگ الگورتھم کے ذریعے رنگا جا سکتا ہے۔ کمپیوٹیشنل پیچیدگی یہ جانچنا کہ آیا دیئے گئے گراف کا ہاڈوگر نمبر کم از کم ایک دی گئی قیمت ہے، این پی مکمل ہے، جس سے یہ پتہ چلتا ہے کہ ہاڈوگر نمبر کا تعین این پی سخت ہے۔ تاہم، مسئلہ فکسڈ پیرامیٹر ٹریک ایبل ہے: وقت کی مقدار میں سب سے بڑے کلک مائنر کو تلاش کرنے کے لیے ایک الگورتھم موجود ہے جو صرف کثیر الجہتی طور پر گراف کے سائز پر منحصر ہے، لیکن تیزی سے اندر۔ مزید برآں، کثیر الجہتی وقت کے الگورتھم ہاڈوگر نمبر کا تخمینہ سب سے بڑے مکمل ذیلی گراف کے سائز کے بہترین کثیر الجہتی وقت کے تخمینے (فرض کریں کہ P ष्णپ) سے نمایاں طور پر زیادہ درست طریقے سے لگا سکتے ہیں۔ متعلقہ تصورات گراف کا آکرومیٹک نمبر سب سے بڑے گروہ کا سائز ہے جو آزاد سیٹوں کے خاندان کو معاہدہ کرکے تشکیل دیا جا سکتا ہے۔ لامحدود گرافوں میں ناقابل شمار گروہ نابالغوں کو پناہ گاہوں کے لحاظ سے نمایاں کیا جا سکتا ہے، جو کچھ تعاقب سے بچنے والے کھیلوں کے لیے چوری کی حکمت عملیوں کو باقاعدہ بناتے ہیں: اگر ہاڈویگر نمبر بے شمار ہے، تو یہ گراف میں پناہ گاہ کی سب سے بڑی ترتیب کے برابر ہے۔ ہیڈویگر نمبر والے ہر گراف میں زیادہ تر کلکس (مکمل ذیلی گراف) ہوتے ہیں۔ گراف پیرامیٹرز کی ایک کلاس کی وضاحت کرتا ہے جسے وہ فنکشن کہتے ہیں، جس میں ہاڈوگر نمبر شامل ہے۔ گراف سے لے کر انٹیجرز تک کے ان افعال کو بغیر کناروں والے گرافوں پر صفر ہونا ضروری ہے، معمولی یک سنگی ہونا ضروری ہے، جب ایک نیا ورٹیکس شامل کیا جاتا ہے جو پچھلے تمام عمودی حصوں سے متصل ہوتا ہے، اور دو ذیلی گرافوں سے بڑی قیمت لینے کے لیے ایک سے بڑھتا ہے۔ ایک کلک جداکار کے دونوں طرف۔ اس طرح کے تمام افعال کا مجموعہ عنصر وار کم سے کم کرنے اور زیادہ سے زیادہ کرنے کی کارروائیوں کے تحت ایک مکمل جالی بناتا ہے۔ اس جالی میں نچلا عنصر ہاڈوگر نمبر ہے، اور اوپری عنصر تین چوڑائی ہے۔ فوٹ نوٹ حوالہ جات۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ گراف غیر متغیر گراف معمولی نظریہ