Circle graph
گراف تھیوری میں، ایک سرکل گراف ایک کورڈ خاکہ کا انٹرسیکشن گراف ہے۔ یعنی یہ ایک غیر ہدایت شدہ گراف ہے جس کے عمودی حصوں کو دائرے کے تاروں کے ایک محدود نظام کے ساتھ اس طرح منسلک کیا جا سکتا ہے کہ دو عمودی حصے ملحقہ ہوں اگر اور صرف اس صورت میں جب متعلقہ تار ایک دوسرے کو عبور کریں۔ الگورتھمک پیچیدگی ایک O (n2) ٹائم الگورتھم دیتی ہے جو اس بات کی جانچ کرتی ہے کہ آیا دیا گیا n-ورٹیکس غیر ہدایت شدہ گراف ایک دائرے کا گراف ہے اور، اگر ایسا ہے تو، اس کی نمائندگی کرنے والے کورڈز کا ایک مجموعہ تشکیل دیتا ہے۔ عام گرافوں پر این پی مکمل ہونے والے متعدد دیگر مسائل میں کثیر الجہتی وقت کے الگورتھم ہوتے ہیں جب وہ دائرے کے گراف تک محدود ہوتے ہیں۔ مثال کے طور پر، دکھایا گیا ہے کہ دائرے کے گراف کی تین چوڑائی کا تعین کیا جا سکتا ہے، اور O (n3) وقت میں درخت کی زیادہ سے زیادہ سڑن کی تعمیر کی جا سکتی ہے۔ مزید برآں، کم از کم فل ان (یعنی، ایک کورڈل گراف جس میں زیادہ سے زیادہ کم کناروں کے ساتھ دیا گیا دائرہ گراف ذیلی گراف کے طور پر موجود ہو) O (n3) وقت میں پایا جا سکتا ہے۔ اس نے دکھایا ہے کہ دائرے کے گراف کا زیادہ سے زیادہ گروہ O (n log2n) وقت میں پایا جا سکتا ہے، جبکہ یہ دکھایا ہے کہ غیر وزنی دائرے کے گراف کا زیادہ سے زیادہ آزاد سیٹ O (n منٹ {d, α}) وقت میں پایا جا سکتا ہے، جہاں d گراف کا ایک پیرامیٹر ہے جسے اس کی کثافت کہا جاتا ہے، اور α دائرے کے گراف کا آزادی نمبر ہے۔ تاہم، ایسے مسائل بھی ہیں جو دائرے کے گراف تک محدود ہونے پر این پی مکمل رہتے ہیں۔ ان میں کم از کم ڈومینیٹنگ سیٹ، کم از کم منسلک ڈومینیٹنگ سیٹ، اور کم از کم کل ڈومینیٹنگ سیٹ کے مسائل شامل ہیں۔ کرومیٹک نمبر دائرے کے گراف کا کرومیٹک نمبر رنگوں کی کم از کم تعداد ہے جو اس کے کورڈز کو رنگنے کے لیے استعمال کیا جا سکتا ہے تاکہ کسی بھی دو کراسنگ کورڈز کا رنگ ایک جیسا نہ ہو۔ چونکہ سرکل گراف بنانا ممکن ہے جس میں صوابدیدی طور پر کورڈز کے بڑے سیٹ ایک دوسرے کو عبور کرتے ہیں، اس لیے سرکل گراف کا کرومیٹک نمبر صوابدیدی طور پر بڑا ہو سکتا ہے، اور سرکل گراف کے کرومیٹک نمبر کا تعین این پی مکمل ہوتا ہے۔ یہ جانچنے کے لیے NP مکمل رہتا ہے کہ آیا دائرے کے گراف کو چار رنگوں سے رنگا جا سکتا ہے۔ انہوں نے دعوی کیا کہ تین رنگوں کے ساتھ رنگ تلاش کرنا کثیر الجہتی وقت میں کیا جا سکتا ہے لیکن اس کے نتیجے کی تحریر میں بہت سی تفصیلات کو چھوڑ دیا گیا ہے۔ کئی مصنفین نے چند رنگوں کے ساتھ دائرے کے گراف کے محدود ذیلی طبقات کو رنگنے کے مسائل کی تحقیقات کی ہیں۔ خاص طور پر، دائرے کے گرافوں کے لیے جن میں k یا اس سے زیادہ کورڈز کا کوئی سیٹ ایک دوسرے کو پار نہیں کرتا ہے، گراف کو اتنے ہی کم رنگوں سے رنگنا ممکن ہے۔ یہ بتانے کا ایک طریقہ یہ ہے کہ دائرے کے گراف-باؤنڈ ہیں۔ خاص صورت میں جب k = 3 (یعنی مثلث سے پاک دائرے کے گراف کے لیے) کرومیٹک نمبر زیادہ سے زیادہ پانچ ہوتا ہے، اور یہ تنگ ہوتا ہے: تمام مثلث سے پاک دائرے کے گراف پانچ رنگوں سے رنگین ہو سکتے ہیں، اور مثلث سے پاک دائرے کے گراف موجود ہوتے ہیں جن کے لیے پانچ رنگوں کی ضرورت ہوتی ہے۔ اگر کسی دائرے کے گراف کا دائرہ کم از کم پانچ ہے (یعنی یہ مثلث سے پاک ہے اور اس میں چار ورٹیکس سائیکل نہیں ہیں) تو اسے زیادہ سے زیادہ تین رنگوں سے رنگا جا سکتا ہے۔ مثلث سے پاک مربع گراف کو رنگنے کا مسئلہ مربع گراف کو درختوں کے کارٹیشین مصنوعات کے آئسومیٹرک ذیلی گراف کے طور پر پیش کرنے کے مسئلے کے مساوی ہے۔ اس خط و کتابت میں، رنگ میں رنگوں کی تعداد مصنوعات کی نمائندگی میں درختوں کی تعداد سے مطابقت رکھتی ہے۔ ایپلی کیشنز سرکل گراف وی ایل ایس آئی فزیکل ڈیزائن میں تار روٹنگ کے لیے ایک خاص کیس کے لیے ایک تجریدی نمائندگی کے طور پر پیدا ہوتے ہیں، جسے "دو ٹرمینل سوئچ باکس روٹنگ" کہا جاتا ہے۔ اس صورت میں روٹنگ ایریا ایک آئتاکار ہے، تمام جال دو ٹرمینل ہیں، اور ٹرمینلز کو آئتاکار کے دائرے پر رکھا جاتا ہے۔ یہ آسانی سے دیکھا جا سکتا ہے کہ ان جالوں کا انٹرسیکشن گراف ایک سرکل گراف ہے۔ تار روٹنگ مرحلے کے اہداف میں یہ یقینی بنانا ہے کہ مختلف جال برقی طور پر منقطع رہیں، اور ان کے ممکنہ انٹرسیکٹنگ حصوں کو مختلف کنڈکٹنگ تہوں میں رکھا جانا چاہیے۔ لہذا سرکل گراف اس روٹنگ کے مسئلے کے مختلف پہلوؤں پر قبضہ کرتے ہیں۔ دائرے کے گرافوں کے رنگوں کو صوابدیدی گرافوں کی کتاب کے سرایت کو تلاش کرنے کے لیے بھی استعمال کیا جا سکتا ہے: اگر کسی دیئے گئے گراف G کے عمودی حصے ایک دائرے پر ترتیب دیے گئے ہیں، جس میں G کے کناروں سے دائرے کے کورڈز بنتے ہیں، تو ان کورڈز کا انٹرسیکشن گراف ایک دائرے کا گراف ہے اور اس دائرے کے گراف کے رنگ کتاب کے سرایت کے مساوی ہیں جو دیئے گئے سرکلر ترتیب کا احترام کرتے ہیں۔ اس مساوات میں، رنگ میں رنگوں کی تعداد کتاب کے سرایت میں صفحات کی تعداد سے مطابقت رکھتی ہے۔ متعلقہ گراف کلاسیں گراف ایک دائرہ گراف ہے اگر اور صرف اس صورت میں جب یہ کسی لائن پر وقفوں کے سیٹ کا اوورلیپ گراف ہو۔ یہ ایک ایسا گراف ہے جس میں عمودی وقفوں سے مطابقت رکھتے ہیں، اور اگر دو وقفے اوورلیپ ہوتے ہیں تو دو عمودی ایک کنارے سے جڑے ہوتے ہیں، جس میں سے کسی میں بھی دوسرا نہیں ہوتا ہے۔ کسی لکیر پر وقفوں کے ایک سیٹ کے انٹرسیکشن گراف کو وقفہ گراف کہا جاتا ہے۔ سٹرنگ گراف، طیارہ میں منحنی خطوط کے انٹرسیکشن گراف، ایک خاص صورت کے طور پر دائرے کے گراف کو شامل کرتے ہیں۔ ہر فاصلہ-موروثی گراف ایک دائرہ گراف ہے، جیسا کہ ہر تعدد گراف اور ہر بے حسی گراف ہے۔ ہر بیرونی طیارہ گراف بھی ایک دائرہ گراف ہے۔ دائرے کے گراف کو کثیر الاضحی دائرے کے گراف، کثیر الاضحی کے چوراہے کے گراف کے ذریعے عام کیا جاتا ہے، یہ سب ایک ہی دائرے میں کندہ ہوتے ہیں۔ حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ ۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ ۔ ۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ دائرے گراف کی انٹرسیکشن کلاسیں ہندسی گراف