Circuit rank
গ্রাফ তত্ত্বে, গণিতের একটি শাখা, সার্কিট র্যাঙ্ক, সাইক্লোম্যাটিক সংখ্যা, চক্র র্যাঙ্ক, বা একটি অনির্দিষ্ট গ্রাফের শূন্যতা হল ন্যূনতম প্রান্তের সংখ্যা যা গ্রাফ থেকে অপসারণ করতে হবে তার সমস্ত চক্রকে ভেঙে, এটিকে একটি গাছ বা বনে পরিণত করতে। এটি গ্রাফের স্বাধীন চক্রের সংখ্যার (একটি চক্র ভিত্তির আকার) সমান। নির্দেশিত গ্রাফের জন্য সংশ্লিষ্ট ফিডব্যাক আর্ক সেট সমস্যার বিপরীতে, সার্কিট র্যাঙ্কটি সহজেই সূত্রটি ব্যবহার করে গণনা করা হয়, যেখানে প্রদত্ত গ্রাফের প্রান্তের সংখ্যা, শীর্ষগুলির সংখ্যা এবং সংযুক্ত উপাদানগুলির সংখ্যা। লোভী অ্যালগরিদম ব্যবহার করে বা বিস্তৃত বনের পরিপূরক হিসাবে ন্যূনতম আকারের প্রান্তগুলি তৈরি করাও সম্ভব যা সমস্ত চক্রকে দক্ষতার সাথে ভেঙে দেয়। সার্কিট র্যাঙ্ককে বীজগাণিতিক গ্রাফ তত্ত্বের পরিপ্রেক্ষিতে একটি গ্রাফের চক্র স্থানের মাত্রা হিসাবে, ম্যাট্রয়েড তত্ত্বের পরিপ্রেক্ষিতে একটি গ্রাফিক ম্যাট্রয়েডের কোর্যাঙ্ক হিসাবে এবং টপোলজির পরিপ্রেক্ষিতে গ্রাফ থেকে প্রাপ্ত টপোলজিকাল স্থানের বেটি সংখ্যাগুলির মধ্যে একটি হিসাবে ব্যাখ্যা করা যেতে পারে। এটি গ্রাফের একটি কানের পচনে কান গণনা করে, প্রায় গাছের উপর প্যারামিটারাইজড জটিলতার ভিত্তি তৈরি করে এবং কোডের একটি অংশের সাইক্লোম্যাটিক জটিলতার সংজ্ঞার অংশ হিসাবে সফ্টওয়্যার মেট্রিক্সে প্রয়োগ করা হয়েছে। সাইক্লোম্যাটিক নম্বরের নামে, ধারণাটি গুস্তাভ কিরচফ দ্বারা প্রবর্তিত হয়েছিল। ম্যাট্রয়েড র্যাঙ্ক এবং ন্যূনতম প্রতিক্রিয়া প্রান্ত সেটের নির্মাণ ম্যাট্রয়েড তত্ত্ব ব্যবহার করে একটি গ্রাফের সার্কিট র্যাঙ্ককে ম্যাট্রয়েডের গ্রাফিক ম্যাট্রয়েডের কোর্যাঙ্ক হিসাবে বর্ণনা করা যেতে পারে। ম্যাট্রয়েডের লোভী বৈশিষ্ট্য ব্যবহার করে, এর অর্থ হল যে কেউ একটি ন্যূনতম প্রান্তের সেট খুঁজে পেতে পারে যা একটি লোভী অ্যালগরিদম ব্যবহার করে সমস্ত চক্রকে ভেঙে দেয় যা প্রতিটি পদক্ষেপে একটি প্রান্ত বেছে নেয় যা অবশিষ্ট গ্রাফের কমপক্ষে একটি চক্রের অন্তর্গত। বিকল্পভাবে, সমস্ত চক্রকে ভেঙে দেওয়া প্রান্তগুলির একটি ন্যূনতম সেট একটি বিস্তৃত বন তৈরি করে এবং প্রসারিত বনের অন্তর্গত নয় এমন প্রান্তগুলির পরিপূরক সেট বেছে নিয়ে পাওয়া যেতে পারে। স্বাধীন চক্রের সংখ্যা বীজগাণিতিক গ্রাফ তত্ত্বে, সার্কিট র্যাঙ্কটিও এর চক্র স্থানের মাত্রা। স্বজ্ঞাতভাবে, এর অর্থ হিসাবে ব্যাখ্যা করা যেতে পারে যে সার্কিট র্যাঙ্ক গ্রাফের স্বাধীন চক্রের সংখ্যা গণনা করে, যেখানে চক্রের একটি সংগ্রহ স্বাধীন হয় যদি অন্যের কিছু উপসেটের প্রতিসম পার্থক্য হিসাবে একটি চক্র গঠন করা সম্ভব না হয়। স্বাধীন চক্রের এই গণনাটি টপোলজির একটি শাখা হোমোলজি তত্ত্ব ব্যবহার করেও ব্যাখ্যা করা যেতে পারে। যে কোনও গ্রাফকে একটি 1-মাত্রিক সরল জটিলতার উদাহরণ হিসাবে দেখা যেতে পারে, এক ধরনের টপোলজিকাল স্থান যা প্রতিটি গ্রাফের প্রান্তকে একটি রেখা বিভাগ দ্বারা উপস্থাপন করে এবং এই রেখা বিভাগগুলিকে তাদের শেষ বিন্দুতে একত্রিত করে গঠিত হয়। সাইক্লোম্যাটিক সংখ্যা হল এই কমপ্লেক্সের প্রথম (পূর্ণসংখ্যা) সমসংস্থান গোষ্ঠীর র্যাঙ্ক, এই টপোলজিক্যাল সংযোগের কারণে, একটি গ্রাফের সাইক্লোম্যাটিক সংখ্যাকে এর প্রথম বেট্টি সংখ্যাও বলা হয়। আরও সাধারণভাবে, যে কোনও টপোলজিকাল স্থানের প্রথম বেট্টি সংখ্যা, একইভাবে সংজ্ঞায়িত, স্থানটিতে স্বাধীন চক্রের সংখ্যা গণনা করে। প্রয়োগ মেশেডনেস সহগ সমতলীয় গ্রাফের জন্য সার্কিট র্যাঙ্কের একটি বৈকল্পিক, একই শীর্ষ সেট সহ যে কোনও সমতলীয় গ্রাফের সর্বাধিক সম্ভাব্য সার্কিট র্যাঙ্ক দ্বারা ভাগ করে স্বাভাবিক করা হয়, তাকে মেশেডনেস সহগ বলা হয়। প্রান্ত এবং শীর্ষ সহ একটি সংযুক্ত সমতলীয় গ্রাফের জন্য, মেশেডনেস সহগ সূত্র দ্বারা গণনা করা যেতে পারে এখানে, সূত্রের সংখ্যাটি প্রদত্ত গ্রাফের সার্কিট র্যাঙ্ক, এবং হরটি একটি-ভার্টেক্স সমতলীয় গ্রাফের বৃহত্তম সম্ভাব্য সার্কিট র্যাঙ্ক। মেশেডনেস সহগটি গাছের জন্য 0 এবং সর্বাধিক সমতলীয় গ্রাফের জন্য 1 এর মধ্যে থাকে। কানের পচন সার্কিট র্যাঙ্ক একটি গ্রাফের কানের পচনে কানের সংখ্যা নিয়ন্ত্রণ করে, যা গ্রাফের প্রান্তগুলিকে পথ এবং চক্রে বিভক্ত করে যা অনেক গ্রাফ অ্যালগরিদমে কার্যকর। বিশেষ করে, একটি গ্রাফ 2-ভার্টেক্স-সংযুক্ত হয় যদি এবং শুধুমাত্র যদি এটির একটি খোলা কানের পচন থাকে। এটি সাবগ্রাফগুলির একটি ক্রম, যেখানে প্রথম সাবগ্রাফ একটি সহজ চক্র, অবশিষ্ট সাবগ্রাফগুলি সমস্ত সহজ পথ, প্রতিটি পথ পূর্ববর্তী সাবগ্রাফগুলির অন্তর্গত শীর্ষে শুরু হয় এবং শেষ হয় এবং একটি পথের প্রতিটি অভ্যন্তরীণ শীর্ষ সেই পথে প্রথমবারের জন্য প্রদর্শিত হয়। সার্কিট র্যাঙ্ক সহ যে কোনও দ্বি-সংযুক্ত গ্রাফে, প্রতিটি খোলা কানের পচনের ঠিক কান থাকে। প্রায়-গাছ সাইক্লোম্যাটিক সংখ্যা সহ একটি গ্রাফকে আর-অলমোস্ট-ট্রিও বলা হয়, কারণ এটি একটি গাছ বা বনে পরিণত করার জন্য গ্রাফ থেকে শুধুমাত্র আর প্রান্তগুলি সরানো প্রয়োজন। একটি 1-নিকটতম গাছ হল একটি নিকটবর্তী গাছঃ একটি সংযুক্ত নিকটবর্তী গাছ হল একটি ছদ্ম গাছ, প্রতিটি শীর্ষে শিকড়যুক্ত (সম্ভবত তুচ্ছ) গাছ সহ একটি চক্র। বেশ কয়েকজন লেখক r-কাছাকাছি-গাছের উপর গ্রাফ অ্যালগরিদমের প্যারামিটারাইজড জটিলতা অধ্যয়ন করেছেন। নির্দেশিত গ্রাফগুলিতে সাধারণীকরণ চক্রের র্যাঙ্ক হল নির্দেশিত গ্রাফগুলির একটি অপরিবর্তনীয় যা গ্রাফে চক্রগুলির বাসা বাঁধার মাত্রা পরিমাপ করে। সার্কিট র্যাঙ্কের তুলনায় এর সংজ্ঞা আরও জটিল (অনির্দিষ্ট গ্রাফের জন্য বৃক্ষ-গভীরতার সংজ্ঞার সাথে ঘনিষ্ঠভাবে সম্পর্কিত) এবং গণনা করা আরও কঠিন। সার্কিট র্যাঙ্কের সাথে সম্পর্কিত নির্দেশিত গ্রাফের জন্য আরেকটি সমস্যা হল ন্যূনতম প্রতিক্রিয়া চাপ সেট, প্রান্তের ক্ষুদ্রতম সেট যার অপসারণ সমস্ত নির্দেশিত চক্রকে ভেঙে দেয়। সাইকেল র্যাঙ্ক এবং ন্যূনতম ফিডব্যাক আর্ক সেট উভয়ই গণনা করার জন্য এনপি-হার্ড। প্রান্তের দিকগুলি উপেক্ষা করে এবং অন্তর্নিহিত অনির্দিষ্ট গ্রাফের সার্কিট র্যাঙ্ক গণনা করে নির্দেশিত গ্রাফগুলির একটি সহজ অপরিবর্তনীয় গণনা করাও সম্ভব। এই নীতিটি সাইক্লোম্যাটিক জটিলতার সংজ্ঞার ভিত্তি গঠন করে, যা কম্পিউটার কোডের একটি অংশ কতটা জটিল তা অনুমান করার জন্য একটি সফ্টওয়্যার মেট্রিক। গাণিতিক রসায়ন রসায়ন এবং কেমিনফরম্যাটিক্সের ক্ষেত্রে, একটি আণবিক গ্রাফের সার্কিট র্যাঙ্ককে (ক্ষুদ্রতম বলয়ের ক্ষুদ্রতম সেটের বলয়ের সংখ্যা) কখনও কখনও ফ্রেরেজাক সংখ্যা হিসাবে উল্লেখ করা হয়। প্যারামিট্রাইজড জটিলতা গ্রাফের কিছু গণনামূলক সমস্যা সাধারণভাবে এনপি-হার্ড, তবে একটি ছোট সার্কিট র্যাঙ্ক সহ গ্রাফের জন্য বহুপদী সময়ে সমাধান করা যেতে পারে। একটি উদাহরণ হল পথ পুনর্গঠন সমস্যা। সম্পর্কিত ধারণাগুলি গ্রাফ থেকে জিনিসগুলি মুছে ফেলার ক্ষেত্রে সংজ্ঞায়িত অন্যান্য সংখ্যাগুলি হ 'লঃ প্রান্ত সংযোগ-গ্রাফটি সংযোগ বিচ্ছিন্ন করার জন্য মুছে ফেলার জন্য সর্বনিম্ন প্রান্তের সংখ্যা; ম্যাচিং প্রিক্লুশন-একটি নিখুঁত মিলনের অস্তিত্ব রোধ করার জন্য মুছে ফেলার জন্য সর্বনিম্ন প্রান্তের সংখ্যা; ফিডব্যাক ভার্টেক্স সেট নম্বর-গ্রাফটি অ্যাসাইক্লিক করার জন্য মুছে ফেলার জন্য সর্বনিম্ন শীর্ষের সংখ্যা; ফিডব্যাক আর্ক সেট-একটি নির্দেশিত গ্রাফ থেকে মুছে ফেলার জন্য সর্বনিম্ন চাপের সংখ্যা, যাতে এটি অ্যাসাইক্লিক হয়। তথ্যসূত্র গ্রাফ অপরিবর্তনীয় ম্যাট্রয়েড তত্ত্ব বিস্তৃত গাছ