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