Graph pebbling
گراف پیبلنگ ایک ریاضیاتی کھیل ہے جو گراف پر کھیلا جاتا ہے جس کے ہر سرے پر صفر یا اس سے زیادہ کنکریاں ہوتی ہیں۔ 'گیم پلے' کنکریٹ چالوں کے ایک سلسلے پر مشتمل ہے۔ گراف پر کنکریوں کی حرکت کم از کم دو کنکریوں کے ساتھ ایک ورٹیکس کا انتخاب کرنے، اس سے دو کنکریوں کو ہٹانے، اور ایک کو ملحقہ ورٹیکس میں شامل کرنے پر مشتمل ہوتی ہے (دوسرا ہٹایا ہوا کنکری کھیل سے خارج کر دیا جاتا ہے)۔ π (G)، گراف G کا کنکریٹ نمبر، سب سے کم قدرتی نمبر n ہے جو مندرجہ ذیل شرط کو پورا کرتا ہے: گراف میں کسی بھی ہدف یا 'جڑ' کے سرے اور گراف پر n کنکریٹ کی کسی بھی ابتدائی ترتیب کو دیکھتے ہوئے، یہ ممکن ہے کہ کنکریٹ حرکتوں کے ایک سلسلے کے بعد، ایک نئی ترتیب تک پہنچ جائے جس میں نامزد جڑ کے سرے میں ایک یا زیادہ کنکریٹ ہوں۔ مثال کے طور پر، 2 عمودی اور 1 کنارے والے گراف پر ان کو جوڑنے والا کنکریٹ نمبر 2 ہے۔ اس بات سے کوئی فرق نہیں پڑتا کہ دو کنکریاں گراف کے عمودی حصوں پر کس طرح رکھی گئی ہیں، کسی کنکری کو گراف کے کسی بھی عمودی حصے میں منتقل کرنا ہمیشہ ممکن ہے۔ گراف پیبلنگ کے مرکزی سوالات میں سے ایک دیئے گئے گراف G کے لیے π (G) کی قدر ہے۔ پیبلنگ کے دیگر موضوعات میں کور پیبلنگ، بہترین پیبلنگ، ڈومینیشن کور پیبلنگ، باؤنڈ، اور پیبلنگ نمبروں کے لیے تھریشولڈز کے ساتھ ساتھ گہرے گراف شامل ہیں۔ π (G)-گراف کا کنکر نمبر کنکر کے کھیل کو سب سے پہلے لاگریاس اور ساکس نے نمبر تھیوری میں کسی خاص مسئلے کو حل کرنے کے آلے کے طور پر تجویز کیا تھا۔ 1989 میں ایف۔ آر۔ کے۔ چنگ نے اس تصور کو ادب میں متعارف کرایا اور کنکریٹ نمبر، π (G) کی وضاحت کی۔ n چوٹیوں پر مکمل گراف کے لیے کنکر نمبر کی آسانی سے n ہونے کی تصدیق کی جاتی ہے: اگر ہمارے پاس گراف پر ڈالنے کے لیے (n−1) کنکر ہوتے تو ہم ہدف کے علاوہ ہر سرے پر ایک کنکر لگا سکتے تھے۔ چونکہ کسی بھی سرے پر دو یا زیادہ کنکریاں نہیں ہوتیں، اس لیے کوئی حرکت ممکن نہیں ہے، اس لیے ہدف پر کنکری رکھنا ناممکن ہے۔ اس طرح، کنکریٹ نمبر n − 1 سے بڑا ہونا چاہیے۔ این کنکریوں کو دیکھتے ہوئے، دو ممکنہ معاملات ہیں۔ اگر ہر سرے پر ایک کنکر ہو تو کسی حرکت کی ضرورت نہیں ہے۔ اگر کوئی ورٹیکس ننگا ہے، تو کم از کم ایک دوسرے ورٹیکس پر دو کنکریاں ہونی چاہئیں، اور ایک کنکری حرکت ایک کنکری کو مکمل گراف میں کسی بھی ہدف ورٹیکس میں شامل کرنے کی اجازت دیتی ہے۔ گراف کے خاندانوں کے لیے π (G) کنکریٹ نمبر گراف کے درج ذیل خاندانوں کے لیے جانا جاتا ہے:، جہاں n عمودی پر ایک مکمل گراف ہے۔ ، n عمودی پر پاتھ گراف کہاں ہے۔ ، n عمودی پر پہیے کا گراف کہاں ہے۔ گراہم کے کنکریٹنگ قیاس آرائی نے رونالڈ گراہم کو اس قیاس آرائی کا سہرا دیا کہ گراف کے کارٹیشین پروڈکٹ کی کنکریٹنگ نمبر زیادہ سے زیادہ پروڈکٹ میں موجود عوامل کے کنکریٹنگ نمبروں کے پروڈکٹ کے برابر ہے۔ یہ گراہم کے کنبلنگ قیاس کے نام سے جانا جاتا ہے۔ یہ ابھی تک حل نہیں ہوا ہے، حالانکہ خصوصی معاملات معلوم ہیں۔ γ (G)-کرل اور دیگر گراف کا کور پیبلنگ نمبر۔ کور پیبلنگ کا تصور متعارف کرایا۔ γ (G)، گراف کا کور کنکریٹ نمبر کنکریٹ کی کم از کم تعداد ہے جس کی ضرورت ہوتی ہے تاکہ کنکریٹ کی کسی بھی ابتدائی ترتیب سے، کنکریٹ کی حرکتوں کے ایک سلسلے کے بعد، گراف کا احاطہ کیا جائے: ہر سرے پر کم از کم ایک کنکریٹ ہو۔ اسٹیکنگ تھیوریم کہلانے والا نتیجہ کسی بھی گراف کے لیے کور پیبلنگ نمبر تلاش کرتا ہے۔ اسٹیکنگ تھیوریم اسٹیکنگ تھیوریم کے مطابق، کنکریوں کی ابتدائی ترتیب جس میں سب سے زیادہ کنکریوں کو حل کرنے کی ضرورت ہوتی ہے تب ہوتی ہے جب تمام کنکریوں کو ایک ہی سرے پر رکھا جاتا ہے۔ اس مشاہدے کی بنیاد پر، G میں ہر ورٹیکس v کی وضاحت کریں، جہاں d (u، v) u سے v تک کے فاصلے کو ظاہر کرتا ہے۔ پھر کور پیبلنگ نمبر سب سے بڑا s (v) ہے جس کا نتیجہ نکلتا ہے۔ γ (G) گراف کے خاندانوں کے لیے کور پیبلنگ نمبر گراف کے درج ذیل خاندانوں کے لیے جانا جاتا ہے:، جہاں n عمودی پر ایک مکمل گراف ہے۔ ، جہاں n عمودی پر ایک راستہ ہے۔ ، n عمودی پر پہیے کا گراف کہاں ہے۔ پیبل گیم پروف آف اسپیس ریفرنسز مزید پڑھنے والے گراف غیر متغیرات بھی دیکھیں۔