End (graph theory)
لامحدود گرافوں کی ریاضی میں، گراف کا اختتام، بدیہی طور پر، ایک ایسی سمت کی نمائندگی کرتا ہے جس میں گراف لامحدود تک پھیلا ہوا ہے۔ اختتام کو ریاضیاتی طور پر لامحدود راستوں کی مساوات کی کلاسوں کے طور پر باقاعدہ بنایا جا سکتا ہے، جیسا کہ گراف پر تعاقب سے بچنے والے کھیلوں کی حکمت عملیوں کو بیان کرنے والی پناہ گاہیں، یا (مقامی طور پر محدود گراف کے معاملے میں) گراف سے وابستہ ٹپوولوجیکل خالی جگہوں کے ٹپوولوجیکل سروں کے طور پر۔ گراف کے سروں کو (کیلی گراف کے ذریعے) محدود طور پر تیار کردہ گروپوں کے سروں کی وضاحت کے لیے استعمال کیا جا سکتا ہے۔ محدود طور پر تیار کردہ لامحدود گروپوں کے ایک، دو، یا لامحدود طور پر بہت سے سرے ہوتے ہیں، اور گروپوں کے سروں کے بارے میں اسٹالنگز تھیوریم ایک سے زیادہ سروں والے گروپوں کے لیے سڑنا فراہم کرتا ہے۔ تعریف اور خصوصیت گراف کے اختتام کو لامحدود راستوں کی مساوات کی کلاسوں کے لحاظ سے بیان کیا گیا تھا۔ ایک لامحدود گراف میں اے ایک نیم لامحدود سادہ راستہ ہے ؛ یعنی، یہ عمودی حصوں کی ایک لامحدود ترتیب ہے جس میں ہر ایک عمودی حصہ ترتیب میں زیادہ سے زیادہ ایک بار ظاہر ہوتا ہے اور ترتیب میں ہر دو مسلسل عمودی حصے گراف میں کسی کنارے کے دو اختتامی نکات ہوتے ہیں۔ ہیلن کی تعریف کے مطابق، دو شعاعیں مساوی ہیں اگر کوئی ایسی کرن ہو (جو دو دی گئی کرنوں میں سے ایک کے برابر ہو سکتی ہے) جس میں ہر ایک میں لامحدود طور پر بہت سے عمودی حصے ہوں۔ یہ ایک مساوات کا تعلق ہے: ہر کرن اپنے آپ کے مساوی ہے، تعریف دو شعاعوں کی ترتیب کے حوالے سے ہم آہنگ ہے، اور اسے عارضی دکھایا جا سکتا ہے۔ لہذا، یہ تمام شعاعوں کے سیٹ کو مساوات کی کلاسوں میں تقسیم کرتا ہے، اور ہیلن نے اختتام کو ان مساوات کی کلاسوں میں سے ایک کے طور پر بیان کیا۔ ایک ہی مساوات کے تعلق کی ایک متبادل تعریف بھی استعمال کی گئی ہے: دو شعاعیں اور مساوی ہیں اگر عمودی حصوں کا کوئی محدود مجموعہ نہ ہو جو ان کے لامحدود بہت سے عمودی حصوں کو ان کے لامحدود بہت سے عمودی حصوں سے الگ کرتا ہے۔ یہ ہالین کی تعریف کے مساوی ہے: اگر ہالین کی تعریف سے شعاع موجود ہے، تو کسی بھی جداکار میں لامحدود طور پر بہت سے نکات ہونے چاہئیں اور اس لیے وہ محدود نہیں ہو سکتا، اور اس کے برعکس اگر موجود نہیں ہے تو ایک ایسا راستہ جو ممکنہ طور پر زیادہ سے زیادہ بار بدلتا ہے اور مطلوبہ محدود جداکار بناتا ہے۔ اینڈز میں پناہ گاہوں کے لحاظ سے بھی زیادہ ٹھوس خصوصیت ہوتی ہے، وہ افعال جو گراف پر تعاقب سے بچنے والے کھیلوں کے لیے چوری کی حکمت عملی بیان کرتے ہیں۔ زیر بحث کھیل میں، ایک ڈاکو پولیس اہلکاروں کے ایک سیٹ سے بچنے کی کوشش کر رہا ہے جس کے کناروں کے ساتھ ورٹیکس سے ورٹیکس کی طرف بڑھ رہا ہے۔ پولیس کے پاس ہیلی کاپٹر ہوتے ہیں اور اس لیے انہیں کناروں کی پیروی کرنے کی ضرورت نہیں ہوتی ؛ تاہم ڈاکو پولیس کو آتے ہوئے دیکھ سکتا ہے اور ہیلی کاپٹر کے اترنے سے پہلے آگے کہاں جانا ہے اس کا انتخاب کر سکتا ہے۔ ایک پناہ گاہ ایک فنکشن ہے جو پولیس کے مقامات کے ہر سیٹ کو حذف کرکے بنائے گئے ذیلی گراف کے منسلک اجزاء میں سے کسی ایک کا نقشہ بناتا ہے۔ ایک ڈاکو کھیل کے ہر دور میں اس جزو کے اندر کسی سرے پر جا کر پولیس سے بچ سکتا ہے۔ پناہ گاہوں کو مستقل مزاجی کی خاصیت کو پورا کرنا چاہیے (اس ضرورت کے مطابق کہ ڈاکو ان چوٹیوں سے نہیں گزر سکتا جن پر پولیس پہلے ہی اتر چکی ہے): اگر یہ پولیس کے دیئے گئے سیٹ کے لیے مقامات کا ایک ذیلی سیٹ ہے، اور دونوں درست سیٹ ہیں، تو پھر اس کا ایک سپر سیٹ ہونا چاہیے۔ ایک پناہ گاہ کا حکم ہوتا ہے اگر پولیس کے مقامات کا مجموعہ جس کے لیے وہ فرار کی حکمت عملی فراہم کرتا ہے اس میں گراف میں عمودی سے کم کے تمام ذیلی سیٹ شامل ہوتے ہیں۔ خاص طور پر، اس میں ترتیب (سب سے چھوٹا الیف نمبر) ہوتا ہے اگر یہ عمودی کے ہر محدود ذیلی سیٹ کو کسی جزو کے ساتھ نقشہ بناتا ہے۔ ہر کرن ترتیب کی پناہ گاہ سے مطابقت رکھتی ہے، یعنی فنکشن ؛ جو ہر محدود سیٹ کو اس کے منفرد جزو سے جوڑتی ہے جس میں کرن کے لامحدود کئی عمودی حصے ہوتے ہیں۔ اس کے برعکس، ترتیب کی ہر پناہ گاہ کو ایک کرن کے ذریعے اس طرح بیان کیا جا سکتا ہے۔ دو شعاعیں مساوی ہوتی ہیں اگر اور صرف اس صورت میں جب وہ ایک ہی پناہ گاہ کی وضاحت کریں، تو گراف کے سرے اس کی ترتیب کی پناہ گاہوں کے ساتھ ایک دوسرے سے مطابقت رکھتے ہیں۔ مثال کے طور پر اگر لامحدود گراف خود ایک کرن ہے، تو اس میں لامحدود طور پر بہت سے رے سب گراف ہوتے ہیں، جن میں سے ایک کے ہر سرے سے شروع ہوتا ہے۔ تاہم، یہ تمام شعاعیں ایک دوسرے کے مساوی ہیں، اس لیے اس کا صرف ایک اختتام ہوتا ہے۔ اگر جنگل ہے (یعنی ایک ایسا گراف جس میں کوئی محدود چکر نہیں ہے)، تو کسی بھی دو شعاعوں کا چوراہا یا تو ایک راستہ یا ایک شعاع ہے ؛ دو شعاعیں مساوی ہیں اگر ان کا چوراہا ایک شعاع ہے۔ اگر بیس ورٹیکس کا انتخاب ہر منسلک جزو میں کیا جاتا ہے، تو بیس ورٹیکس کے ہر سرے پر ایک منفرد کرن ہوتی ہے جو بیس ورٹیکس میں سے ایک سے شروع ہوتی ہے، لہذا سروں کو ان کینونکل کرنوں کے ساتھ ایک سے ایک خط و کتابت میں رکھا جا سکتا ہے۔ ہر قابل گنتی گراف میں ایک پھیلا ہوا جنگل ہوتا ہے جس کے سرے ایک جیسے ہوتے ہیں۔ تاہم، صرف ایک سرے کے ساتھ بے شمار لامحدود گراف موجود ہیں جن میں ہر پھیلے ہوئے درخت کے لامحدود کئی سرے ہوتے ہیں۔ اگر ایک لامحدود گرڈ گراف ہے، تو اس میں بہت سی کرنیں ہوتی ہیں، اور من مانی طور پر ورٹیکس-ڈسجوائنٹ کرنوں کے بڑے سیٹ ہوتے ہیں۔ تاہم، اس کا صرف ایک اختتام ہے۔ یہ پناہ گاہوں کے لحاظ سے سروں کی خصوصیت کا استعمال کرتے ہوئے سب سے زیادہ آسانی سے دیکھا جا سکتا ہے: عمودی حصوں کے کسی بھی محدود سیٹ کو ہٹانے سے بالکل ایک لامحدود جڑا ہوا جزو رہ جاتا ہے، لہذا صرف ایک ہی پناہ گاہ ہوتی ہے (وہ جو ہر محدود سیٹ کو منفرد لامحدود جڑے ہوئے جزو سے جوڑتا ہے)۔ ٹوپولوجیکل سروں سے تعلق پوائنٹ سیٹ ٹوپولوجی میں، ایک ایسے اختتام کا تصور موجود ہے جو گراف تھیوری میں اختتام کے تصور سے ملتا جلتا ہے، لیکن بالکل ایسا نہیں ہے، جو اس سے بہت پہلے کا ہے۔ اگر کسی ٹپوولوجیکل جگہ کو کمپیکٹ سیٹوں کی گھونسلے والی ترتیب سے ڈھانپا جا سکتا ہے، تو جگہ کا اختتام کمپیکٹ سیٹوں کی تکمیل کے اجزاء کا ایک سلسلہ ہے۔ یہ تعریف کمپیکٹ سیٹوں کے انتخاب پر منحصر نہیں ہے: اس طرح کے ایک انتخاب کے ذریعہ بیان کردہ سروں کو کسی دوسرے انتخاب کے ذریعہ بیان کردہ سروں کے ساتھ ون ٹو ون خط و کتابت میں رکھا جا سکتا ہے۔ ایک لامحدود گراف کو ٹوپولوجیکل اسپیس میں دو مختلف لیکن متعلقہ طریقوں سے بنایا جا سکتا ہے: گراف کے ہر سرے کو ایک نقطہ سے اور گراف کے ہر کنارے کو ایک کھلے یونٹ کے وقفے سے تبدیل کرنے سے گراف سے ایک ہاؤس ڈورف اسپیس پیدا ہوتی ہے جس میں ایک سیٹ کی وضاحت کی جاتی ہے جب بھی گراف کے کنارے کے ساتھ ہر چوراہا یونٹ کے وقفے کا کھلا ذیلی سیٹ ہوتا ہے۔ گراف کے ہر سرے کو ایک نقطہ سے اور گراف کے ہر کنارے کو ایک نقطہ سے تبدیل کرنے سے ایک غیر ہاؤز ڈورف جگہ پیدا ہوتی ہے جس میں کھلے سیٹ اس پراپرٹی کے ساتھ سیٹ ہوتے ہیں، اگر اس کا ایک سرے سے تعلق ہے، تو اسی طرح ہر کنارے کو اس کے اختتامی نکات میں سے ایک کے طور پر حاصل ہوتا ہے۔ دونوں صورتوں میں، کا ہر محدود ذیلی گراف ٹپوولوجیکل اسپیس کے ایک کمپیکٹ ذیلی جگہ سے مطابقت رکھتا ہے، اور ہر کمپیکٹ ذیلی جگہ ایک محدود ذیلی گراف سے مطابقت رکھتی ہے، ہاؤس ڈورف کے معاملے میں، کناروں کے محدود طور پر بہت سے کمپیکٹ مناسب ذیلی سیٹ۔ اس طرح، گراف کو کمپیکٹ سیٹوں کی گھونسلے والی ترتیب سے احاطہ کیا جا سکتا ہے اگر اور صرف اس صورت میں جب یہ مقامی طور پر محدود ہو، جس میں ہر سرے پر کناروں کی ایک محدود تعداد ہو۔ اگر کوئی گراف جڑا ہوا ہے اور مقامی طور پر محدود ہے، تو اس میں ایک کمپیکٹ کور ہوتا ہے جس میں سیٹ کچھ من مانی طور پر منتخب کردہ ابتدائی ورٹیکس سے زیادہ سے زیادہ فاصلے پر عمودی سیٹ ہوتا ہے۔ اس صورت میں کوئی بھی پناہ گاہ ٹپوولوجیکل اسپیس کے اختتام کی وضاحت کرتی ہے جس میں اور اس کے برعکس، اگر ٹوپوولوجیکل اسپیس کا ایک اختتام ہے جس سے اس کی وضاحت کی گئی ہے، تو یہ ایک پناہ گاہ کی وضاحت کرتا ہے جس میں جزو موجود ہے، جہاں کوئی بھی تعداد اتنی بڑی ہے جس میں موجود ہے۔ اس طرح، جڑے ہوئے اور مقامی طور پر محدود گرافوں کے لیے، ٹپوولوجیکل سرے گراف تھیوریٹک سروں کے ساتھ ون ٹو ون خط و کتابت میں ہوتے ہیں۔ ان گرافوں کے لیے جو مقامی طور پر محدود نہیں ہو سکتے، گراف اور اس کے سروں سے ٹپوولوجیکل اسپیس کی وضاحت کرنا اب بھی ممکن ہے۔ اس جگہ کو میٹرک اسپیس کے طور پر پیش کیا جا سکتا ہے اگر اور صرف اس صورت میں جب گراف میں ایک عام پھیلا ہوا درخت ہو، ایک جڑا ہوا پھیلا ہوا درخت ایسا ہو کہ ہر گراف کا کنارہ آباؤ اجداد-نسل کے جوڑے کو جوڑتا ہو۔ اگر ایک عام پھیلا ہوا درخت موجود ہے، تو اس کے سروں کا مجموعہ وہی ہے جو دیئے گئے گراف میں ہے: گراف کے ہر سرے پر درخت میں بالکل ایک لامحدود راستہ ہونا چاہیے۔ خاص قسم کے سرے آزاد سرے گراف کے ایک سرے کو آزاد سرے کے طور پر بیان کیا جاتا ہے اگر گراف کے دوسرے تمام سروں سے الگ ہونے والی خاصیت کے ساتھ عمودی حصوں کا ایک محدود مجموعہ ہو۔ (یعنی، پناہ گاہوں کے لحاظ سے، ہر دوسرے سرے سے جدا ہے۔) محدود طور پر کئی سروں والے گراف میں، ہر سرے کو آزاد ہونا چاہیے۔ یہ ثابت کرتا ہے کہ، اگر لامحدود طور پر کئی سرے ہیں، تو یا تو ایک ایسا اختتام موجود ہے جو آزاد نہیں ہے، یا شعاعوں کا ایک لامحدود خاندان موجود ہے جو ایک مشترکہ ابتدائی سرے کا اشتراک کرتے ہیں اور بصورت دیگر ایک دوسرے سے جدا ہوتے ہیں۔ موٹے سرے گراف کا ایک موٹا سرے ایک ایسا سرے ہے جس میں لامحدود طور پر بہت سی جوڑی کے لحاظ سے مختلف شعاعیں ہوتی ہیں۔ ہیلن کا گرڈ تھیوریم ان گرافوں کی خصوصیت رکھتا ہے جو موٹے سروں پر مشتمل ہوتے ہیں: وہ بالکل وہی گراف ہوتے ہیں جن میں ذیلی گراف کے طور پر ہیکساگونل ٹائلنگ کی ذیلی تقسیم ہوتی ہے۔ خاص قسم کے گراف سمیٹرک اور تقریبا سمیٹرک گراف ایک جڑے ہوئے مقامی طور پر محدود گراف کو "تقریبا سمیٹرک" کے طور پر بیان کرتے ہیں اگر کوئی ورٹیکس اور ایسی تعداد موجود ہو کہ، ہر دوسرے ورٹیکس کے لیے، گراف کی ایک آٹومورفزم ہو جس کی تصویر فاصلے کے اندر ہو ؛ مساوی طور پر، ایک جڑا ہوا مقامی طور پر محدود گراف تقریبا سمیٹرک ہوتا ہے اگر اس کے آٹومورفزم گروپ میں محدود طور پر بہت سے مدار ہوں۔ جیسا کہ وہ دکھاتا ہے، ہر جڑے ہوئے مقامی طور پر محدود تقریبا ہم آہنگ گراف کے لیے، سروں کی تعداد یا تو زیادہ سے زیادہ دو ہوتی ہے یا ناقابل شمار ؛ اگر یہ ناقابل شمار ہے، تو سروں میں کینٹر سیٹ کی ٹوپولوجی ہوتی ہے۔ مزید برآں، موہر سے پتہ چلتا ہے کہ سروں کی تعداد چیزر مستقل کو کنٹرول کرتی ہے جہاں گراف کے عمودی حصوں کے تمام محدود غیر خالی سیٹوں پر رینج ہوتی ہے اور جہاں ایک اختتامی نقطہ کے ساتھ کناروں کے سیٹ کی نشاندہی ہوتی ہے۔ بے شمار کئی سروں والے تقریبا ہم آہنگ گرافوں کے لیے، تاہم، صرف دو سروں والے تقریبا ہم آہنگ گرافوں کے لیے،۔ کیلی گراف گروپ کے لیے ہر گروپ اور جنریٹرز کا ایک سیٹ کیلی گراف کا تعین کرتا ہے، ایک گراف جس کے عمودی حصے گروپ کے عناصر ہوتے ہیں اور کنارے عناصر کے جوڑے ہوتے ہیں جہاں جنریٹرز میں سے ایک ہوتا ہے۔ محدود طور پر تیار کردہ گروپ کے معاملے میں، گروپ کے سروں کو جنریٹرز کے محدود سیٹ کے لیے کیلی گراف کے سروں کے طور پر بیان کیا جاتا ہے۔ یہ تعریف جنریٹرز کے انتخاب کے تحت غیر متغیر ہے، اس معنی میں کہ اگر جنریٹرز کے دو مختلف محدود سیٹ کا انتخاب کیا جاتا ہے، تو دو کیلی گراف کے سرے ایک دوسرے کے ساتھ ایک دوسرے سے مطابقت رکھتے ہیں۔ مثال کے طور پر، ہر مفت گروپ کے پاس کیلی گراف (اس کے مفت جنریٹرز کے لیے) ہوتا ہے جو کہ ایک درخت ہوتا ہے۔ ایک جنریٹر پر آزاد گروپ کے دو سروں کے ساتھ، اس کے کیلی گراف کے طور پر دوگنا لامحدود راستہ ہے۔ ہر دوسرے آزاد گروپ کے لامحدود کئی سرے ہوتے ہیں۔ ہر حتمی طور پر تیار کردہ لامحدود گروپ کے یا تو 1، 2، یا لامحدود طور پر بہت سے سرے ہوتے ہیں، اور گروپوں کے سروں کے بارے میں اسٹالنگز تھیوریم ایک سے زیادہ سروں والے گروپوں کا سڑنا فراہم کرتا ہے۔ خاص طور پر: ایک حتمی طور پر تیار کردہ لامحدود گروپ کے 2 سرے ہوتے ہیں اگر اور صرف اس صورت میں جب اس میں محدود انڈیکس کا چکور ذیلی گروپ ہو۔ ایک حتمی طور پر تیار کردہ لامحدود گروپ کے لامحدود سرے ہوتے ہیں اگر اور صرف اس صورت میں جب یہ یا تو انضمام کے ساتھ ایک غیر معمولی آزاد پروڈکٹ ہو یا محدود انضمام کے ساتھ ایچ این این-ایکسٹینشن ہو۔ دیگر تمام حتمی طور پر پیدا شدہ لامحدود گروہوں کا بالکل ایک اختتام ہوتا ہے۔ نوٹ حوالہ جات گراف تھیوری اشیاء لامحدود گراف