Halin graph
গ্রাফ তত্ত্বে, হ্যালিন গ্রাফ হল এক ধরনের সমতলীয় গ্রাফ, যা একটি গাছের পাতাকে একটি চক্রের সাথে সংযুক্ত করে তৈরি করা হয়। গাছের কমপক্ষে চারটি শীর্ষ থাকতে হবে, যার কোনওটিরই ঠিক দুটি প্রতিবেশী নেই; এটি সমতলে টানা উচিত যাতে এর কোনও প্রান্ত অতিক্রম না করে (এটিকে প্ল্যানার এম্বেডিং বলা হয়), এবং চক্রটি এই এম্বেডিংয়ে তাদের ঘড়ির কাঁটার দিকে ক্রম অনুসারে পাতাগুলিকে সংযুক্ত করে। এইভাবে, চক্রটি হ্যালিন গ্রাফের বাইরের মুখ গঠন করে, যার ভিতরে গাছটি রয়েছে। হ্যালিন গ্রাফের নামকরণ করা হয়েছে জার্মান গণিতবিদ রুডলফ হ্যালিন-এর নামে, যিনি 1971 সালে এগুলি অধ্যয়ন করেছিলেন। ঘন হ্যালিন গ্রাফগুলি-যার মধ্যে প্রতিটি শীর্ষ ঠিক তিনটি প্রান্ত স্পর্শ করে-ইতিমধ্যে এক শতাব্দীরও বেশি আগে কার্কম্যান দ্বারা অধ্যয়ন করা হয়েছিল। হ্যালিন গ্রাফগুলি পলিহেড্রাল গ্রাফ, যার অর্থ হল প্রতিটি হ্যালিন গ্রাফ একটি উত্তল পলিহেড্রনের শীর্ষ এবং প্রান্ত তৈরি করতে ব্যবহার করা যেতে পারে এবং এগুলি থেকে গঠিত পলিহেড্রাকে ছাদহীন পলিহেড্র বা গম্বুজ বলা হয়। প্রতিটি হ্যালিন গ্রাফের সমস্ত শীর্ষে একটি হ্যামিল্টনিয়ান চক্র থাকে, পাশাপাশি গ্রাফের শীর্ষের সংখ্যা পর্যন্ত প্রায় সমস্ত দৈর্ঘ্যের চক্র থাকে। হ্যালিন গ্রাফগুলি রৈখিক সময়ে শনাক্ত করা যেতে পারে। যেহেতু হ্যালিন গ্রাফের ত্রি-প্রস্থ কম, তাই অনেক গণনামূলক সমস্যা যা অন্যান্য ধরনের সমতলীয় গ্রাফের জন্য কঠিন, যেমন হ্যামিল্টনিয়ান চক্র খুঁজে বের করা, হ্যালিন গ্রাফের মাধ্যমে দ্রুত সমাধান করা যেতে পারে। উদাহরণস্বরূপ, একটি তারা হল এমন একটি গাছ যার ঠিক একটি অভ্যন্তরীণ শীর্ষ থাকে। একটি তারায় হ্যালিন গ্রাফ নির্মাণ প্রয়োগ করলে একটি চাকা গ্রাফ তৈরি হয়, যা একটি পিরামিডের (প্রান্তের) গ্রাফ। একটি ত্রিভুজাকার প্রিজমের গ্রাফটিও একটি হ্যালিন গ্রাফঃ এটি এমনভাবে আঁকা যেতে পারে যাতে এর আয়তক্ষেত্রাকার মুখগুলির মধ্যে একটি বাইরের চক্র হয় এবং অবশিষ্ট প্রান্তগুলি চারটি পাতা, দুটি অভ্যন্তরীণ শীর্ষ এবং পাঁচটি প্রান্ত সহ একটি গাছ গঠন করে। ফ্রুক্ট গ্রাফ, পাঁচটি ক্ষুদ্রতম ঘন গ্রাফের মধ্যে একটি, যার কোনও অ-তুচ্ছ গ্রাফ অটোমরফিজম নেই, এটিও একটি হ্যালিন গ্রাফ। বৈশিষ্ট্য প্রতিটি হ্যালিন গ্রাফ 3-সংযুক্ত, যার অর্থ এটি থেকে দুটি শীর্ষ মুছে ফেলা এবং অবশিষ্ট শীর্ষগুলি সংযোগ বিচ্ছিন্ন করা সম্ভব নয়। এটি প্রান্ত-ন্যূনতম 3-সংযুক্ত, যার অর্থ যদি এর কোনও একটি প্রান্ত সরানো হয়, তবে অবশিষ্ট গ্রাফটি আর 3-সংযুক্ত থাকবে না। স্টেনিৎজের উপপাদ্য অনুসারে, একটি 3-সংযুক্ত সমতলীয় গ্রাফ হিসাবে, এটিকে একটি উত্তল পলিহেড্রনের শীর্ষ এবং প্রান্তের সেট হিসাবে উপস্থাপন করা যেতে পারে; অর্থাৎ, এটি একটি পলিহেড্রাল গ্রাফ। যে পলিহেড্রনটি গ্রাফটি উপলব্ধি করে তা বেছে নেওয়া যেতে পারে যাতে গাছের সমস্ত পাতা ধারণকারী মুখটি অনুভূমিক হয় এবং অন্যান্য সমস্ত মুখ সমান ঢাল সহ এর উপরে থাকে। প্রতিটি পলিহেড্রাল গ্রাফের মতো, হ্যালিন গ্রাফের একটি অনন্য প্ল্যানার এম্বেডিং রয়েছে, যা এর মুখগুলির মধ্যে কোনটি বাইরের মুখ হতে হবে তা বেছে নেয়। প্রতিটি হ্যালিন গ্রাফ হ্যামিল্টনিয়ান গ্রাফ এবং গ্রাফের প্রতিটি প্রান্ত হ্যামিল্টনিয়ান চক্রের অন্তর্গত। উপরন্তু, যে কোনও শীর্ষ মুছে ফেলার পরে যে কোনও হ্যালিন গ্রাফ হ্যামিল্টনিয়ান থাকে। যেহেতু ডিগ্রি 2-এর শীর্ষবিহীন প্রতিটি গাছে দুটি পাতা থাকে যা একই মূল ভাগ করে নেয়, তাই প্রতিটি হ্যালিন গ্রাফে একটি ত্রিভুজ থাকে। বিশেষ করে, একটি হ্যালিন গ্রাফের পক্ষে ত্রিভুজ-মুক্ত গ্রাফ বা দ্বিদলীয় গ্রাফ হওয়া সম্ভব নয়। আরও দৃঢ়ভাবে, প্রতিটি হ্যালিন গ্রাফ প্রায় প্যানসাইক্লিক, এই অর্থে যে এটির একক জোড় দৈর্ঘ্যের সম্ভাব্য ব্যতিক্রম ছাড়া 3 থেকে n পর্যন্ত সমস্ত দৈর্ঘ্যের চক্র রয়েছে। উপরন্তু, যে কোনও হ্যালিন গ্রাফ প্রায় প্যানসাইক্লিক থাকে যদি একটি প্রান্ত সংকুচিত হয় এবং ডিগ্রি তিন-এর অভ্যন্তরীণ শীর্ষ ছাড়াই প্রতিটি হ্যালিন গ্রাফ প্যানসাইক্লিক হয়। একটি হ্যালিন গ্রাফের আপতন ক্রোমাটিক সংখ্যা যার সর্বোচ্চ ডিগ্রি চারের বেশি হয়। এটি সমস্ত জোড়া (v, e) রঙ করার জন্য প্রয়োজনীয় রঙের সংখ্যা যেখানে v হল গ্রাফের একটি শীর্ষ, এবং e হল v-এর একটি প্রান্ত ঘটনা, যা রঙের নির্দিষ্ট সীমাবদ্ধতা মেনে চলে। যে জোড়াগুলি একটি শীর্ষ ভাগ করে নেয় বা একটি প্রান্ত ভাগ করে নেয় তাদের একই রঙ থাকার অনুমতি নেই। উপরন্তু, একটি জোড়ার (v, e) অন্য জোড়ার মতো একই রঙ থাকতে পারে না যা e এর অন্য প্রান্তবিন্দু ব্যবহার করে। অথবা সহ হ্যালিন গ্রাফের জন্য, আপতন ক্রোমাটিক সংখ্যাটি যথাক্রমে বা তত বড় হতে পারে। গণনামূলক জটিলতা একটি প্রদত্ত-ভার্টেক্স গ্রাফ রৈখিক সময়ে একটি হ্যালিন গ্রাফ কিনা তা পরীক্ষা করা সম্ভব, গ্রাফের একটি সমতলীয় এম্বেডিং খুঁজে বের করে (যদি একটি বিদ্যমান থাকে), এবং তারপরে এমন একটি মুখ রয়েছে কিনা তা পরীক্ষা করে যার কমপক্ষে শীর্ষস্থান রয়েছে, সমস্ত ডিগ্রি তিন। যদি তাই হয়, তবে এই ধরনের সর্বাধিক চারটি মুখ থাকতে পারে এবং তাদের প্রত্যেকটির জন্য রৈখিক সময়ে পরীক্ষা করা সম্ভব যে গ্রাফের বাকি অংশটি এই মুখের শীর্ষগুলি পাতা হিসাবে একটি গাছ গঠন করে কিনা। অন্যদিকে, যদি এমন কোনও মুখ না থাকে, তবে গ্রাফটি হ্যালিন নয়। বিকল্পভাবে, শীর্ষ এবং প্রান্ত সহ একটি গ্রাফ হ্যালিন হয় যদি এবং শুধুমাত্র যদি এটি সমতলীয় হয়, 3-সংযুক্ত, এবং একটি মুখ থাকে যার শীর্ষগুলির সংখ্যা গ্রাফের সার্কিট র্যাঙ্কের সমান হয়, যার সবগুলিই রৈখিক সময়ে পরীক্ষা করা যেতে পারে। রৈখিক সময়ে হ্যালিন গ্রাফগুলি শনাক্ত করার অন্যান্য পদ্ধতির মধ্যে রয়েছে করসেলের উপপাদ্যের প্রয়োগ, বা গ্রাফ পুনর্লিখনের উপর ভিত্তি করে একটি পদ্ধতি, যার কোনওটিই গ্রাফের প্ল্যানার এম্বেডিং জানার উপর নির্ভর করে না। প্রতিটি হ্যালিন গ্রাফের ত্রি-প্রস্থ = 3 থাকে। অতএব, অনেক গ্রাফ অপ্টিমাইজেশান সমস্যা যা নির্বিচারে প্ল্যানার গ্রাফের জন্য এনপি-সম্পূর্ণ, যেমন সর্বাধিক স্বাধীন সেট খুঁজে পাওয়া, গতিশীল প্রোগ্রামিং বা করসেলের উপপাদ্য ব্যবহার করে হ্যালিন গ্রাফগুলিতে রৈখিক সময়ে সমাধান করা যেতে পারে, বা কিছু ক্ষেত্রে (যেমন হ্যামিল্টনিয়ান চক্রের নির্মাণ) সরাসরি অ্যালগরিদম দ্বারা। যাইহোক, প্রদত্ত গ্রাফের বৃহত্তম হ্যালিন সাবগ্রাফ খুঁজে বের করা, প্রদত্ত গ্রাফের সমস্ত শীর্ষগুলি অন্তর্ভুক্ত করে এমন কোনও হ্যালিন সাবগ্রাফ রয়েছে কিনা তা পরীক্ষা করা বা প্রদত্ত গ্রাফটি বৃহত্তর হ্যালিন গ্রাফের সাবগ্রাফ কিনা তা পরীক্ষা করা এনপি-সম্পূর্ণ। 1971 সালে, হ্যালিন ন্যূনতম 3-ভার্টেক্স-সংযুক্ত গ্রাফের একটি শ্রেণী হিসাবে হ্যালিন গ্রাফগুলি প্রবর্তন করেছিলেনঃ গ্রাফের প্রতিটি প্রান্তের জন্য, সেই প্রান্তটি অপসারণ গ্রাফের সংযোগকে হ্রাস করে। এই গ্রাফগুলি এই আবিষ্কারের সাথে তাৎপর্য অর্জন করেছিল যে অনেক অ্যালগরিদমিক সমস্যা যা নির্বিচারে প্ল্যানার গ্রাফের জন্য গণনামূলকভাবে অসম্ভব ছিল সেগুলি দক্ষতার সাথে সমাধান করা যেতে পারে। এই সত্যটি পরে তাদের নিম্ন ত্রি-প্রস্থ এবং করসেলের উপপাদ্যের মতো অ্যালগরিদমিক মেটা-উপপাদ্যগুলির একটি পরিণতি হিসাবে ব্যাখ্যা করা হয়েছিল যা নিম্ন ত্রি-প্রস্থের যে কোনও গ্রাফে এই সমস্যাগুলির কার্যকর সমাধান সরবরাহ করে। এই গ্রাফগুলির উপর হ্যালিনের কাজের আগে, 1856 সালে টমাস কার্কম্যান এবং 1965 সালে হ্যান্স রাডেমাকার দ্বারা ঘন (বা 3-নিয়মিত) হ্যালিন গ্রাফ সম্পর্কিত গ্রাফ গণনা সমস্যাগুলি অধ্যয়ন করা হয়েছিল। রাডেমাকার এই গ্রাফগুলিকে পলিহেড্রা ভিত্তিক বলে অভিহিত করেন। তিনি এগুলিকে ঘন পলিহেড্রাল গ্রাফ হিসাবে সংজ্ঞায়িত করেছেন যার মধ্যে একটি মুখের দিক রয়েছে। এই সংজ্ঞার সাথে মানানসই গ্রাফগুলি ঠিক কিউবিক হ্যালিন গ্রাফ। হ্যালিন গ্রাফ এবং 4-ভার্টেক্স-সংযুক্ত প্ল্যানার গ্রাফ উভয়ই হ্যামিল্টনিয়ান চক্র ধারণ করে এই সত্য দ্বারা অনুপ্রাণিত হয়ে, অনুমান করা হয় যে প্রতিটি 4-ভার্টেক্স-সংযুক্ত প্ল্যানার গ্রাফে একটি বিস্তৃত হ্যালিন সাবগ্রাফ রয়েছে; এখানে "স্প্যানিং" মানে হল যে সাবগ্রাফটি বৃহত্তর গ্রাফের সমস্ত শীর্ষগুলি অন্তর্ভুক্ত করে। লোভাস-প্লামার অনুমান 2015 সাল পর্যন্ত খোলা ছিল, যখন অসীম সংখ্যক বিপরীত উদাহরণের জন্য একটি নির্মাণ প্রকাশিত হয়েছিল। হ্যালিন গ্রাফগুলিকে কখনও কখনও স্কার্টেড ট্রি বা ছাদবিহীন পলিহেড্রাও বলা হয়। তবে, এই নামগুলি দ্ব্যর্থহীন। কিছু লেখক গাছের পাতাকে একটি চক্রের সাথে সংযুক্ত করে গাছ থেকে গঠিত সমতলীয় গ্রাফকে বোঝাতে "স্কার্টেড ট্রি" নামটি ব্যবহার করেন, তবে গাছের অভ্যন্তরীণ শীর্ষে তিন বা তার বেশি ডিগ্রি থাকার প্রয়োজন হয় না। এবং "ভিত্তিক পলিহেড্রা"-র মতো, "ছাদবিহীন পলিহেড্রা" নামটি ঘন হ্যালিন গ্রাফকেও বোঝাতে পারে। উত্তল পলিহেড্রা যার গ্রাফগুলি হ্যালিন গ্রাফ, সেগুলিকেও গম্বুজ বলা হয়। রেফারেন্সগুলি বাহ্যিক লিঙ্কগুলি হ্যালিন গ্রাফ, গ্রাফ ক্লাস অন্তর্ভুক্তি সম্পর্কিত তথ্য ব্যবস্থা। গ্রাফ পরিবার প্ল্যানার গ্রাফ