Circuit rank
گراف تھیوری میں، ریاضی کی ایک شاخ، سرکٹ رینک، سائکلومیٹک نمبر، سائیکل رینک، یا کسی غیر ہدایت شدہ گراف کی صفر کناروں کی کم از کم تعداد ہے جسے گراف سے اس کے تمام چکروں کو توڑنے کے لیے ہٹانا ضروری ہے، جس سے یہ درخت یا جنگل بن جاتا ہے۔ یہ گراف میں آزاد چکروں کی تعداد (سائیکل کی بنیاد کا سائز) کے برابر ہے۔ ہدایت شدہ گرافوں کے لیے متعلقہ فیڈ بیک آرک سیٹ کے مسئلے کے برعکس، سرکٹ رینک کا حساب آسانی سے فارمولے کا استعمال کرتے ہوئے کیا جاتا ہے، جہاں دیئے گئے گراف میں کناروں کی تعداد ہے، عمودی حصوں کی تعداد ہے، اور منسلک اجزاء کی تعداد ہے۔ کم سے کم سائز کے کناروں کا مجموعہ بنانا بھی ممکن ہے جو تمام چکروں کو مؤثر طریقے سے توڑ دے، یا تو لالچی الگورتھم کا استعمال کرتے ہوئے یا پھیلے ہوئے جنگل کی تکمیل کرتے ہوئے۔ سرکٹ رینک کو الجبرائی گراف تھیوری کے لحاظ سے گراف کے سائیکل اسپیس کے طول و عرض کے طور پر، میٹرائڈ تھیوری کے لحاظ سے گرافک میٹرائڈ کے کورانک کے طور پر، اور ٹوپولوجی کے لحاظ سے گراف سے اخذ کردہ ٹوپولوجیکل اسپیس کے بیٹی نمبروں میں سے ایک کے طور پر سمجھایا جا سکتا ہے۔ یہ گراف کے کان کے سڑنے میں کانوں کو شمار کرتا ہے، تقریبا درختوں پر پیرامیٹرائزڈ پیچیدگی کی بنیاد بناتا ہے، اور کوڈ کے ٹکڑے کی سائکلومیٹک پیچیدگی کی تعریف کے حصے کے طور پر سافٹ ویئر میٹرکس میں لاگو کیا گیا ہے۔ سائکلومیٹک نمبر کے نام سے یہ تصور گستاو کرچوف نے متعارف کرایا تھا۔ میٹرائڈ رینک اور کم از کم فیڈ بیک ایج سیٹ کی تعمیر گراف کے سرکٹ رینک کو میٹرائڈ تھیوری کا استعمال کرتے ہوئے میٹرائڈ کے گرافک میٹرائڈ کے کورانک کے طور پر بیان کیا جا سکتا ہے۔ میٹروئڈز کی لالچی خاصیت کا استعمال کرتے ہوئے، اس کا مطلب یہ ہے کہ کوئی بھی ایسے کناروں کا کم از کم مجموعہ تلاش کر سکتا ہے جو لالچی الگورتھم کا استعمال کرتے ہوئے تمام چکروں کو توڑ دیتا ہے جو ہر مرحلے پر ایک ایسے کنارے کا انتخاب کرتا ہے جس کا تعلق باقی گراف کے کم از کم ایک چکر سے ہو۔ متبادل طور پر، کناروں کا ایک کم از کم مجموعہ جو تمام چکروں کو توڑتا ہے، ایک پھیلا ہوا جنگل بنا کر اور کناروں کے تکمیلی سیٹ کا انتخاب کرکے پایا جا سکتا ہے جن کا تعلق پھیلے ہوئے جنگل سے نہیں ہے۔ آزاد چکروں کی تعداد الجبرائی گراف تھیوری میں، سرکٹ کا درجہ بھی سائیکل کی جگہ کا طول و عرض ہے۔ بدیہی طور پر، اس کی وضاحت اس معنی کے طور پر کی جا سکتی ہے کہ سرکٹ رینک گراف میں آزاد چکروں کی تعداد کو شمار کرتا ہے، جہاں چکروں کا مجموعہ آزاد ہوتا ہے اگر یہ ممکن نہ ہو کہ چکروں میں سے کسی ایک کو دوسروں کے کچھ ذیلی سیٹ کے متناسب فرق کے طور پر تشکیل دیا جائے۔ آزاد چکروں کی اس گنتی کو ہومولوجی تھیوری کا استعمال کرتے ہوئے بھی سمجھایا جا سکتا ہے، جو ٹوپولوجی کی ایک شاخ ہے۔ کسی بھی گراف کو 1 جہتی سادہ کمپلیکس کی مثال کے طور پر دیکھا جا سکتا ہے، ایک قسم کی ٹوپوولوجیکل اسپیس جو ہر گراف کے کنارے کو لائن کے حصے سے ظاہر کرتی ہے اور ان لائن کے حصوں کو ان کے اختتامی نکات پر ایک ساتھ جوڑتی ہے۔ سائکلومیٹک نمبر اس کمپلیکس کے پہلے (انٹیجر) ہومیولوجی گروپ کا درجہ ہے، اس ٹپوولوجیکل کنکشن کی وجہ سے، گراف کے سائکلومیٹک نمبر کو اس کا پہلا بیٹی نمبر بھی کہا جاتا ہے۔ زیادہ عام طور پر، کسی بھی ٹپوولوجیکل اسپیس کا پہلا بیٹی نمبر، اسی طرح بیان کیا گیا ہے، خلا میں آزاد چکروں کی تعداد کو شمار کرتا ہے۔ میشیڈنیس گتانک ایپلی کیشنز میشیڈنیس گتانک پلانر گراف کے لیے سرکٹ رینک کا ایک متغیر، جسے ایک ہی ورٹیکس سیٹ کے ساتھ کسی بھی پلانر گراف کے زیادہ سے زیادہ ممکنہ سرکٹ رینک سے تقسیم کرکے معمول بنایا جاتا ہے، کو میشیڈنیس گتانک کہا جاتا ہے۔ کناروں اور عمودی حصوں کے ساتھ جڑے ہوئے پلانر گراف کے لیے، میشڈنیس گتانک کا حساب فارمولے کے ذریعے کیا جا سکتا ہے۔ یہاں، فارمولے کا نیومریٹر دیئے گئے گراف کا سرکٹ رینک ہے، اور ڈینومینیٹر-ورٹیکس پلانر گراف کا سب سے بڑا ممکنہ سرکٹ رینک ہے۔ میشڈنیس گتانک درختوں کے لیے 0 اور زیادہ سے زیادہ طیارہ گراف کے لیے 1 کے درمیان ہوتا ہے۔ کان کا سڑنا سرکٹ کا درجہ گراف کے کان کے سڑنے میں کانوں کی تعداد کو کنٹرول کرتا ہے، گراف کے کناروں کو راستوں اور چکروں میں تقسیم کرنا جو بہت سے گراف الگورتھم میں مفید ہے۔ خاص طور پر، ایک گراف 2-ورٹیکس سے منسلک ہوتا ہے اگر اور صرف اس صورت میں جب اس میں کھلے کان کا سڑنا ہو۔ یہ ذیلی گرافوں کا ایک سلسلہ ہے، جہاں پہلا ذیلی گراف ایک سادہ سائیکل ہے، باقی ذیلی گراف تمام سادہ راستے ہیں، ہر راستہ ان عمودی حصوں پر شروع ہوتا ہے اور ختم ہوتا ہے جو پچھلے ذیلی گرافوں سے تعلق رکھتے ہیں، اور کسی راستے کا ہر اندرونی ورٹیکس اس راستے میں پہلی بار ظاہر ہوتا ہے۔ سرکٹ رینک کے ساتھ کسی بھی دو جڑے ہوئے گراف میں، ہر کھلے کان کے سڑنے کے بالکل کان ہوتے ہیں۔ تقریبا درخت سائکلومیٹک نمبر والے گراف کو r-قریب ترین درخت بھی کہا جاتا ہے، کیونکہ اسے درخت یا جنگل میں تبدیل کرنے کے لیے گراف سے صرف r کناروں کو ہٹانے کی ضرورت ہوتی ہے۔ ایک قریب ترین درخت ایک قریب ترین درخت ہے: ایک جڑا ہوا قریب کا درخت ایک فرضی درخت ہے، ایک چکر جس میں (ممکنہ طور پر معمولی) درخت ہر سرے پر جڑا ہوا ہے۔ کئی مصنفین نے آر-قریب درختوں پر گراف الگورتھم کی پیرامیٹرائزڈ پیچیدگی کا مطالعہ کیا ہے، جس کے ذریعہ پیرامیٹرائز کیا گیا ہے۔ ڈائریکٹڈ گرافوں میں عمومییاں سائیکل رینک ڈائریکٹڈ گرافوں کا ایک غیر متغیر ہے جو گراف میں سائیکلوں کے گھونسلوں کی سطح کی پیمائش کرتا ہے۔ اس کی تعریف سرکٹ رینک سے زیادہ پیچیدہ ہے (غیر ہدایت شدہ گراف کے لیے درخت کی گہرائی کی تعریف سے قریب سے متعلق) اور اس کا حساب لگانا زیادہ مشکل ہے۔ سرکٹ رینک سے متعلق ڈائریکٹڈ گراف کے لیے ایک اور مسئلہ کم از کم فیڈ بیک آرک سیٹ ہے، کناروں کا سب سے چھوٹا سیٹ جس کا ہٹانا تمام ڈائریکٹڈ سائیکلوں کو توڑ دیتا ہے۔ سائیکل رینک اور کم از کم فیڈ بیک آرک سیٹ دونوں کا حساب لگانا NP-مشکل ہے۔ کناروں کی سمتوں کو نظر انداز کرکے اور بنیادی غیر ہدایت شدہ گراف کے سرکٹ رینک کا حساب لگا کر ہدایت شدہ گراف کے ایک آسان غیر متغیر کا حساب لگانا بھی ممکن ہے۔ یہ اصول سائکلومیٹک پیچیدگی کی تعریف کی بنیاد بناتا ہے، یہ اندازہ لگانے کے لیے کہ کمپیوٹر کوڈ کا ایک ٹکڑا کتنا پیچیدہ ہے، ایک سافٹ ویئر میٹرک ہے۔ کمپیوٹیشنل کیمسٹری کیمسٹری اور کیمینفارمیٹکس کے شعبوں میں، سالماتی گراف کے سرکٹ رینک (سب سے چھوٹے رنگوں کے سب سے چھوٹے سیٹ میں رنگوں کی تعداد) کو بعض اوقات فریریجاک نمبر کہا جاتا ہے۔ پیرامیٹرائزڈ پیچیدگی گراف پر کچھ کمپیوٹیشنل مسائل عام طور پر این پی سخت ہوتے ہیں، لیکن چھوٹے سرکٹ رینک والے گراف کے لیے کثیر الجہتی وقت میں حل کیے جا سکتے ہیں۔ ایک مثال راستے کی تشکیل نو کا مسئلہ ہے۔ متعلقہ تصورات گراف سے چیزوں کو حذف کرنے کے لحاظ سے بیان کردہ دیگر اعداد یہ ہیں: ایج کنیکٹوٹی-گراف کو منقطع کرنے کے لیے حذف کرنے کے لیے کناروں کی کم از کم تعداد ؛ میچنگ پریکلیوژن-کامل مماثلت کے وجود کو روکنے کے لیے حذف کرنے کے لیے کناروں کی کم از کم تعداد ؛ فیڈ بیک ورٹیکس سیٹ نمبر-گراف کو ایسائکلک بنانے کے لیے حذف کرنے کے لیے عمودی حصوں کی کم از کم تعداد ؛ فیڈ بیک آرک سیٹ-ہدایت شدہ گراف سے حذف کرنے کے لیے آرکس کی کم از کم تعداد، تاکہ اسے ایسائکلک بنایا جا سکے۔ حوالہ جات گراف غیر متغیر میٹرائڈ تھیوری اسپاننگ ٹری