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

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

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

অপ্রকাশিত গ্রাফ

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

--২ ->

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

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

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

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