Circle graph
গ্রাফ তত্ত্বে, একটি বৃত্ত গ্রাফ হল একটি কর্ড চিত্রের ছেদ গ্রাফ। অর্থাৎ, এটি একটি অনির্দিষ্ট গ্রাফ যার শীর্ষগুলি একটি বৃত্তের কর্ডগুলির একটি সীমাবদ্ধ ব্যবস্থার সাথে এমনভাবে যুক্ত হতে পারে যে দুটি শীর্ষগুলি সংলগ্ন থাকে যদি এবং কেবল তখনই যদি সংশ্লিষ্ট কর্ডগুলি একে অপরকে অতিক্রম করে। অ্যালগরিদমিক জটিলতা একটি ও (এন2)-টাইম অ্যালগরিদম দেয় যা একটি প্রদত্ত এন-ভার্টেক্স অনির্দিষ্ট গ্রাফ একটি বৃত্তাকার গ্রাফ কিনা তা পরীক্ষা করে এবং যদি তা হয় তবে এটি প্রতিনিধিত্ব করে এমন কর্ডগুলির একটি সেট তৈরি করে। সাধারণ গ্রাফগুলিতে এনপি-সম্পূর্ণ অন্যান্য বেশ কয়েকটি সমস্যার বহুপদী সময় অ্যালগরিদম থাকে যখন বৃত্তাকার গ্রাফের মধ্যে সীমাবদ্ধ থাকে। উদাহরণস্বরূপ, দেখানো হয়েছে যে একটি বৃত্ত গ্রাফের ত্রি-প্রস্থ নির্ধারণ করা যেতে পারে এবং ও (এন3) সময়ে একটি সর্বোত্তম বৃক্ষ পচন তৈরি করা যেতে পারে। উপরন্তু, একটি ন্যূনতম পূরণ (অর্থাৎ, যতটা সম্ভব কম প্রান্ত সহ একটি কর্ডাল গ্রাফ যা একটি উপগ্রাফ হিসাবে প্রদত্ত বৃত্ত গ্রাফ ধারণ করে) ও (এন 3) সময়ে পাওয়া যেতে পারে। দেখানো হয়েছে যে একটি বৃত্ত গ্রাফের সর্বাধিক চক্র O (n log2n) সময়ে পাওয়া যেতে পারে, যেখানে দেখানো হয়েছে যে একটি ওজনহীন বৃত্ত গ্রাফের সর্বাধিক স্বাধীন সেট O (n মিনিট {d, α}) সময়ে পাওয়া যেতে পারে, যেখানে d হল গ্রাফের একটি পরামিতি যা তার ঘনত্ব হিসাবে পরিচিত, এবং α হল বৃত্ত গ্রাফের স্বাধীনতা সংখ্যা। যাইহোক, এমন কিছু সমস্যা রয়েছে যা বৃত্ত গ্রাফের মধ্যে সীমাবদ্ধ থাকলে এনপি-সম্পূর্ণ থাকে। এর মধ্যে রয়েছে ন্যূনতম আধিপত্য সেট, ন্যূনতম সংযুক্ত আধিপত্য সেট এবং ন্যূনতম মোট আধিপত্য সেট সমস্যা। ক্রোমাটিক সংখ্যা একটি বৃত্ত গ্রাফের ক্রোমাটিক সংখ্যা হল ন্যূনতম রঙের সংখ্যা যা তার কর্ডগুলিকে রঙ করার জন্য ব্যবহার করা যেতে পারে যাতে কোনও দুটি ক্রসিং কর্ডের একই রঙ না থাকে। যেহেতু বৃত্তাকার গ্রাফ তৈরি করা সম্ভব যেখানে নির্বিচারে বড় বড় কর্ডগুলি একে অপরকে অতিক্রম করে, তাই একটি বৃত্তাকার গ্রাফের ক্রোমাটিক সংখ্যা নির্বিচারে বড় হতে পারে এবং একটি বৃত্তাকার গ্রাফের ক্রোমাটিক সংখ্যা নির্ধারণ করা এনপি-সম্পূর্ণ। একটি বৃত্তাকার গ্রাফকে চারটি রঙ দিয়ে রঙ করা যায় কিনা তা পরীক্ষা করার জন্য এটি এনপি-সম্পূর্ণ থাকে। তিনি দাবি করেন যে, তিনটি রঙের রঙ খুঁজে বের করা বহুপদী সময়ে করা যেতে পারে, কিন্তু তাঁর এই ফলাফলের লেখায় অনেক বিবরণ বাদ দেওয়া হয়েছে। বেশ কয়েকজন লেখক বৃত্ত গ্রাফের সীমাবদ্ধ উপশ্রেণীগুলিকে অল্প রঙের সাথে রঙ করার সমস্যাগুলি তদন্ত করেছেন। বিশেষত, বৃত্তাকার গ্রাফগুলির জন্য যেখানে k বা তার বেশি কর্ডের কোনও সেট একে অপরকে অতিক্রম করে না, গ্রাফটিকে যত কম রঙ দিয়ে রঙ করা সম্ভব। এটি বলার একটি উপায় হল বৃত্তের গ্রাফগুলি-সীমাবদ্ধ। বিশেষ ক্ষেত্রে যখন k = 3 (অর্থাৎ, ত্রিভুজ-মুক্ত বৃত্ত গ্রাফের জন্য) ক্রোমাটিক সংখ্যা সর্বাধিক পাঁচটি, এবং এটি আঁটসাঁটঃ সমস্ত ত্রিভুজ-মুক্ত বৃত্ত গ্রাফ পাঁচটি রঙে রঙিন হতে পারে, এবং ত্রিভুজ-মুক্ত বৃত্ত গ্রাফ রয়েছে যার জন্য পাঁচটি রঙের প্রয়োজন হয়। যদি একটি বৃত্ত গ্রাফের অন্তত পাঁচটি ঘের থাকে (অর্থাৎ, এটি ত্রিভুজ-মুক্ত এবং কোনও চার-ভার্টেক্স চক্র না থাকে) তবে এটি সর্বাধিক তিনটি রঙে রঙিন হতে পারে। ত্রিভুজ-মুক্ত স্কোয়ারগ্রাফ রঙ করার সমস্যাটি গাছের কার্টেসিয়ান পণ্যগুলির আইসোমেট্রিক সাবগ্রাফ হিসাবে স্কোয়ারগ্রাফগুলি উপস্থাপন করার সমস্যার সমতুল্য; এই চিঠিতে, রঙের রঙের সংখ্যা পণ্যের উপস্থাপনায় গাছের সংখ্যার সাথে মিলে যায়। অ্যাপ্লিকেশন সার্কেল গ্রাফগুলি তারের রাউটিংয়ের জন্য একটি বিশেষ ক্ষেত্রে বিমূর্ত উপস্থাপনা হিসাবে ভিএলএসআই শারীরিক নকশায় উদ্ভূত হয়, যা "দুই-টার্মিনাল সুইচবক্স রাউটিং" নামে পরিচিত। এই ক্ষেত্রে রাউটিং এলাকাটি একটি আয়তক্ষেত্র, সমস্ত জাল দুটি টার্মিনাল, এবং টার্মিনালগুলি আয়তক্ষেত্রের পরিধির উপর স্থাপন করা হয়। এটি সহজেই দেখা যায় যে এই জালগুলির ছেদ গ্রাফটি একটি বৃত্তাকার গ্রাফ। তারের রাউটিং ধাপের লক্ষ্যগুলির মধ্যে একটি হল বিভিন্ন জাল যাতে বৈদ্যুতিকভাবে বিচ্ছিন্ন থাকে এবং তাদের সম্ভাব্য ছেদকারী অংশগুলি অবশ্যই বিভিন্ন পরিবাহী স্তরে স্থাপন করা উচিত। অতএব বৃত্তাকার গ্রাফগুলি এই রাউটিং সমস্যার বিভিন্ন দিক ধারণ করে। বৃত্তাকার গ্রাফের রঙগুলি নির্বিচারে গ্রাফের বইয়ের এম্বেডিং খুঁজে বের করতেও ব্যবহার করা যেতে পারেঃ যদি প্রদত্ত গ্রাফ জি-এর শীর্ষগুলি একটি বৃত্তের উপর সাজানো থাকে, যেখানে জি-এর প্রান্তগুলি বৃত্তের কর্ড গঠন করে, তবে এই কর্ডগুলির ছেদ গ্রাফটি একটি বৃত্তাকার গ্রাফ এবং এই বৃত্তাকার গ্রাফের রঙগুলি প্রদত্ত বৃত্তাকার বিন্যাসকে সম্মান করে এমন বইয়ের এম্বেডিংয়ের সমতুল্য। এই সমতুল্যতায়, রঙের রঙের সংখ্যা বইয়ের এম্বেডিংয়ের পৃষ্ঠাগুলির সংখ্যার সাথে মিলে যায়। একটি গ্রাফ একটি বৃত্তাকার গ্রাফ হয় যদি এবং শুধুমাত্র যদি এটি একটি লাইনের বিরতির একটি সেটের ওভারল্যাপ গ্রাফ হয়। এটি এমন একটি গ্রাফ যেখানে শীর্ষগুলি ব্যবধানগুলির সাথে সামঞ্জস্যপূর্ণ, এবং দুটি শীর্ষ একটি প্রান্ত দ্বারা সংযুক্ত থাকে যদি দুটি ব্যবধান ওভারল্যাপ হয়, যার মধ্যে কোনওটিতেই অন্যটি থাকে না। একটি রেখার অন্তরালের একটি সেটের ছেদ গ্রাফকে অন্তরাল গ্রাফ বলা হয়। স্ট্রিং গ্রাফ, সমতলে বক্ররেখার ছেদ গ্রাফ, একটি বিশেষ ক্ষেত্রে বৃত্ত গ্রাফ অন্তর্ভুক্ত করে। প্রতিটি দূরত্ব-বংশগত গ্রাফ একটি বৃত্তাকার গ্রাফ, যেমন প্রতিটি ক্রমবর্ধমান গ্রাফ এবং প্রতিটি উদাসীনতা গ্রাফ। প্রতিটি বাইরের সমতলীয় গ্রাফও একটি বৃত্তাকার গ্রাফ। বৃত্তের গ্রাফগুলি বহুভুজ-বৃত্তের গ্রাফ দ্বারা সাধারণীকরণ করা হয়, বহুভুজগুলির ছেদ গ্রাফগুলি একই বৃত্তে খোদাই করা থাকে। উল্লেখগুলি উল্লেখ করুন। । । । । । । যেমনটি উল্লেখ করা হয়েছে। । যেমনটি উল্লেখ করা হয়েছে। । যেমনটি উল্লেখ করা হয়েছে। । । । । যেমনটি উল্লেখ করা হয়েছে। । । । । । । । যেমনটি উল্লেখ করা হয়েছে। বৃত্ত গ্রাফের ছেদ শ্রেণী জ্যামিতিক গ্রাফ