প্ল্যানার গ্রাফের ধারণা
প্ল্যানার গ্রাফ হল এমন একটি গ্রাফ যা একটি সমতল পৃষ্ঠে আঁকা যেতে পারে এমনভাবে যে এর এজগুলি একে অপরকে ছেদ না করে। অর্থাৎ, একটি প্ল্যানার গ্রাফের ভেরটেক্স এবং এজগুলি এমনভাবে সাজানো যায় যে একাধিক পাথের মধ্যে সংযোগ থাকতে পারে কিন্তু তারা একে অপরকে অতিক্রম করবে না।
প্ল্যানার গ্রাফের বৈশিষ্ট্য
- সমতল চিত্রায়ণ:
- প্ল্যানার গ্রাফের সবচেয়ে গুরুত্বপূর্ণ বৈশিষ্ট্য হল এটি সমতলে চিত্রিত করা যায়। এটি এমনভাবে করা যায় যাতে কোনো দুইটি এজের সংযোগ একত্রিত না হয়।
এজ সংখ্যা সীমাবদ্ধতা:
- একটি প্ল্যানার গ্রাফে যদি ভেরটেক্স থাকে, তাহলে এজের সংখ্যা এর জন্য নিম্নলিখিত শর্তাবলী প্রযোজ্য:
এই সম্পর্কটি প্ল্যানার গ্রাফের জন্য এজের সংখ্যা নির্ধারণ করতে সহায়ক।
- কনট্রোলেড সাইকেল:
- প্ল্যানার গ্রাফের মধ্যে সাইকেলের জন্য কিছু সীমাবদ্ধতা থাকে। বিশেষত, একটি গ্রাফ ইউলারিয়ান বা হ্যামিল্টোনিয়ান হলে তা প্ল্যানার হতে পারে।
- কার্টেজিয়ান থিওরেম:
- একটি গ্রাফ প্ল্যানার হয় যদি এবং শুধুমাত্র যদি (একটি পূর্ণ বাইপার্টাইট গ্রাফ) বা (পাঁচটি ভেরটেক্সের একটি পূর্ণ গ্রাফ) এর কোন উপগ্রাফ না থাকে।
- বিভিন্ন উপগ্রাফ:
- প্ল্যানার গ্রাফের যে কোন উপগ্রাফ যদি প্ল্যানার হয়, তবে মূল গ্রাফও প্ল্যানার হবে। তবে, একটি প্ল্যানার গ্রাফের উপগ্রাফগুলি অবশ্যই প্ল্যানার হতে হবে।
- গ্রাফের সংযুক্ততা:
- প্ল্যানার গ্রাফ হতে হলে গ্রাফটি সংযুক্ত হতে হবে। অর্থাৎ, প্রতিটি ভেরটেক্স থেকে অন্য ভেরটেক্সের কাছে পৌঁছানো সম্ভব হতে হবে।
সারসংক্ষেপ
প্ল্যানার গ্রাফ হল একটি গুরুত্বপূর্ণ ধারণা যা গ্রাফের এজ এবং ভেরটেক্সের সংযোগ বিশ্লেষণে ব্যবহৃত হয়। এটি সমতল পৃষ্ঠে আঁকার জন্য একটি নির্দিষ্ট কাঠামো বজায় রাখে এবং এর বিভিন্ন বৈশিষ্ট্য, যেমন এজ সংখ্যা সীমাবদ্ধতা এবং সংযুক্ততা, প্ল্যানার গ্রাফের নির্ধারণে সহায়ক। এই বৈশিষ্ট্যগুলি গ্রাফ তত্ত্ব এবং বাস্তব জীবনের বিভিন্ন সমস্যার সমাধানে অপরিহার্য।
Content added By
Read more
