নির্দেশিত এবং অনির্দেশিত গ্রাফের মধ্যে পার্থক্য

নির্দেশিত বনাম অনির্দেশিত গ্রাফ

একটি গ্রাফ হল একটি গাণিতিক কাঠামো যা শীর্ষবিন্দু এবং প্রান্তের সেট দিয়ে তৈরি। একটি গ্রাফ বস্তুর একটি সেটকে প্রতিনিধিত্ব করে (উল্লম্ব দ্বারা উপস্থাপিত) যা কিছু লিঙ্কের মাধ্যমে সংযুক্ত থাকে (প্রান্ত দ্বারা উপস্থাপিত)। গাণিতিক স্বরলিপি ব্যবহার করে, একটি গ্রাফ G দ্বারা প্রতিনিধিত্ব করা যেতে পারে, যেখানে G=(V, E) এবং V হল শীর্ষবিন্দুর সেট এবং E হল প্রান্তগুলির সেট। একটি অনির্দেশিত গ্রাফে প্রান্তগুলির সাথে যুক্ত কোন দিক নেই যা শীর্ষবিন্দুগুলিকে সংযুক্ত করে। একটি নির্দেশিত গ্রাফে প্রান্তগুলির সাথে যুক্ত একটি দিক রয়েছে যা শীর্ষবিন্দুগুলিকে সংযুক্ত করে৷

অনির্দেশিত গ্রাফ

আগেই উল্লিখিত হিসাবে, একটি অনির্দেশিত গ্রাফ হল এমন একটি গ্রাফ যার প্রান্তগুলিতে কোন দিক নেই যা গ্রাফের শীর্ষগুলিকে সংযুক্ত করে।চিত্র 1 V={V1, V2, V3} শীর্ষবিন্দুগুলির সেট সহ একটি অনির্দেশিত গ্রাফ চিত্রিত করে। উপরের গ্রাফে প্রান্তের সেট V={(V1, V2), (V2, V3), (V1, V3)} হিসাবে লেখা যেতে পারে। এটাও লক্ষ করা যায় যে V={(V2, V1), (V3, V2), (V3, V1)} হিসাবে প্রান্তের সেট লিখতে বাধা দেওয়ার কিছু নেই যেহেতু প্রান্তগুলির একটি দিক নেই৷ তাই একটি অনির্দেশিত গ্রাফের প্রান্তগুলিকে ক্রমযুক্ত জোড়া বলা হয় না। এটি একটি অনির্দেশিত গ্রাফের প্রধান বৈশিষ্ট্য। অনির্দেশিত গ্রাফগুলি শীর্ষবিন্দু দ্বারা উপস্থাপিত বস্তুর মধ্যে প্রতিসাম্য সম্পর্ক উপস্থাপন করতে ব্যবহার করা যেতে পারে। উদাহরণস্বরূপ, একটি দ্বিমুখী সড়ক নেটওয়ার্ক যা শহরগুলির একটি সেটকে সংযুক্ত করে একটি অনির্দেশিত গ্রাফ ব্যবহার করে উপস্থাপন করা যেতে পারে। শহরগুলিকে গ্রাফের শীর্ষবিন্দু দ্বারা উপস্থাপন করা যেতে পারে এবং প্রান্তগুলি শহরগুলির সাথে সংযোগকারী দ্বিমুখী রাস্তাগুলিকে প্রতিনিধিত্ব করে৷

নির্দেশিত গ্রাফ

একটি নির্দেশিত গ্রাফ হল একটি গ্রাফ যেখানে গ্রাফের প্রান্তগুলি যা শীর্ষবিন্দুগুলিকে সংযুক্ত করে তাদের একটি দিকনির্দেশ রয়েছে৷ চিত্র 2 V={V1, V2, V3} শীর্ষবিন্দুগুলির সেট সহ একটি নির্দেশিত গ্রাফ চিত্রিত করে। উপরের গ্রাফে প্রান্তের সেট V={(V1, V2), (V2, V3), (V1, V3)} হিসাবে লেখা যেতে পারে। একটি অনির্দেশিত গ্রাফের প্রান্তগুলিকে ক্রমানুসারে জোড়া হয়। আনুষ্ঠানিকভাবে, নির্দেশিত গ্রাফে প্রান্ত eকে নির্দেশিত জোড়া e=(x, y) দ্বারা উপস্থাপিত করা যেতে পারে যেখানে x হল শীর্ষবিন্দু যাকে বলা হয় উৎপত্তি, উৎস বা প্রান্তের প্রাথমিক বিন্দু, এবং শীর্ষবিন্দু y কে টার্মিনাস বলা হয়, সমাপ্তি শীর্ষবিন্দু বা টার্মিনাল পয়েন্ট। উদাহরণস্বরূপ, একটি রাস্তার নেটওয়ার্ক যা একমুখী রাস্তা ব্যবহার করে শহরগুলির একটি সেটকে সংযুক্ত করে একটি অনির্দেশিত গ্রাফ ব্যবহার করে উপস্থাপন করা যেতে পারে। শহরগুলিকে গ্রাফের শীর্ষবিন্দু দ্বারা উপস্থাপন করা যেতে পারে এবং নির্দেশিত প্রান্তগুলি সেই রাস্তাগুলিকে প্রতিনিধিত্ব করে যেগুলি শহরগুলির সাথে সংযোগ স্থাপন করে রাস্তার ট্র্যাফিক প্রবাহের দিকটি বিবেচনা করে৷

নির্দেশিত গ্রাফ এবং অনির্দেশিত গ্রাফের মধ্যে পার্থক্য কী?

একটি নির্দেশিত গ্রাফে একটি প্রান্ত হল একটি আদেশযুক্ত জোড়া, যেখানে আদেশযুক্ত জোড়া প্রান্তের দিক নির্দেশ করে যা দুটি শীর্ষবিন্দুকে সংযুক্ত করে। অন্যদিকে, একটি অনির্দেশিত গ্রাফে, একটি প্রান্ত হল একটি অবিন্যস্ত জোড়া, যেহেতু একটি প্রান্তের সাথে কোন দিক যুক্ত নেই। অনির্দেশিত গ্রাফগুলি বস্তুর মধ্যে প্রতিসাম্য সম্পর্ক উপস্থাপন করতে ব্যবহার করা যেতে পারে। একটি অনির্দেশিত গ্রাফে প্রতিটি নোডের ইন-ডিগ্রী এবং আউট-ডিগ্রী সমান তবে এটি একটি নির্দেশিত গ্রাফের জন্য সত্য নয়। একটি অনির্দেশিত গ্রাফ উপস্থাপন করার জন্য একটি ম্যাট্রিক্স ব্যবহার করার সময়, ম্যাট্রিক্সটি সর্বদা একটি প্রতিসম গ্রাফে পরিণত হয়, তবে এটি নির্দেশিত গ্রাফের জন্য সত্য নয়। একটি অনির্দেশিত গ্রাফকে একটি নির্দেশিত গ্রাফে রূপান্তরিত করা যেতে পারে প্রতিটি প্রান্ত বিপরীত দিকে যাওয়া দুটি নির্দেশিত প্রান্ত দিয়ে প্রতিস্থাপন করে। যাইহোক, একটি নির্দেশিত গ্রাফকে একটি অনির্দেশিত গ্রাফে রূপান্তর করা সম্ভব নয়৷