Queen's graph
ریاضی میں، ملکہ کا گراف ایک غیر ہدایت شدہ گراف ہے جو شطرنج کے تختے پر ملکہ کی تمام قانونی چالوں-شطرنج کے ٹکڑے-کی نمائندگی کرتا ہے۔ گراف میں، ہر سرے شطرنج کے تختے پر ایک مربع کی نمائندگی کرتا ہے، اور ہر کنارے ایک قانونی حرکت ہے جو ملکہ کر سکتی ہے، یعنی کسی بھی تعداد میں مربعوں کی طرف سے افقی، عمودی یا اخترن حرکت۔ اگر شطرنج بورڈ کے طول و عرض ہیں، تو انڈیوسڈ گراف کو ملکہ کا گراف کہا جاتا ہے۔ گراف کے آزاد سیٹ متعدد رانیوں کی تقرریوں سے مطابقت رکھتے ہیں جہاں کوئی دو رانیاں ایک دوسرے پر حملہ نہیں کر رہی ہیں۔ ان کا مطالعہ آٹھ رانیوں کے پہیلی میں کیا جاتا ہے، جہاں آٹھ غیر حملہ آور رانیوں کو ایک معیاری شطرنج کے تختے پر رکھا جاتا ہے۔ غالب سیٹ ملکہ کے انتظامات کی نمائندگی کرتے ہیں جہاں ہر مربع پر ایک ملکہ حملہ کرتی ہے یا اس پر قبضہ کرتی ہے۔ پانچ ملکہ، لیکن کم نہیں، شطرنج بورڈ پر غلبہ حاصل کر سکتی ہیں۔ گراف کے رنگ ہر مربع کو رنگنے کے طریقوں کی نمائندگی کرتے ہیں تاکہ ایک ملکہ ایک ہی رنگ کے کسی بھی دو مربعوں کے درمیان حرکت نہ کر سکے۔ شطرنج بورڈ کے لیے کم از کم n رنگوں کی ضرورت ہوتی ہے، لیکن بورڈ کے لیے 9 رنگوں کی ضرورت ہوتی ہے۔ خصوصیات ہر ملکہ کے گراف کے لیے ایک ہیملٹنین سائیکل ہوتا ہے، اور گراف دو جڑے ہوتے ہیں (اگر کسی ایک سرے کو ہٹا دیا جائے تو وہ جڑے رہتے ہیں)۔ اور ملکہ کے گراف کے خصوصی معاملات مکمل ہو چکے ہیں۔ آزادی گراف کا ایک آزاد سیٹ شطرنج کے تختے پر کئی رانیوں کی جگہ سے مطابقت رکھتا ہے جیسے کہ کوئی دو رانیاں ایک دوسرے پر حملہ نہ کر رہی ہوں۔ شطرنج کے بورڈ میں، سب سے بڑا آزاد سیٹ زیادہ سے زیادہ n عمودی پر مشتمل ہوتا ہے، کیونکہ کوئی بھی دو ملکہ ایک ہی صف یا کالم میں نہیں ہو سکتی ہیں۔ یہ اوپری حد n = 2 اور n = 3 کے علاوہ تمام n کے لیے حاصل کی جا سکتی ہے۔ n = 8 کے معاملے میں، یہ روایتی آٹھ ملکہ پہیلی ہے۔ غلبہ ملکہ کے گراف کا ایک غالب سیٹ ملکہ کی جگہ سے مطابقت رکھتا ہے کہ شطرنج کے تختے پر موجود ہر مربع پر یا تو ملکہ حملہ کرتی ہے یا اس پر قبضہ کرتی ہے۔ شطرنج کے تختے پر، پانچ رانیاں غلبہ حاصل کر سکتی ہیں، اور یہ کم از کم ممکنہ تعداد ہے (چار رانیاں کم از کم دو چوکوں کو بغیر کسی حملے کے چھوڑ دیتی ہیں)۔ پانچ رانیوں کی 4,860 ایسی جگہیں ہیں، جن میں وہ جگہیں بھی شامل ہیں جہاں رانیوں کا کنٹرول ہوتا ہے اور تمام چوکوں پر قبضہ ہوتا ہے، یعنی۔ وہ بالترتیب ایک دوسرے کی حفاظت کرتے ہیں۔ اس ذیلی گروپ میں، ایسی پوزیشنیں بھی ہیں جہاں ملکہ صرف مرکزی اخترن پر مربعوں پر قابض ہوتی ہیں (مثال کے طور پر۔ a1 سے h8 تک)، یا تمام ذیلی اخترن پر (مثال کے طور پر۔ A2 سے G8 تک)۔ غیر لوپنگ آئتاکار شطرنج بورڈ کو ٹورس یا سلنڈر سے تبدیل کرکے گراف میں ترمیم کرنے سے کم از کم غالب سیٹ کا سائز کم ہو کر چار ہو جاتا ہے۔ ملکہ کے گراف پر بورڈ کے مرکز میں واحد سرے کا غلبہ ہے۔ ملکہ کے گراف کا مرکزی ورٹیکس 8 ورٹیکس کے علاوہ سب سے متصل ہے: وہ ورٹیکس جو نائٹ کے گراف کے مرکزی ورٹیکس سے متصل ہیں۔ ڈومینیشن نمبرز ملکہ کے گراف کے ڈومینیشن نمبر d (n) کو سب سے چھوٹے ڈومینیٹنگ سیٹ کے سائز کے طور پر بیان کرتے ہیں، اور ڈائیگنل ڈومینیشن نمبر dd (n) کو سب سے چھوٹے ڈومینیٹنگ سیٹ کا سائز ہونا چاہیے جو کہ لمبے ڈائیگنل کا ذیلی سیٹ ہے۔ نوٹ کریں کہ تمام n کے لیے حد حاصل کی جاتی ہے، لیکن کے لیے نہیں۔ ڈومینیشن نمبر n میں لکیری ہے، جس کی حدود اس طرح دی گئی ہیں: d (n) کی ابتدائی اقدار 1، 1، 1، 2، 3، 3، 4، 5، 5، 5، 5 ہیں۔ Kn کو کسی ذیلی سیٹ کا زیادہ سے زیادہ سائز مان لیں کہ ہر نمبر کی برابری ایک جیسی ہو اور کوئی بھی تین نمبر ریاضی کی ترقی نہیں بناتے (سیٹ "مڈ پوائنٹ فری" ہے)۔ ملکہ کے گراف کا اخترن تسلط نمبر ہے۔ آزاد تسلط نمبر ID (n) کو ملکہ کے گراف میں سب سے چھوٹے آزاد، غالب سیٹ کے سائز کے طور پر بیان کریں۔ یہ معلوم ہے۔ ملکہ کے گراف کی رنگ کاری ہر سرے پر رنگوں کی اس طرح تفویض ہے کہ کسی بھی دو ملحقہ سرے کو ایک ہی رنگ نہ دیا جائے۔ مثال کے طور پر، اگر a8 سرخ رنگ کا ہے تو a-فائل، آٹھویں رینک یا لمبے اخترن پر کوئی دوسرا مربع سرخ رنگ کا نہیں ہو سکتا، کیونکہ ایک ملکہ a8 سے ان میں سے کسی بھی مربع میں منتقل ہو سکتی ہے۔ گراف کا کرومیٹک نمبر رنگوں کی سب سے چھوٹی تعداد ہے جسے اسے رنگنے کے لیے استعمال کیا جا سکتا ہے۔ ملکہ کے گراف کے معاملے میں، کم از کم n رنگوں کی ضرورت ہوتی ہے، کیونکہ کسی رینک یا فائل میں ہر مربع کو مختلف رنگ کی ضرورت ہوتی ہے (یعنی۔ قطاریں اور کالم کلکس ہیں)۔ کرومیٹک نمبر بالکل n ہے اگر (یعنی۔ n 6 کے ضرب سے ایک زیادہ یا ایک کم ہے)۔ ملکہ کے گراف کا کرومیٹک نمبر 9 ہے۔ اگر سیٹ سے کسی بھی ورٹیکس کو ہٹانے سے سیٹ کے پڑوس میں تبدیلی آتی ہے تو عمودی کا ایک سیٹ ناقابل تلافی ہوتا ہے۔ ہر سرے کے لیے، ایک ملحقہ سرے ہوتا ہے جو سیٹ میں کسی دوسرے سرے سے متصل نہیں ہوتا ہے۔ یہ ملکہ کے ایک سیٹ سے مطابقت رکھتا ہے جس میں سے ہر ایک کم از کم ایک مربع کو منفرد طور پر کنٹرول کرتا ہے۔ ملکہ کے گراف پر ایک غیر متزلزل سیٹ کے زیادہ سے زیادہ سائز IR (n) کی خصوصیت مشکل ہے۔ معروف اقدار میں تعاقب سے بچنے کا کھیل شامل ہے۔ ملکہ کے گراف پر تعاقب سے بچنے کے کھیل پر غور کریں جو مندرجہ ذیل اصولوں کے مطابق کھیلا جاتا ہے: ایک سفید ملکہ ایک کونے سے شروع ہوتی ہے اور ایک سیاہ ملکہ مخالف کونے میں۔ کھلاڑی متبادل حرکتیں کرتے ہیں، جن میں ملکہ کو ملحقہ سرے پر منتقل کرنا شامل ہوتا ہے جس پر گزرتے ہوئے (افقی، عمودی یا ترچھا) یا مخالف ملکہ سے متصل سرے پر اترے بغیر پہنچا جا سکتا ہے۔ اس کھیل کو جوڑی بنانے کی حکمت عملی کے ساتھ سفید فام جیت سکتے ہیں۔ کنگ کا گراف نائٹ کا گراف روک کا گراف بشپ کا گراف حوالہ جات ریاضیاتی شطرنج کے مسائل گراف کے پیرامیٹرک خاندانوں کو بھی دیکھیں۔