Cactus graph
গ্রাফ তত্ত্বে, ক্যাকটাস (কখনও কখনও ক্যাকটাস ট্রি বলা হয়) হল একটি সংযুক্ত গ্রাফ যেখানে যে কোনও দুটি সাধারণ চক্রের সর্বাধিক একটি শীর্ষের মিল থাকে। সমতুল্যভাবে, এটি একটি সংযুক্ত গ্রাফ যেখানে প্রতিটি প্রান্ত সর্বাধিক একটি সাধারণ চক্রের অন্তর্গত, বা (অ-তুচ্ছ ক্যাকটির জন্য) যেখানে প্রতিটি ব্লক (কাট-ভার্টেক্স ছাড়া সর্বাধিক সাবগ্রাফ) একটি প্রান্ত বা একটি চক্র। ক্যাকটির বৈশিষ্ট্য হল বাইরের সমতলীয় গ্রাফ। প্রতিটি সিউডোট্রি একটি ক্যাকটাস। একটি অ-তুচ্ছ গ্রাফ একটি ক্যাকটাস হয় যদি এবং শুধুমাত্র যদি প্রতিটি ব্লক একটি সাধারণ চক্র বা একটি প্রান্ত হয়। গ্রাফের পরিবার যেখানে প্রতিটি উপাদান একটি ক্যাকটাস, গ্রাফের ছোটখাটো ক্রিয়াকলাপের অধীনে নিম্নমুখীভাবে বন্ধ করা হয়। এই গ্রাফ পরিবারটি একটি একক নিষিদ্ধ মাইনর দ্বারা চিহ্নিত করা যেতে পারে, সম্পূর্ণ গ্রাফ K4 থেকে একটি প্রান্ত অপসারণ করে গঠিত চার-ভার্টেক্স হীরা গ্রাফ। ত্রিভুজাকার ক্যাকটাস একটি বিশেষ ধরনের ক্যাকটাস গ্রাফ যার প্রতিটি চক্রের দৈর্ঘ্য তিন এবং প্রতিটি প্রান্ত একটি চক্রের অন্তর্গত। উদাহরণস্বরূপ, বন্ধুত্বের গ্রাফ, একটি একক ভাগ করা শীর্ষে একত্রিত ত্রিভুজগুলির সংগ্রহ থেকে গঠিত গ্রাফগুলি ত্রিভুজাকার ক্যাক্টি। ক্যাকটাস গ্রাফ হওয়ার পাশাপাশি ত্রিভুজাকার ক্যাকটিস ব্লক গ্রাফ এবং স্থানীয়ভাবে রৈখিক গ্রাফও হয়। ত্রিভুজাকার ক্যাকটাসগুলির এমন বৈশিষ্ট্য রয়েছে যে যদি তাদের থেকে কোনও মিল সরিয়ে ফেলা হয় তবে তারা সংযুক্ত থাকে; নির্দিষ্ট সংখ্যক শীর্ষের জন্য, এই বৈশিষ্ট্যের সাথে তাদের সম্ভাব্য প্রান্তগুলি সবচেয়ে কম থাকে। বিজোড় সংখ্যক শীর্ষযুক্ত প্রতিটি গাছকে প্রান্ত যোগ করে একটি ত্রিভুজাকার ক্যাকটাসে বর্ধিত করা যেতে পারে, যা একটি মিল অপসারণের পরে সংযুক্ত থাকার বৈশিষ্ট্যের সাথে ন্যূনতম বৃদ্ধি দেয়। ম্যাট্রয়েড প্যারিটি সমস্যার জন্য একটি অ্যালগরিদম ব্যবহার করে যে কোনও গ্রাফের বৃহত্তম ত্রিভুজাকার ক্যাকটাস বহুপদী সময়ে পাওয়া যেতে পারে। যেহেতু ত্রিভুজাকার ক্যাকটাস গ্রাফগুলি সমতলীয় গ্রাফ, তাই বৃহত্তম ত্রিভুজাকার ক্যাকটাসকে বৃহত্তম সমতলীয় উপ-গ্রাফের আনুমানিক হিসাবে ব্যবহার করা যেতে পারে, যা সমতলীকরণের ক্ষেত্রে একটি গুরুত্বপূর্ণ উপ-সমস্যা। একটি আনুমানিক অ্যালগরিদম হিসাবে, এই পদ্ধতির আনুমানিক অনুপাত 4/9, যা সর্বাধিক প্ল্যানার সাবগ্রাফ সমস্যার জন্য সর্বাধিক পরিচিত। বৃহত্তম ত্রিভুজাকার ক্যাকটাস খুঁজে বের করার অ্যালগরিদমটি লোভাস এবং প্লামারের একটি উপপাদ্যের সাথে যুক্ত যা এই বৃহত্তম ক্যাকটাসে ত্রিভুজের সংখ্যাকে চিহ্নিত করে। লোভাস এবং প্লামার প্রদত্ত গ্রাফের শীর্ষ এবং প্রান্তের বিভাজন জোড়াটিকে উপসেট হিসাবে বিবেচনা করেন, এই বৈশিষ্ট্য সহ যে গ্রাফের প্রতিটি ত্রিভুজের শীর্ষ বিভাজনের একক শ্রেণিতে দুটি শীর্ষ থাকে বা প্রান্ত বিভাজনের একক শ্রেণিতে তিনটি প্রান্ত থাকে; তারা এই বৈশিষ্ট্য সহ এক জোড়া বিভাজনকে বৈধ বলে অভিহিত করে। তারপর বৃহত্তম ত্রিভুজাকার ক্যাকটাসে ত্রিভুজের সংখ্যা বৈধ বিভাজনের জোড়ার উপর সর্বাধিক, এবং এর, যেখানে প্রদত্ত গ্রাফের শীর্ষগুলির সংখ্যা এবং প্রান্ত শ্রেণী দ্বারা মিলিত শীর্ষ শ্রেণীর সংখ্যা। প্রতিটি সমতল গ্রাফে একটি ক্যাকটাস সাবগ্রাফ থাকে যার মধ্যে ত্রিভুজাকার মুখের কমপক্ষে ভগ্নাংশ থাকে। এই ফলাফলটি উপরের মিনি-ম্যাক্স সূত্রটি ব্যবহার না করে সর্বাধিক প্ল্যানার সাবগ্রাফ সমস্যার জন্য 4/9-আনুমানিক অ্যালগরিদমের সরাসরি বিশ্লেষণকে বোঝায়। রোজার অনুমান ত্রিভুজাকার ক্যাকটাস সম্পর্কিত একটি গুরুত্বপূর্ণ অনুমান হল রোজার অনুমান, যা আলেকজান্ডার রোজার নামে নামকরণ করা হয়েছে, যা বলে যে সমস্ত ত্রিভুজাকার ক্যাকটাই সুন্দর বা প্রায়-কৃপণ। আরও সুনির্দিষ্টভাবে বলতে গেলে, সমস্ত ত্রিভুজাকার ক্যাকটির t ষ্ণ 0,1 মড 4 ব্লকগুলি সুন্দর এবং t ষ্ণ 2,3 মোড 4 ব্লকগুলি প্রায় সুন্দর। অ্যালগরিদম এবং অ্যাপ্লিকেশন কিছু সুবিধা অবস্থান সমস্যা যা সাধারণ গ্রাফের জন্য এনপি-হার্ড, সেইসাথে কিছু অন্যান্য গ্রাফ সমস্যা, ক্যাকটির জন্য বহুপদী সময়ে সমাধান করা যেতে পারে। যেহেতু ক্যাক্টিগুলি বাইরের সমতলীয় গ্রাফের বিশেষ ক্ষেত্রে, তাই গ্রাফের উপর বেশ কয়েকটি সমন্বিত অপ্টিমাইজেশান সমস্যা তাদের জন্য বহুপদী সময়ে সমাধান করা যেতে পারে। ক্যাকটাই বৈদ্যুতিক বর্তনীকে প্রতিনিধিত্ব করে যার দরকারী বৈশিষ্ট্য রয়েছে। ক্যাকটির একটি প্রাথমিক প্রয়োগ অপ-অ্যাম্পের প্রতিনিধিত্বের সাথে যুক্ত ছিল। বিভিন্ন জিনোম বা জিনোমের অংশগুলির মধ্যে সম্পর্কের প্রতিনিধিত্ব করার উপায় হিসাবে তুলনামূলক জিনোমিক্সেও ক্যাকটিকে ব্যবহার করা হয়েছে। যদি একটি ক্যাকটাস সংযুক্ত থাকে এবং এর প্রতিটি শীর্ষ সর্বাধিক দুটি ব্লকের অন্তর্গত হয়, তবে এটিকে ক্রিসমাস ক্যাকটাস বলা হয়। প্রতিটি পলিহেড্রাল গ্রাফের একটি ক্রিসমাস ক্যাকটাস সাবগ্রাফ থাকে যা তার সমস্ত শীর্ষগুলি অন্তর্ভুক্ত করে, একটি সত্য যা প্রমাণের ক্ষেত্রে একটি গুরুত্বপূর্ণ ভূমিকা পালন করে যে প্রতিটি পলিহেড্রাল গ্রাফের ইউক্লিডিয়ান সমতলে একটি লোভী এম্বেডিং রয়েছে, যা শীর্ষে স্থানাঙ্কের একটি অ্যাসাইনমেন্ট যার জন্য লোভী ফরোয়ার্ডিং সমস্ত জোড়া শীর্ষের মধ্যে বার্তা রাউটিংয়ে সফল হয়। টপোলজিক্যাল গ্রাফ তত্ত্বে, যে গ্রাফগুলির সেলুলার এম্বেডিংগুলি সমস্ত সমতলীয় হয় সেগুলি ক্যাকটাস গ্রাফের ঠিক উপপরিবার যা প্রতিটি শীর্ষে সর্বাধিক একটি চক্রের অন্তর্গত। এই গ্রাফগুলিতে দুটি নিষিদ্ধ অপ্রাপ্তবয়স্ক রয়েছে, ডায়মন্ড গ্রাফ এবং ফাইভ-ভার্টেক্স ফ্রেন্ডশিপ গ্রাফ। ইতিহাস ক্যাকটিকে প্রথম হুসিমি গাছের নামে অধ্যয়ন করা হয়েছিল, যা ফ্রাঙ্ক হারারি এবং জর্জ ইউজিন উহলেনবেক দ্বারা কোডি হুসিমির এই গ্রাফগুলির উপর পূর্ববর্তী কাজের সম্মানে তাদের দেওয়া হয়েছিল। একই হারারি-উহলেনবেক কাগজে এই ধরনের গ্রাফের জন্য "ক্যাকটাস" নামটি সংরক্ষিত রয়েছে যেখানে প্রতিটি চক্র একটি ত্রিভুজ, তবে এখন সমস্ত দৈর্ঘ্যের চক্রের অনুমতি দেওয়া মানসম্মত। এদিকে, হুসিমি গাছ নামটি সাধারণত সেই গ্রাফগুলিকে বোঝাতে এসেছে যেখানে প্রতিটি ব্লক একটি সম্পূর্ণ গ্রাফ (সমতুল্যভাবে, অন্য কোনও গ্রাফের ব্লকগুলির ছেদ গ্রাফ)। এই ব্যবহারের সাথে হুসিমির কাজের খুব কমই সম্পর্ক ছিল এবং আরও প্রাসঙ্গিক শব্দ ব্লক গ্রাফ এখন এই পরিবারের জন্য ব্যবহৃত হয়; তবে, এই অস্পষ্টতার কারণে এই বাক্যাংশটি ক্যাকটাস গ্রাফকে বোঝাতে কম ব্যবহৃত হয়েছে। তথ্যসূত্র বাহ্যিক সংযোগ বৈদ্যুতিন বর্তনীর বিশ্লেষণ ও নকশায় ক্যাকটাস গ্রাফের প্রয়োগ গ্রাফ পরিবার প্ল্যানার গ্রাফ ইন্টিগ্রেটেড সার্কিট