প্রতিটি গাছ দ্বিপক্ষীয়। সমান সংখ্যক শীর্ষবিন্দু সহ সাইকেল গ্রাফগুলি দ্বিপক্ষীয়। প্রতিটি প্ল্যানার গ্রাফ যার সমস্ত মুখের সমান দৈর্ঘ্য দ্বিপক্ষীয়৷
সব কি দ্বিপক্ষীয় গ্রাফ গাছ?
প্রতিটি গাছ দ্বিপক্ষীয়। সমান সংখ্যক শীর্ষবিন্দু সহ সাইকেল গ্রাফগুলি দ্বিপক্ষীয়। প্রতিটি প্ল্যানার গ্রাফ যার সমস্ত মুখের সমান দৈর্ঘ্য দ্বিপক্ষীয়৷
প্রতিটি গাছই দ্বিপক্ষীয় গ্রাফ কেন?
বৃক্ষ: একটি গাছ হল N – 1 প্রান্ত বিশিষ্ট একটি সরল গ্রাফ যেখানে N হল শীর্ষবিন্দুর সংখ্যা যাতে যেকোনো দুটি শীর্ষবিন্দুর মধ্যে ঠিক একটি পথ থাকে। দ্বিপক্ষীয়: একটি গ্রাফ দ্বিপক্ষীয় হয় যদি আমরা শীর্ষবিন্দুকে দুটি বিচ্ছিন্ন সেট V1, V2 এ বিভক্ত করতে পারি যাতে কোনো প্রান্ত একই সেট থেকে শীর্ষবিন্দুকে সংযুক্ত করতে পারে না
আপনি কীভাবে প্রমাণ করবেন যে প্রতিটি গাছ একটি দ্বিপক্ষীয় গ্রাফ?
'' দিয়ে চিহ্নিত শীর্ষবিন্দুর সেট হতে দিন এবং '' দিয়ে চিহ্নিত শীর্ষবিন্দুর সেট হতে দিন। স্পষ্টতই যে কোন দুটি স্বতন্ত্র শীর্ষবিন্দু একটি প্রান্ত দ্বারা সংলগ্ন নয়, এবং একইভাবে, কারণ গাছের কোন সার্কিট নেই; অধিকন্তু, স্পষ্টভাবে গ্রাফের শীর্ষবিন্দু সেটটিকে দুটি বিচ্ছিন্ন উপসেটে ভাগ করুন। সুতরাং, যে কোন গাছ দ্বিপক্ষীয়।
প্রতিটি সম্পূর্ণ গ্রাফ কি দ্বিপক্ষীয়?
প্রতিটি সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ। K , হল একটি মুর গ্রাফ এবং একটি (n, 4)-খাঁচা। সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ K , এবং কে , +1 একই সংখ্যক শীর্ষবিন্দু সহ সমস্ত ত্রিভুজ-মুক্ত গ্রাফের মধ্যে সর্বাধিক সম্ভাব্য সংখ্যক প্রান্ত রয়েছে; এটি ম্যান্টেলের উপপাদ্য।
