ডেটা স্ট্রাকচারে আয়লারিয়ান ও হ্যামিল্টোনিয়ান গ্রাফ

এই বিভাগে আমরা আয়লারিয়ান ও হ্যামিল্টোনিয়ান গ্রাফ দেখব। কিন্তু এর আগে আমাদের গ্রাফে ট্রেইল কী সেটি দেখতে হবে। ধরি আমাদের নিচের মতো একটি গ্রাফ আছে:

ট্রেইল হল একটি পথ, যা এজের একটি ক্রম (v1, v2), (v2, v3), …, (vk-1, vk) যেখানে সব ভেরটেক্স (v1, v2, …, vk) ভিন্ন নাও হতে পারে, কিন্তু সব এজ ভিন্ন হবে। এই উদাহরণে একটি ট্রেইল হল {(B, A), (A, C), (C, D), (D, A), (A, F)}। এটি একটি ট্রেইল। কিন্তু এটিকে সিম্পল পথ বলা যাবে না কারণ ভেরটেক্স A দুবার দখল করা হয়েছে। যদি প্রথম ও শেষ ভেরটেক্স একই হয়, তবে সেটি একটি ক্লোজড ট্রেইল হবে।

আয়লারিয়ান ট্রেইল

একটি গ্রাফ G(V, E)-এ আয়লারিয়ান ট্রেইল হল এমন একটি ট্রেইল যা প্রতিটি এজকে ঠিক একবার অন্তর্ভুক্ত করে। যদি G-র একটি ক্লোজড আয়লারিয়ান ট্রেইল থাকে, তবে সেই গ্রাফকে আয়লারিয়ান গ্রাফ বলা হয়। অন্য কথায়, একটি গ্রাফ G আয়লারিয়ান গ্রাফ হবে যদি একটি ভেরটেক্স থেকে শুরু করে প্রতিটি এজকে ঠিক একবার ট্রাভার্স করে প্রত্যাবর্তন করা যায়। আয়লার প্রমাণ করলেন যে একটি গ্রাফ আয়লারিয়ান গ্রাফ হবে যদি এবং কেবল যদি তার প্রতিটি ভেরটেক্সের ডিগ্রি জোড় সংখ্যা হয়।

হ্যামিল্টোনিয়ান সাইকেল

একটি সাইকেলকে হ্যামিল্টোনিয়ান সাইকেল বলা হয় যদি সেটি গ্রাফ G-এর প্রতিটি ভেরটেক্সের মধ্য দিয়ে যায়। একটি গ্রাফ হ্যামিল্টোনিয়ান কিনা তা নির্ধারণের জন্য nhiều ভিন্ন থিওরেম পর্যাপ্ত শর্ত দেয়। যাইহোক, একটি যাদবিক গ্রাফ হ্যামিল্টোনিয়ান কিনা তা নির্ধারণ করা একটি NP-Complete সমস্যা।