Halin graph
گراف تھیوری میں، ہیلن گراف ایک قسم کا پلانر گراف ہے، جو درخت کے پتوں کو سائیکل میں جوڑ کر بنایا گیا ہے۔ درخت کے کم از کم چار عمودی حصے ہونے چاہئیں، جن میں سے کسی کے بالکل دو پڑوسی نہیں ہیں۔ اسے ہوائی جہاز میں کھینچا جانا چاہیے تاکہ اس کے کناروں میں سے کوئی بھی پار نہ ہو (اسے پلانر ایمبیڈنگ کہا جاتا ہے)، اور سائیکل اس ایمبیڈنگ میں پتوں کو ان کی گھڑی کی سمت ترتیب میں جوڑتا ہے۔ اس طرح، سائیکل ہیلن گراف کا بیرونی رخ بناتا ہے، جس کے اندر درخت ہوتا ہے۔ ہیلن گراف کا نام جرمن ریاضی دان روڈولف ہیلن کے نام پر رکھا گیا ہے، جس نے 1971 میں ان کا مطالعہ کیا تھا۔ کیوبک ہیلن گراف-جن میں ہر ایک سر بالکل تین کناروں کو چھوتا ہے-کا مطالعہ کرک مین نے پہلے ہی ایک صدی سے زیادہ عرصہ پہلے کیا تھا۔ ہالین گراف پولی ہیڈرل گراف ہوتے ہیں، جس کا مطلب ہے کہ ہر ہالین گراف کو کنویکس پولی ہیڈرون کے عمودی اور کناروں کو بنانے کے لیے استعمال کیا جا سکتا ہے، اور ان سے بننے والے پولی ہیڈر کو چھت کے بغیر پولی ہیڈر یا گنبد کہا جاتا ہے۔ ہر ہیلن گراف میں اس کے تمام عمودی حصوں کے ساتھ ساتھ گراف کے عمودی حصوں کی تعداد تک تقریبا تمام لمبائی کا ایک ہیملٹنین سائیکل ہوتا ہے۔ ہالین گراف کو لکیری وقت میں پہچانا جا سکتا ہے۔ چونکہ ہیلن گراف کی تین چوڑائی کم ہوتی ہے، اس لیے بہت سے کمپیوٹیشنل مسائل جو دیگر قسم کے پلانر گراف پر مشکل ہوتے ہیں، جیسے کہ ہیملٹنین سائیکلوں کو تلاش کرنا، کو ہیلن گراف پر تیزی سے حل کیا جا سکتا ہے۔ مثال ایک ستارہ ایک ایسا درخت ہے جس کا بالکل ایک اندرونی ورٹیکس ہے۔ ایک ستارے پر ہیلن گراف کی تعمیر کو لاگو کرنے سے ایک پہیے کا گراف پیدا ہوتا ہے، جو ایک اہرام (کے کناروں) کا گراف ہے۔ مثلث پریزم کا گراف بھی ایک ہیلن گراف ہے: اسے اس طرح کھینچا جا سکتا ہے کہ اس کے آئتاکار چہروں میں سے ایک بیرونی چکر ہو، اور باقی کنارے ایک درخت کی تشکیل کرتے ہیں جس میں چار پتے، دو اندرونی عمودی اور پانچ کنارے ہوتے ہیں۔ فروچٹ گراف، پانچ سب سے چھوٹے کیوبک گرافوں میں سے ایک ہے جس میں کوئی غیر معمولی گراف آٹومورفزم نہیں ہے، یہ بھی ایک ہیلن گراف ہے۔ خصوصیات ہر ہیلن گراف 3 سے جڑا ہوا ہے، یعنی اس سے دو عمودی حصوں کو حذف کرنا اور باقی عمودی حصوں کو منقطع کرنا ممکن نہیں ہے۔ یہ ایج-منیمل 3 سے جڑا ہوا ہے، جس کا مطلب ہے کہ اگر اس کے کناروں میں سے کسی ایک کو ہٹا دیا جائے تو باقی گراف اب 3 سے جڑا نہیں رہے گا۔ اسٹینٹز تھیوریم کے مطابق، 3 جڑے ہوئے پلانر گراف کے طور پر، اسے کنویکس پولی ہیڈرون کے عمودی اور کناروں کے سیٹ کے طور پر پیش کیا جا سکتا ہے ؛ یعنی یہ ایک پولی ہیڈرل گراف ہے۔ گراف کا احساس کرنے والے پولی ہیڈرون کا انتخاب اس طرح کیا جا سکتا ہے کہ درخت کے تمام پتوں پر مشتمل چہرہ افقی ہو، اور دیگر تمام چہرے برابر ڈھلوانوں کے ساتھ اس کے اوپر پڑے ہوں۔ ہر پولی ہیڈرل گراف کی طرح ہیلین گراف میں بھی ایک منفرد پلینر ایمبیڈنگ ہوتی ہے، جو اس بات کے انتخاب تک ہوتی ہے کہ اس کے چہروں میں سے کون سا بیرونی چہرہ ہے۔ ہر ہیلن گراف ہیملٹنین گراف ہے، اور گراف کے ہر کنارے کا تعلق ہیملٹنین سائیکل سے ہے۔ مزید برآں، کوئی بھی ہیلن گراف کسی بھی سرے کو ہٹانے کے بعد ہیملٹنین رہتا ہے۔ کیونکہ ڈگری 2 کے عمودی بغیر ہر درخت میں دو پتے ہوتے ہیں جو ایک ہی والدین کا اشتراک کرتے ہیں، ہر ہیلن گراف میں ایک مثلث ہوتا ہے۔ خاص طور پر، ہیلن گراف کے لیے مثلث سے پاک گراف اور نہ ہی دو طرفہ گراف ہونا ممکن نہیں ہے۔ زیادہ مضبوطی سے، ہر ہیلن گراف تقریبا پینسیکلک ہوتا ہے، اس معنی میں کہ اس میں 3 سے n تک کی تمام لمبائی کے چکر ہوتے ہیں جس میں ایک واحد لمبائی کی ممکنہ رعایت ہوتی ہے۔ مزید برآں، کوئی بھی ہیلن گراف تقریبا پینسیکلک رہتا ہے اگر ایک کنارے کو سکڑا جاتا ہے، اور ہر ہیلن گراف جس میں ڈگری تین کے اندرونی عمودی حصے نہیں ہوتے ہیں، پینسیکلک ہوتا ہے۔ زیادہ سے زیادہ ڈگری چار سے زیادہ کے ساتھ ہیلن گراف کا واقع کرومیٹک نمبر ہے۔ یہ تمام جوڑوں (v، e) کو رنگنے کے لیے درکار رنگوں کی تعداد ہے جہاں v گراف کا ایک ورٹیکس ہے، اور e v کے لیے ایک ایج انسیٹنٹ ہے، جو رنگ پر کچھ رکاوٹوں کی پابندی کرتا ہے۔ جوڑے جو ایک سرے کا اشتراک کرتے ہیں یا جو ایک کنارے کا اشتراک کرتے ہیں انہیں ایک ہی رنگ کی اجازت نہیں ہے۔ اس کے علاوہ، ایک جوڑے (v، e) کا رنگ دوسرے جوڑے جیسا نہیں ہو سکتا جو e کے دوسرے اختتامی نقطہ کو استعمال کرتا ہے۔ یا کے ساتھ ہالین گراف کے لیے، واقع کرومیٹک نمبر بالترتیب اتنا ہی بڑا ہو سکتا ہے۔ کمپیوٹیشنل پیچیدگی یہ جانچنا ممکن ہے کہ آیا دیا گیا-ورٹیکس گراف لکیری وقت میں ہیلن گراف ہے، گراف کی پلانر ایمبیڈنگ تلاش کرکے (اگر کوئی موجود ہے)، اور پھر یہ جانچ کر کے کہ آیا کوئی ایسا چہرہ موجود ہے جس میں کم از کم عمودی، تمام ڈگری تین ہیں۔ اگر ایسا ہے تو، زیادہ سے زیادہ چار ایسے چہرے ہو سکتے ہیں، اور ان میں سے ہر ایک کے لیے لکیری وقت میں جانچ کرنا ممکن ہے کہ آیا باقی گراف ایک درخت بناتا ہے جس کے چہرے کے عمودی حصے اس کے پتے کے طور پر ہیں۔ دوسری طرف، اگر ایسا کوئی چہرہ موجود نہیں ہے، تو گراف ہیلن نہیں ہے۔ متبادل طور پر، عمودی اور کناروں والا گراف ہالین ہوتا ہے اگر اور صرف اس صورت میں جب یہ ہموار ہو، 3 سے جڑا ہو، اور اس کا چہرہ ہو جس کے عمودی حصوں کی تعداد گراف کے سرکٹ رینک کے برابر ہو، ان سب کو لکیری وقت میں چیک کیا جا سکتا ہے۔ لکیری ٹائم میں ہیلن گراف کو پہچاننے کے دیگر طریقوں میں کورسل کے تھیوریم کا اطلاق، یا گراف کی دوبارہ تحریر پر مبنی طریقہ شامل ہے، جن میں سے کوئی بھی گراف کی پلینر ایمبیڈنگ کو جاننے پر انحصار نہیں کرتا ہے۔ ہر ہیلن گراف کی تین چوڑائی = 3 ہوتی ہے۔ لہذا، گراف کی اصلاح کے بہت سے مسائل جو صوابدیدی پلانر گراف کے لیے این پی مکمل ہیں، جیسے کہ زیادہ سے زیادہ آزاد سیٹ تلاش کرنا، متحرک پروگرامنگ یا کورسل کے نظریہ کا استعمال کرتے ہوئے ہیلن گراف پر لکیری وقت میں حل کیا جا سکتا ہے، یا کچھ معاملات میں (جیسے ہیملٹنین سائیکلوں کی تعمیر) براہ راست الگورتھم کے ذریعے۔ تاہم، کسی دیئے گئے گراف کا سب سے بڑا ہیلن ذیلی گراف تلاش کرنا، یہ جانچنے کے لیے کہ آیا کوئی ہیلن ذیلی گراف موجود ہے جس میں دیئے گئے گراف کے تمام عمودی حصے شامل ہیں، یا یہ جانچنے کے لیے کہ آیا دیا گیا گراف کسی بڑے ہیلن گراف کا ذیلی گراف ہے، این پی مکمل ہے۔ 1971 میں، ہیلن نے ہیلن گراف کو کم سے کم 3-ورٹیکس سے منسلک گراف کی کلاس کے طور پر متعارف کرایا: گراف کے ہر کنارے کے لیے، اس کنارے کو ہٹانے سے گراف کا رابطہ کم ہو جاتا ہے۔ ان گرافوں نے اس دریافت کے ساتھ اہمیت حاصل کی کہ بہت سے الگورتھمک مسائل جو صوابدیدی پلانر گرافوں کے لیے کمپیوٹیشنل طور پر ناقابل عمل تھے، ان پر مؤثر طریقے سے حل کیے جا سکتے ہیں۔ اس حقیقت کو بعد میں ان کی کم تین چوڑائی، اور کورسل کے نظریہ جیسے الگورتھمک میٹا تھیوریمز کا نتیجہ قرار دیا گیا جو کم تین چوڑائی کے کسی بھی گراف پر ان مسائل کا موثر حل فراہم کرتے ہیں۔ ان گرافوں پر ہیلن کے کام سے پہلے، کیوبک (یا 3-باقاعدہ) ہیلن گراف سے متعلق گراف گنتی کے مسائل کا مطالعہ تھامس کرکمین نے 1856 میں اور ہنس ریڈماچر نے 1965 میں کیا تھا۔ ریڈماچر ان گرافوں کو پولی ہیڈرا کہتے ہیں۔ وہ ان کی وضاحت کیوبک پولی ہیڈرل گراف کے طور پر کرتا ہے جس میں چہرے ہوتے ہیں جن میں سے ایک چہرے کے اطراف ہوتے ہیں۔ اس تعریف سے مطابقت رکھنے والے گراف بالکل کیوبک ہیلن گراف ہیں۔ اس حقیقت سے متاثر ہو کر کہ ہالین گراف اور 4-ورٹیکس سے منسلک پلانر گراف دونوں ہیملٹنین سائیکلوں پر مشتمل ہیں، یہ قیاس کیا گیا کہ ہر 4-ورٹیکس سے منسلک پلانر گراف میں ایک پھیلا ہوا ہالین سب گراف ہوتا ہے۔ یہاں "اسپاننگ" کا مطلب ہے کہ سب گراف میں بڑے گراف کے تمام عمودی حصے شامل ہیں۔ لووز-پلمر قیاس 2015 تک کھلا رہا، جب لامحدود بہت سے جوابی مثالوں کی تعمیر شائع ہوئی۔ ہیلن گراف کو بعض اوقات اسکرٹڈ ٹری یا بغیر چھت والی پولی ہیڈرا بھی کہا جاتا ہے۔ تاہم، یہ نام مبہم ہیں۔ کچھ مصنفین پتوں کو ایک چکر میں جوڑ کر درختوں سے بنے پلانر گراف کا حوالہ دینے کے لیے "اسکرٹڈ ٹریز" کا نام استعمال کرتے ہیں، لیکن اس بات کی ضرورت کے بغیر کہ درخت کے اندرونی عمودی حصوں میں ڈگری تین یا اس سے زیادہ ہو۔ اور "بیسڈ پولی ہیڈرا" کی طرح، "روف لیس پولی ہیڈرا" نام بھی کیوبک ہیلن گراف کا حوالہ دے سکتا ہے۔ کنویکس پولی ہیڈرا جن کے گراف ہیلن گراف ہوتے ہیں انہیں بھی گنبد کہا جاتا ہے۔ حوالہ جات بیرونی روابط ہیلن گراف، گراف کلاس کی شمولیت پر انفارمیشن سسٹم۔ گراف فیملی پلانر گراف