Splittance
গণিতের একটি শাখা, গ্রাফ তত্ত্বে, একটি অনির্দিষ্ট গ্রাফের বিভাজন একটি বিভক্ত গ্রাফ থেকে তার দূরত্ব পরিমাপ করে। একটি বিভক্ত গ্রাফ হল এমন একটি গ্রাফ যার শীর্ষগুলিকে একটি স্বাধীন সেট (এই উপসেটের মধ্যে কোনও প্রান্ত ছাড়াই) এবং একটি ক্লিকে (এই উপসেটের মধ্যে সমস্ত সম্ভাব্য প্রান্ত সহ) বিভক্ত করা যেতে পারে। স্প্লিট্যান্স হল প্রান্ত সংযোজন এবং অপসারণের ক্ষুদ্রতম সংখ্যা যা প্রদত্ত গ্রাফটিকে একটি বিভক্ত গ্রাফে রূপান্তরিত করে। ডিগ্রি সিকোয়েন্স থেকে গণনা একটি গ্রাফের বিভাজন শুধুমাত্র গ্রাফের ডিগ্রি সিকোয়েন্স থেকে গণনা করা যেতে পারে, গ্রাফের বিস্তারিত কাঠামো পরীক্ষা না করেই। ধরা যাক যেকোনও গ্রাফের শীর্ষবিন্দুতে, যার মাত্রা হ্রাসমান ক্রমে থাকে। ধরা যাক সবচেয়ে বড় সূচক যার জন্য। তারপর এর বিভাজন হল প্রদত্ত গ্রাফটি ইতিমধ্যেই একটি বিভক্ত গ্রাফ যদি। অন্যথায়, গণনা করে, সর্বাধিক মাত্রার শীর্ষগুলির জোড়াগুলির মধ্যে সমস্ত অনুপস্থিত প্রান্ত যোগ করে এবং অবশিষ্ট শীর্ষগুলির জোড়াগুলির মধ্যে সমস্ত প্রান্ত সরিয়ে এটিকে একটি বিভক্ত গ্রাফে পরিণত করা যেতে পারে। ফলস্বরূপ, বিভাজন এবং প্রান্ত সংযোজন এবং অপসারণের একটি ক্রম যা উপলব্ধি করে যে এটি রৈখিক সময়ে গণনা করা যেতে পারে। প্রয়োগ একটি গ্রাফের বিভাজনকে অ্যালগরিদমের দক্ষতা বর্ণনা করার জন্য একটি পরামিতি হিসাবে প্যারামিটারাইজড জটিলতায় ব্যবহার করা হয়েছে। উদাহরণস্বরূপ, গ্রাফের রঙ এই পরামিতিটির অধীনে স্থির-পরামিতি ট্র্যাক্টেবলঃ রৈখিক সময়ে সীমাবদ্ধ বিভাজনের গ্রাফগুলিকে সর্বোত্তমভাবে রঙ করা সম্ভব। রেফারেন্স গ্রাফ অপরিবর্তনীয়