Split graph
গণিতের একটি শাখা, গ্রাফ তত্ত্বে, একটি বিভক্ত গ্রাফ হল এমন একটি গ্রাফ যেখানে শীর্ষগুলিকে একটি চক্র এবং একটি স্বাধীন সেটে বিভক্ত করা যেতে পারে। বিভক্ত গ্রাফগুলি প্রথম দ্বারা অধ্যয়ন করা হয়েছিল, এবং স্বাধীনভাবে দ্বারা প্রবর্তিত হয়েছিল। একটি বিভক্ত গ্রাফের একাধিক বিভাজন একটি চক্র এবং একটি স্বাধীন সেটে থাকতে পারে; উদাহরণস্বরূপ, পথটি একটি বিভক্ত গ্রাফ, যার শীর্ষগুলি তিনটি ভিন্ন উপায়ে বিভক্ত করা যেতে পারেঃ চক্র এবং স্বাধীন সেটটি চক্র এবং স্বাধীন সেটটি চক্র এবং স্বাধীন সেট স্প্লিট গ্রাফগুলি তাদের নিষিদ্ধ প্ররোচিত উপগ্রাফগুলির পরিপ্রেক্ষিতে চিহ্নিত করা যেতে পারেঃ একটি গ্রাফ বিভক্ত করা হয় যদি এবং শুধুমাত্র যদি কোনও প্ররোচিত উপগ্রাফ চার বা পাঁচটি শীর্ষে একটি চক্র না হয়, বা বিচ্ছিন্ন প্রান্তের একটি জোড়া (একটি 4-চক্রের পরিপূরক) হয়। অন্যান্য গ্রাফ পরিবারের সাথে সম্পর্ক সংজ্ঞা থেকে, বিভক্ত গ্রাফগুলি স্পষ্টভাবে পরিপূরকের অধীনে বন্ধ করা হয়। বিভক্ত গ্রাফের আরেকটি বৈশিষ্ট্যের মধ্যে রয়েছে পরিপূরকঃ এগুলি কর্ডাল গ্রাফ যার পরিপূরকগুলিও কর্ডাল। ঠিক যেমন কর্ডাল গ্রাফগুলি গাছের উপ-গাছের ছেদ গ্রাফ, তেমনি বিভক্ত গ্রাফগুলি তারা গ্রাফের স্বতন্ত্র স্তরগুলির ছেদ গ্রাফ। প্রায় সমস্ত কর্ডাল গ্রাফগুলি বিভক্ত গ্রাফ; অর্থাৎ, n অসীমের সীমাতে যাওয়ার সাথে সাথে, বিভক্ত n-ভার্টেক্স কর্ডাল গ্রাফের ভগ্নাংশ একটির কাছে পৌঁছায়। যেহেতু কর্ডাল গ্রাফগুলি নিখুঁত, তাই বিভক্ত গ্রাফগুলিও নিখুঁত। ডাবল স্প্লিট গ্রাফ, প্রতিটি শীর্ষকে দ্বিগুণ করে বিভক্ত গ্রাফ থেকে প্রাপ্ত গ্রাফের একটি পরিবার (তাই চক্রটি একটি অ্যান্টিম্যাচিং প্ররোচিত করতে আসে এবং স্বাধীন সেটটি একটি ম্যাচিং প্ররোচিত করতে আসে), নিখুঁত গ্রাফের পাঁচটি মৌলিক শ্রেণীর মধ্যে একটি হিসাবে বিশিষ্টভাবে চিত্রিত হয় যা থেকে অন্যান্য সমস্ত শক্তিশালী নিখুঁত গ্রাফ উপপাদ্য দ্বারা প্রমাণ তৈরি করা যেতে পারে। যদি একটি গ্রাফ একটি বিভক্ত গ্রাফ এবং একটি ব্যবধান গ্রাফ উভয়ই হয়, তবে এর পরিপূরক একটি বিভক্ত গ্রাফ এবং একটি তুলনামূলক গ্রাফ এবং তদ্বিপরীত উভয়ই হয়। বিভক্ত তুলনামূলক গ্রাফ, এবং তাই বিভক্ত ব্যবধান গ্রাফ, তিনটি নিষিদ্ধ প্ররোচিত উপগ্রাফগুলির একটি সেটের পরিপ্রেক্ষিতে চিহ্নিত করা যেতে পারে। বিভক্ত গ্রাফগুলি ঠিক প্রান্তিক গ্রাফ। বিভক্ত ক্রমবিন্যাস গ্রাফগুলি ঠিক সেই ব্যবধান গ্রাফগুলির মধ্যে রয়েছে যার ব্যবধান গ্রাফ পরিপূরক রয়েছে; এগুলি তির্যক-সংযুক্ত ক্রমবিন্যাসের ক্রমবিন্যাস গ্রাফ। বিভক্ত গ্রাফগুলিতে কোক্রোমেটিক সংখ্যা 2 থাকে। অ্যালগরিদমিক সমস্যাগুলি একটি বিভক্ত গ্রাফ হতে দিন, যা একটি চক্র এবং একটি স্বাধীন সেটে বিভক্ত। তারপর একটি বিভক্ত গ্রাফের প্রতিটি সর্বাধিক চক্র হয় নিজেই, অথবা একটি শীর্ষের প্রতিবেশী। সুতরাং, সর্বাধিক চক্র এবং একটি বিভক্ত গ্রাফের পরিপূরক হিসাবে সর্বাধিক স্বাধীন সেট সনাক্ত করা সহজ। যে কোনও বিভক্ত আলেখ্যে, নিম্নলিখিত তিনটি সম্ভাবনার মধ্যে একটি অবশ্যই সত্য হতে হবেঃ এমন একটি শীর্ষ রয়েছে যা সম্পূর্ণ। এই ক্ষেত্রে, একটি সর্বাধিক চক্র এবং একটি সর্বাধিক স্বাধীন সেট। এর মধ্যে এমন একটি শীর্ষ রয়েছে যা স্বাধীন। এই ক্ষেত্রে, এটি একটি সর্বাধিক স্বাধীন সেট এবং এটি একটি সর্বাধিক চক্র। এটি একটি সর্বাধিক চক্র এবং একটি সর্বাধিক স্বাধীন সেট। এই ক্ষেত্রে, একটি চক্র এবং একটি স্বাধীন সেটের মধ্যে একটি অনন্য বিভাজন রয়েছে, এটি সর্বাধিক চক্র, এবং সর্বাধিক স্বাধীন সেট। গ্রাফ কালারিং সহ আরও সাধারণ গ্রাফ পরিবারগুলিতে এনপি-সম্পূর্ণ কিছু অন্যান্য অপ্টিমাইজেশান সমস্যা স্প্লিট গ্রাফগুলিতে একইভাবে সোজা। একটি হ্যামিল্টনিয়ান চক্র খুঁজে পাওয়া এনপি-সম্পূর্ণ থাকে এমনকি বিভক্ত গ্রাফগুলির জন্যও যা দৃঢ়ভাবে কর্ডাল গ্রাফ। এটিও সর্বজনবিদিত যে ন্যূনতম প্রভাবশালী সেট সমস্যা বিভক্ত গ্রাফের জন্য এনপি-সম্পূর্ণ থাকে। ডিগ্রি সিকোয়েন্স বিভক্ত গ্রাফের একটি উল্লেখযোগ্য বৈশিষ্ট্য হল যে এগুলি কেবল তাদের ডিগ্রি সিকোয়েন্স থেকে শনাক্ত করা যায়। একটি গ্রাফের ডিগ্রি সিকোয়েন্স হতে দিন, এবং এর সবচেয়ে বড় মান হতে দিন। তারপর একটি বিভক্ত গ্রাফ হয় যদি এবং শুধুমাত্র যদি এটি হয়, তবে বৃহত্তম ডিগ্রি সহ শীর্ষগুলি সর্বাধিক চক্র গঠন করে এবং অবশিষ্ট শীর্ষগুলি একটি স্বাধীন সেট গঠন করে। একটি নির্বিচারে গ্রাফের বিভাজন পরিমাপ করে যে এই বৈষম্য কতটা সত্য হতে ব্যর্থ হয়েছে। যদি একটি গ্রাফ একটি বিভক্ত গ্রাফ না হয়, তবে প্রান্ত সন্নিবেশ এবং অপসারণের ক্ষুদ্রতম ক্রম যা এটিকে একটি বিভক্ত গ্রাফে পরিণত করে তা বৃহত্তম ডিগ্রি সহ শীর্ষগুলির মধ্যে সমস্ত অনুপস্থিত প্রান্ত যুক্ত করে এবং অবশিষ্ট শীর্ষগুলির জোড়াগুলির মধ্যে সমস্ত প্রান্ত অপসারণ করে প্রাপ্ত করা যেতে পারে; বিভাজন এই ক্রমের ক্রিয়াকলাপের সংখ্যা গণনা করে। বিভক্ত গ্রাফ গণনা করে দেখা যায় যে এন-ভার্টেক্স বিভক্ত গ্রাফগুলি নির্দিষ্ট স্পার্নার পরিবারের সাথে এক-থেকে-এক মিল রয়েছে। এই তথ্যটি ব্যবহার করে, তিনি n শীর্ষে অ-আইসোমরফিক বিভক্ত গ্রাফের সংখ্যার জন্য একটি সূত্র নির্ধারণ করেছিলেন। n = 1 থেকে শুরু করে n এর ছোট মানগুলির জন্য, এই সংখ্যাগুলি হল 1,2,4,9,21,56,164,557,2223,10766,64956,501696,। এই গণনামূলক ফলাফল এর আগে দ্বারা প্রমাণিত হয়েছিল। উল্লেখগুলি উল্লেখ করুন। । । । । । । । । । । । । । । ইউ. এস. এস. আর-এর অ্যাকাডেমি অফ সায়েন্সেস-এর গাণিতিক নোট 48 (6): <আই. ডি. 1>, "অচিহ্নিত সংযুক্ত বস্তু গণনা করার আরেকটি পদ্ধতি" (1990) হিসাবে অনুবাদ করা হয়েছে। । । মার্টিন চার্লস গোলাম্বিকের "অ্যালগরিদমিক গ্রাফ থিওরি অ্যান্ড পারফেক্ট গ্রাফস" বইটিতে বিভক্ত গ্রাফের উপর একটি অধ্যায় রয়েছে। গ্রাফ পরিবার গ্রাফের ছেদ শ্রেণী নিখুঁত গ্রাফ