Thrackle
تھریکل ہوائی جہاز میں گراف کا ایک سرایت ہے جس میں ہر کنارے اردن آرک ہوتا ہے اور کناروں کا ہر جوڑا بالکل ایک بار ملتا ہے۔ کنارے یا تو ایک مشترکہ اختتامی نقطہ پر مل سکتے ہیں، یا، اگر ان میں کوئی مشترکہ اختتامی نقطہ نہیں ہے، تو ان کے اندرونی حصے میں ایک نقطہ پر۔ مؤخر الذکر صورت میں، انہیں اپنے چوراہے کے مقام پر عبور کرنا ہوگا: چوراہے کو متصل ہونا چاہیے۔ لکیری تھریکل ایک تھریکل ہے جو اس طرح کھینچا جاتا ہے کہ اس کے کنارے سیدھی لکیر کے حصے ہوتے ہیں۔ جیسا کہ پال ایرڈس نے مشاہدہ کیا، ہر لکیری تھریکل میں زیادہ سے زیادہ اتنے ہی کنارے ہوتے ہیں جتنے کہ عمودی ہوتے ہیں۔ اگر ایک ورٹیکس v تین یا زیادہ کناروں vw، vx، اور vy سے جڑا ہوا ہے، تو ان کناروں میں سے کم از کم ایک (جیسے vw) ایک ایسی لکیر پر واقع ہے جو دو دوسرے کناروں کو الگ کرتی ہے۔ پھر، ڈبلیو کی ڈگری ون ہونی چاہیے، کیونکہ ڈبلیو پر ختم ہونے والا کوئی بھی لائن سیگمنٹ، وی ڈبلیو کے علاوہ، وی ایکس اور وی وائی دونوں کو چھو نہیں سکتا۔ ڈبلیو اور وی ڈبلیو کو ہٹانے سے کناروں اور عمودی حصوں کی تعداد کے درمیان فرق کو تبدیل کیے بغیر ایک چھوٹا تھریکل پیدا ہوتا ہے۔ اس طرح ہٹانے کے بعد ایک تھریکل کی طرف لے جاتا ہے جس میں ہر سرے کے زیادہ سے زیادہ دو پڑوسی ہوتے ہیں، ہاتھ ملانے والے لیما کے ذریعہ کناروں کی تعداد زیادہ سے زیادہ سرے کی تعداد ہوتی ہے۔ ایرڈس کے ثبوت کی بنیاد پر، کوئی یہ اندازہ لگا سکتا ہے کہ ہر لکیری تھراکل ایک فرضی جنگل ہے۔ عجیب لمبائی کے ہر چکر کو لکیری تھریکل بنانے کے لیے ترتیب دیا جا سکتا ہے، لیکن یہ ایک یکساں لمبائی والے چکر کے لیے ممکن نہیں ہے، کیونکہ اگر سائیکل کے ایک کنارے کو من مانی طور پر منتخب کیا جاتا ہے تو دوسرے سائیکل کے عمودی حصوں کو اس کنارے کے ذریعے لائن کے مخالف اطراف میں باری باری ہونا چاہیے۔ مائیکا پیرلز نے ایک اور آسان ثبوت فراہم کیا کہ لکیری تھریکلز کے زیادہ سے زیادہ n کنارے ہوتے ہیں، اس حقیقت کی بنیاد پر کہ لکیری تھریکل میں ہر کنارے کا ایک اختتامی نقطہ ہوتا ہے جس پر کنارے زیادہ سے زیادہ 180 ڈگری کے زاویے پر پھیلے ہوتے ہیں، اور جس کے لیے یہ اس مدت کے اندر سب سے زیادہ گھڑی کی سمت کا کنارے ہوتا ہے۔ کیونکہ، اگر نہیں، تو دو کنارے ہوں گے، جو کنارے کے مخالف اختتامی نکات پر واقع ہوں گے اور کنارے کے ذریعے لکیر کے مخالف اطراف میں پڑے ہوں گے، جو ایک دوسرے کو عبور نہیں کر سکتے تھے۔ لیکن ہر ورٹیکس میں صرف ایک کنارے کے حوالے سے یہ خاصیت ہو سکتی ہے، اس لیے کناروں کی تعداد زیادہ سے زیادہ عمودی کی تعداد کے برابر ہوتی ہے۔ جیسا کہ ایردوس نے بھی مشاہدہ کیا، ایک پوائنٹ سیٹ کے قطر کا احساس کرنے والے پوائنٹس کے جوڑوں کے سیٹ کو ایک لکیری تھریکل بنانا چاہیے: کوئی بھی دو قطر ایک دوسرے سے جدا نہیں ہو سکتے، کیونکہ اگر وہ ہوتے تو ان کے چار اختتامی نکات کا جوڑا دو جداگانہ کناروں سے زیادہ فاصلے پر ہوتا۔ اس وجہ سے، ہوائی جہاز میں n پوائنٹس کے ہر سیٹ میں زیادہ سے زیادہ n قطر والے جوڑے ہو سکتے ہیں، جو 1934 میں ہینز ہاپف اور ایرکا پنوٹز کے ذریعہ پوچھے گئے سوال کا جواب دیتے ہیں۔ اینڈریو ویزسونی نے اعلی جہتوں میں قطر کے جوڑوں کی تعداد پر حدود کا قیاس کیا، اس مسئلے کو عام کیا۔ کمپیوٹیشنل جیومیٹری میں، گھومنے والے کیلیپرز کا طریقہ کنویکس پوزیشن میں پوائنٹس کے کسی بھی سیٹ سے لکیری تھریکل بنانے کے لیے استعمال کیا جا سکتا ہے، ان پوائنٹس کے جوڑوں کو جوڑ کر جو پوائنٹس کے کنویکس ہل کے متوازی لائنوں کو سپورٹ کرتے ہیں۔ اس گراف میں ذیلی گراف کے طور پر قطر کے جوڑوں کا تھریکل ہوتا ہے۔ رین ہارٹ کثیر الاضحی کے قطر لکیری تھریکلز بناتے ہیں۔ لکیری تھریکلز کی گنتی کو سب سے بڑے چھوٹے کثیر الاضحی مسئلے کو حل کرنے کے لیے استعمال کیا جا سکتا ہے، اس کے قطر کے مقابلے میں زیادہ سے زیادہ رقبے والے این-گون کو تلاش کرنے کے لیے۔ تھریکل قیاس جان ایچ کونوے نے قیاس کیا کہ، کسی بھی تھریکل میں، کناروں کی تعداد زیادہ سے زیادہ عمودی تعداد کے برابر ہوتی ہے۔ کونوے نے خود اصطلاحات کے راستے اور دھبے (بالترتیب کناروں اور عمودی حصوں کے لیے) استعمال کیے، اس لیے کونوے کا تھریکل قیاس اصل میں اس شکل میں بیان کیا گیا تھا کہ ہر تھریکل میں کم از کم اتنے ہی دھبے ہوتے ہیں جتنے راستے ہوتے ہیں۔ کونوے نے انعام کے مسائل کے ایک حصے کے طور پر، اس قیاس کو ثابت کرنے یا غلط ثابت کرنے کے لیے $1000 کا انعام پیش کیا، جس میں کونوے کا 99 گراف کا مسئلہ، ڈینزر سیٹوں کا کم از کم فاصلہ، اور حرکت 16 کے بعد سلور سکےج کا فاتح بھی شامل ہے۔ اسی طرح، تھراکل قیاس کو اس طرح بیان کیا جا سکتا ہے کہ ہر تھراکل ایک فرضی جنگل ہے۔ مزید خاص طور پر، اگر تھریکل قیاس درست ہے، تو تھریکلز کو بالکل ووڈال کے نتیجے سے نمایاں کیا جا سکتا ہے: وہ فرضی جنگلات ہیں جن میں لمبائی چار کا کوئی چکر نہیں ہوتا ہے اور زیادہ سے زیادہ ایک عجیب چکر ہوتا ہے۔ یہ ثابت ہو چکا ہے کہ C4 کے علاوہ ہر سائیکل گراف میں تھریکل ایمبیڈنگ ہوتی ہے، جس سے پتہ چلتا ہے کہ قیاس تیز ہے۔ یعنی ایسے تھریکلز ہوتے ہیں جن میں راستوں کے برابر مقامات ہوتے ہیں۔ دوسری انتہا پر، بدترین صورت حال یہ ہے کہ مقامات کی تعداد راستوں کی تعداد سے دوگنی ہے ؛ یہ بھی قابل حصول ہے۔ تھریکل قیاس اس طرح سے کھینچے گئے تھریکلز کے لیے درست جانا جاتا ہے کہ ہر کنارے ایک ایکس مونوٹون وکر ہے، جسے ہر عمودی لکیر سے زیادہ سے زیادہ ایک بار عبور کیا جاتا ہے۔ معروف حدود نے ثابت کیا کہ ہر دو طرفہ تھریکل ایک پلانر گراف ہے، حالانکہ پلانر انداز میں نہیں کھینچا گیا ہے۔ نتیجے کے طور پر، وہ ظاہر کرتے ہیں کہ n عمودی کے ساتھ ہر تھریکل ایبل گراف میں زیادہ سے زیادہ 2n−3 کنارے ہوتے ہیں۔ اس کے بعد سے اس حد کو کئی بار بہتر بنایا گیا ہے۔ سب سے پہلے، اسے 3 (n−1)/2 تک بہتر بنایا گیا، اور ایک اور بہتری تقریبا 1.428n کی حد تک پہنچ گئی۔ مزید برآں، مؤخر الذکر نتیجہ کو ثابت کرنے کے لیے استعمال ہونے والا طریقہ کسی بھی ε> 0 کے لیے ایک محدود الگورتھم حاصل کرتا ہے جو یا تو (1 + ε) n کے پابند کو بہتر بناتا ہے یا قیاس کو غلط ثابت کرتا ہے۔ موجودہ ریکارڈ کی وجہ سے ہے، جس نے 1.3984n کا پابند ثابت کیا۔ اگر قیاس غلط ہے، تو ایک کم سے کم جوابی مثال میں دو یکساں چکروں کی شکل ہوگی جو ایک سرے کا اشتراک کرتی ہیں۔ لہذا، قیاس آرائی کو ثابت کرنے کے لیے، یہ ثابت کرنا کافی ہوگا کہ اس قسم کے گراف کو تھریکل کے طور پر نہیں کھینچا جا سکتا۔ حوالہ جات بیرونی لنکس thrackle.org-مسئلہ کے بارے میں ویب سائٹ قیاس آرائی ٹپوولوجیکل گراف تھیوری ہندسی چوراہا