Cactus graph
گراف تھیوری میں، کیکٹس (جسے بعض اوقات کیکٹس ٹری کہا جاتا ہے) ایک جڑا ہوا گراف ہے جس میں کسی بھی دو سادہ چکروں میں زیادہ سے زیادہ ایک ورٹیکس مشترک ہوتا ہے۔ مساوی طور پر، یہ ایک منسلک گراف ہے جس میں ہر کنارے کا تعلق زیادہ سے زیادہ ایک سادہ سائیکل سے ہے، یا (غیر معمولی کیکٹی کے لیے) جس میں ہر بلاک (کٹ ورٹیکس کے بغیر زیادہ سے زیادہ ذیلی گراف) ایک کنارے یا سائیکل ہے۔ کیکٹی کی خصوصیات بیرونی طیارہ گراف ہیں۔ ہر سڈوٹری ایک کیکٹس ہے۔ ایک غیر معمولی گراف ایک کیکٹس ہے اگر اور صرف اس صورت میں جب ہر بلاک یا تو ایک سادہ سائیکل یا ایک کنارے ہو۔ گراف کا وہ خاندان جس میں ہر جزو ایک کیکٹس ہے، گراف معمولی کارروائیوں کے تحت نیچے کی طرف بند ہوتا ہے۔ اس گراف خاندان کی خصوصیت ایک واحد ممنوعہ معمولی، چار ورٹیکس ہیرے کا گراف ہو سکتا ہے جو مکمل گراف K4 سے ایک کنارے کو ہٹا کر بنایا گیا ہو۔ مثلث کیکٹس ایک مثلث کیکٹس ایک خاص قسم کا کیکٹس گراف ہے جس میں ہر سائیکل کی لمبائی تین ہوتی ہے اور ہر کنارے کا تعلق ایک سائیکل سے ہوتا ہے۔ مثال کے طور پر، دوستی کے گراف، مثلث کے مجموعے سے بنے گراف جو ایک مشترکہ سرے پر ایک ساتھ جڑے ہوئے ہیں، سہ رخی کیکٹی ہیں۔ کیکٹس گراف ہونے کے ساتھ ساتھ مثلث کیکٹس بھی بلاک گراف اور مقامی طور پر لکیری گراف ہوتے ہیں۔ سہ رخی کیکٹس کی خاصیت یہ ہے کہ اگر ان سے کوئی مماثلت ہٹا دی جاتی ہے تو وہ جڑے رہتے ہیں۔ عمودی کی دی گئی تعداد کے لیے، ان کے پاس اس خاصیت کے ساتھ کم سے کم ممکنہ کنارے ہوتے ہیں۔ ہر درخت جس کے عمودی حصوں کی ایک عجیب تعداد ہوتی ہے، اس میں کناروں کو شامل کرکے مثلث کیکٹس میں بڑھایا جا سکتا ہے، جس سے ملاپ کو ہٹانے کے بعد جڑے رہنے کی خاصیت کے ساتھ کم سے کم اضافہ ہوتا ہے۔ کسی بھی گراف میں سب سے بڑا سہ رخی کیکٹس میٹرایڈ پیریٹی کے مسئلے کے لیے الگورتھم کا استعمال کرتے ہوئے کثیر الجہتی وقت میں پایا جا سکتا ہے۔ چونکہ مثلث کیکٹس گراف پلانر گراف ہوتے ہیں، اس لیے سب سے بڑے مثلث کیکٹس کو سب سے بڑے پلانر سب گراف کے تخمینے کے طور پر استعمال کیا جا سکتا ہے، جو پلانرائزیشن میں ایک اہم ذیلی مسئلہ ہے۔ ایک تخمینہ الگورتھم کے طور پر، اس طریقہ کار کا تخمینہ تناسب 4/9 ہے، جو زیادہ سے زیادہ پلانر سب گراف کے مسئلے کے لیے مشہور ہے۔ سب سے بڑے مثلث کیکٹس کو تلاش کرنے کا الگورتھم لووز اور پلمر کے ایک نظریہ سے وابستہ ہے جو اس سب سے بڑے کیکٹس میں مثلث کی تعداد کی خصوصیت رکھتا ہے۔ لووسز اور پلمر دیئے گئے گراف کے عمودی حصوں اور کناروں کی تقسیم کے جوڑوں کو ذیلی سیٹوں میں سمجھتے ہیں، اس خاصیت کے ساتھ کہ گراف کے ہر مثلث میں یا تو عمودی تقسیم کے ایک ہی طبقے میں دو عمودی حصے ہوتے ہیں یا کنارے کی تقسیم کے ایک ہی طبقے میں تینوں کنارے ہوتے ہیں۔ وہ اس خاصیت کے ساتھ تقسیم کے جوڑے کو درست کہتے ہیں۔ پھر سب سے بڑے مثلث کیکٹس میں مثلثوں کی تعداد زیادہ سے زیادہ، درست پارٹیشنوں کے جوڑوں کے برابر ہوتی ہے اور، کے، دیئے گئے گراف میں عمودی حصوں کی تعداد کہاں ہے اور ایج کلاس کے ذریعہ ملنے والی عمودی کلاسوں کی تعداد ہے۔ ہر ہوائی جہاز کے گراف میں ایک کیکٹس سب گراف ہوتا ہے جس میں ہوائی جہاز کے مثلث چہروں کا کم از کم حصہ شامل ہوتا ہے۔ اس نتیجے سے 4/9 کا براہ راست تجزیہ ظاہر ہوتا ہے-زیادہ سے زیادہ پلانر سب گراف کے مسئلے کے لیے اوپر دیے گئے کم سے کم فارمولے کا استعمال کیے بغیر تخمینہ الگورتھم۔ روزا کا قیاس مثلث کیکٹس سے متعلق ایک اہم قیاس روزا کا قیاس ہے، جس کا نام الیگزینڈر روزا کے نام پر رکھا گیا ہے، جس میں کہا گیا ہے کہ تمام مثلث کیکٹس خوبصورت یا تقریبا مہربان ہیں۔ مزید واضح طور پر تمام مثلث کیکٹی t ष्ण 0، 1 موڈ 4 بلاکس کے ساتھ خوبصورت ہیں، اور جو t ष्ण 2، 3 موڈ 4 کے ساتھ قریب خوبصورت ہیں۔ الگورتھم اور ایپلی کیشنز سہولت کے مقام کے کچھ مسائل جو عام گراف کے لیے این پی-سخت ہوتے ہیں، نیز گراف کے کچھ دیگر مسائل، کیکٹی کے لیے کثیر الجہتی وقت میں حل کیے جا سکتے ہیں۔ چونکہ کیکٹی بیرونی طیارہ گراف کے خاص معاملات ہیں، اس لیے گراف پر مشترکہ اصلاح کے متعدد مسائل کو ان کے لیے کثیر الجہتی وقت میں حل کیا جا سکتا ہے۔ کیکٹی برقی سرکٹس کی نمائندگی کرتا ہے جن میں مفید خصوصیات ہوتی ہیں۔ کیکٹی کا ابتدائی استعمال اوپی ایمپس کی نمائندگی سے وابستہ تھا۔ کیکٹی کو تقابلی جینومکس میں بھی مختلف جینوموں یا جینوم کے حصوں کے درمیان تعلقات کی نمائندگی کرنے کے طریقے کے طور پر استعمال کیا گیا ہے۔ اگر ایک کیکٹس جڑا ہوا ہے، اور اس کے ہر ایک عمودی حصے کا تعلق زیادہ سے زیادہ دو بلاکس سے ہے، تو اسے کرسمس کیکٹس کہا جاتا ہے۔ ہر پولی ہیڈرل گراف میں کرسمس کیکٹس کا ذیلی گراف ہوتا ہے جس میں اس کے تمام عمودی حصے شامل ہوتے ہیں، یہ ایک ایسی حقیقت ہے جو اس بات کے ثبوت میں ایک اہم کردار ادا کرتی ہے کہ ہر پولی ہیڈرل گراف میں یوکلڈین سطح میں ایک لالچی سرایت ہوتی ہے، جو چوٹیوں کے لیے نقاط کی ایک تفویض ہے جس کے لیے لالچی فارورڈنگ تمام جوڑوں کے عمودی حصوں کے درمیان پیغامات کو منتقل کرنے میں کامیاب ہوتی ہے۔ ٹپوولوجیکل گراف تھیوری میں، وہ گراف جن کے سیلولر ایمبیڈنگز تمام پلینر ہوتے ہیں بالکل کیکٹس گراف کے ذیلی خاندان ہوتے ہیں جس میں اضافی خاصیت ہوتی ہے کہ ہر ورٹیکس کا تعلق زیادہ سے زیادہ ایک سائیکل سے ہوتا ہے۔ ان گرافوں میں دو ممنوع نابالغ ہیں، ڈائمنڈ گراف اور فائیو ورٹیکس فرینڈشپ گراف۔ تاریخ کیکٹی کا مطالعہ سب سے پہلے ہوسیمی درختوں کے نام سے کیا گیا تھا، جو انہیں فرینک ہیری اور جارج یوجین اولن بیک نے ان گرافوں پر کوڈی ہوسیمی کے پچھلے کام کے اعزاز میں دیا تھا۔ اسی ہیری-اہلن بیک کاغذ میں اس قسم کے گرافوں کے لیے "کیکٹس" کا نام محفوظ ہے جس میں ہر چکر ایک مثلث ہے، لیکن اب تمام لمبائی کے چکروں کی اجازت دینا معیاری ہے۔ دریں اثنا، ہوسیمی ٹری کا نام عام طور پر ان گرافوں کے لیے آیا ہے جن میں ہر بلاک ایک مکمل گراف ہے (مساوی طور پر، کسی دوسرے گراف میں بلاکس کے انٹرسیکشن گراف)۔ اس استعمال کا حسیمی کے کام سے کوئی تعلق نہیں تھا، اور اب اس خاندان کے لیے زیادہ مناسب اصطلاح بلاک گراف استعمال کیا جاتا ہے ؛ تاہم، اس ابہام کی وجہ سے یہ فقرہ کیکٹس گراف کا حوالہ دینے کے لیے کم کثرت سے استعمال ہوتا ہے۔ حوالہ جات بیرونی روابط الیکٹرانک سرکٹس کے تجزیہ اور ڈیزائن میں کیکٹس گراف کا اطلاق گراف فیملی پلانر گراف انٹیگریٹڈ سرکٹس