Directed graph
গণিতে, এবং আরও সুনির্দিষ্টভাবে গ্রাফ তত্ত্বে, একটি নির্দেশিত গ্রাফ (বা ডিগ্রাফ) এমন একটি গ্রাফ যা নির্দেশিত প্রান্ত দ্বারা সংযুক্ত শীর্ষগুলির একটি সেট নিয়ে গঠিত, যাকে প্রায়শই চাপ বলা হয়। সংজ্ঞা আনুষ্ঠানিক ভাষায়, একটি নির্দেশিত গ্রাফ হল একটি ক্রমযুক্ত জোড়া যেখানে ভি হল একটি সেট যার উপাদানগুলিকে শীর্ষ, নোড বা পয়েন্ট বলা হয়; এ হল শীর্ষগুলির ক্রমযুক্ত জোড়ার একটি সেট, যাকে বলা হয় আর্ক্স, নির্দেশিত প্রান্ত (কখনও কখনও কেবল এ-এর পরিবর্তে ই নামে সংশ্লিষ্ট সেটের সাথে প্রান্ত), তীর বা নির্দেশিত রেখা। এটি একটি সাধারণ বা অনির্দিষ্ট গ্রাফের থেকে পৃথক, যার মধ্যে পরেরটিকে অনিয়ন্ত্রিত জোড়া শীর্ষের পরিপ্রেক্ষিতে সংজ্ঞায়িত করা হয়, যাকে সাধারণত প্রান্ত, লিঙ্ক বা রেখা বলা হয়। পূর্বোক্ত সংজ্ঞাটি একটি নির্দেশিত গ্রাফকে একই উৎস এবং লক্ষ্য নোড সহ একাধিক তীরের অনুমতি দেয় না, তবে কিছু লেখক একটি বিস্তৃত সংজ্ঞা বিবেচনা করেন যা নির্দেশিত গ্রাফগুলিকে এই ধরনের একাধিক চাপের অনুমতি দেয় (যথা, তারা চাপ সেটটিকে একটি মাল্টিসেট হতে দেয়)। কখনও কখনও এই সত্তাগুলিকে নির্দেশিত বহু-লিপি (বা বহু-লিপি) বলা হয়। অন্যদিকে, পূর্বোক্ত সংজ্ঞাটি একটি নির্দেশিত গ্রাফকে লুপ রাখার অনুমতি দেয় (অর্থাৎ, বৃত্ত যা সরাসরি নোডগুলিকে নিজেদের সাথে সংযুক্ত করে), তবে কিছু লেখক একটি সংকীর্ণ সংজ্ঞা বিবেচনা করেন যা নির্দেশিত গ্রাফগুলিকে লুপ করার অনুমতি দেয় না। লুপ ছাড়া নির্দেশিত গ্রাফগুলিকে সহজ নির্দেশিত গ্রাফ বলা যেতে পারে, অন্যদিকে লুপ সহ নির্দেশিত গ্রাফগুলিকে লুপ-ডিগ্রাফ বলা যেতে পারে (বিভাগ দেখুন নির্দেশিত গ্রাফের প্রকার)। নির্দেশিত গ্রাফের প্রকার উপশ্রেণী প্রতিসম নির্দেশিত গ্রাফগুলি নির্দেশিত গ্রাফ যেখানে সমস্ত প্রান্ত দু 'বার প্রদর্শিত হয়, প্রতিটি দিকে একটি করে (অর্থাৎ, ডিগ্রাফের অন্তর্গত প্রতিটি তীরের জন্য, সংশ্লিষ্ট বিপরীত তীরটিও এর অন্তর্গত)। (এই ধরনের প্রান্তকে কখনও কখনও "দ্বিমুখী" বলা হয় এবং এই ধরনের গ্রাফগুলিকে কখনও কখনও "দ্বিমুখী" বলা হয়, তবে এটি দ্বিমুখী গ্রাফের অর্থের সাথে দ্বন্দ্ব করে।) সহজ নির্দেশিত গ্রাফগুলি এমন নির্দেশিত গ্রাফ যা কোনও লুপ (তীর যা সরাসরি নিজেদের সাথে শীর্ষগুলিকে সংযুক্ত করে) এবং একই উৎস এবং লক্ষ্য নোড সহ একাধিক তীর নেই। ইতিমধ্যে প্রবর্তিত হিসাবে, একাধিক তীরের ক্ষেত্রে সত্তাকে সাধারণত নির্দেশিত মাল্টিগ্রাফ হিসাবে সম্বোধন করা হয়। কিছু লেখক লুপ সহ ডিগ্রাফকে লুপ-ডিগ্রাফ হিসাবে বর্ণনা করেছেন। সম্পূর্ণ নির্দেশিত গ্রাফগুলি সহজ নির্দেশিত গ্রাফ যেখানে প্রতিটি জোড়া শীর্ষগুলি নির্দেশিত চাপের প্রতিসম জোড়া দ্বারা যুক্ত হয় (এটি বিপরীত চাপের জোড়া দ্বারা প্রতিস্থাপিত প্রান্তগুলির সাথে একটি অনির্দিষ্ট সম্পূর্ণ গ্রাফের সমতুল্য)। এটি অনুসরণ করে যে একটি সম্পূর্ণ ডিগ্রাফ প্রতিসম। অর্ধ-সম্পূর্ণ মাল্টিপার্টাইট ডিগ্রাফ হল সহজ ডিগ্রাফ যেখানে ভার্টেক্স সেটকে এমন সেটে ভাগ করা হয় যাতে বিভিন্ন সেটে x এবং y শীর্ষের প্রতিটি জুটির জন্য x এবং y এর মধ্যে একটি চাপ থাকে। x এবং y এর মধ্যে একটি চাপ বা বিপরীত দিকে দুটি চাপ থাকতে পারে। অর্ধ-সম্পূর্ণ ডিগ্রাফগুলি হল সহজ ডিগ্রাফ যেখানে প্রতিটি জোড়া শীর্ষের মধ্যে একটি চাপ থাকে। প্রতিটি অর্ধ-সম্পূর্ণ ডিগ্রাফ একটি তুচ্ছ উপায়ে একটি অর্ধ-সম্পূর্ণ মাল্টিপার্টাইট ডিগ্রাফ, যার প্রতিটি শীর্ষভাগ বিভাজনের একটি সেট গঠন করে। আধা-ক্ষণস্থায়ী চিত্রলিপি হল সহজ চিত্রলিপি যেখানে x থেকে y এবং y থেকে z পর্যন্ত বৃত্তাকার স্বতন্ত্র শীর্ষগুলির প্রতিটি ত্রিগুণ x, y, z-এর জন্য x এবং z-এর মধ্যে একটি চাপ থাকে। x এবং z এর মধ্যে কেবল একটি চাপ বা বিপরীত দিকে দুটি চাপ থাকতে পারে। একটি অর্ধ-সম্পূর্ণ ডিগ্রাফ হল একটি আধা-ক্ষণস্থায়ী ডিগ্রাফ। কে-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো-কো - অভিমুখী গ্রাফগুলি নির্দেশিত গ্রাফ যার কোনও বিপরীত জোড়া নির্দেশিত প্রান্ত নেই (অর্থাৎ। সর্বাধিক একটি এবং গ্রাফের তীর হতে পারে)। এটি অনুসরণ করে যে একটি নির্দেশিত গ্রাফ একটি ওরিয়েন্টেড গ্রাফ হয় যদি এবং শুধুমাত্র যদি এটির কোনও 2-চক্র না থাকে। (এটি "ওরিয়েন্টেড গ্রাফ"-এর একমাত্র অর্থ নয়; দেখুন ওরিয়েন্টেশন (গ্রাফ তত্ত্ব)। টুর্নামেন্টগুলি অনির্দিষ্ট সম্পূর্ণ গ্রাফের প্রতিটি প্রান্তের জন্য একটি দিক নির্বাচন করে প্রাপ্ত ভিত্তিক গ্রাফ। একটি টুর্নামেন্ট একটি অর্ধ-সম্পূর্ণ ডিগ্রাফ। একটি নির্দেশিত গ্রাফ অ্যাসাইক্লিক হয় যদি এর কোনও নির্দেশিত চক্র না থাকে। এই ধরনের ডিগ্রাফ-এর সাধারণ নাম হল ডাইরেক্টেড অ্যাসাইক্লিক গ্রাফ (ডিএজি)। মাল্টিট্রি হল ডিএজি যেখানে একই প্রারম্ভিক শীর্ষ থেকে একই শেষ শীর্ষে যাওয়ার জন্য কোনও দুটি স্বতন্ত্র নির্দেশিত পথ নেই। ওরিয়েন্টেড ট্রি বা পলিট্রি হল ডি. এ. জি যা গাছের প্রান্তগুলি (সংযুক্ত, অ্যাসাইক্লিক অনির্দিষ্ট গ্রাফ) ওরিয়েন্ট করে গঠিত হয়। শিকড়যুক্ত গাছগুলি হল অভিমুখী গাছ যেখানে অন্তর্নিহিত অনির্দিষ্ট গাছের সমস্ত প্রান্ত মূল থেকে দূরে বা দিকে পরিচালিত হয় (এগুলিকে যথাক্রমে, আর্বোরেসেন্স বা আউট-ট্রি এবং ইন-ট্রি বলা হয়। সম্পূরক বৈশিষ্ট্যযুক্ত ডিগ্রাফ ওজনযুক্ত নির্দেশিত গ্রাফ (নির্দেশিত নেটওয়ার্ক হিসাবেও পরিচিত) হল (সহজ) নির্দেশিত গ্রাফ যা তাদের তীরগুলিতে নির্ধারিত ওজন সহ, ওজনযুক্ত গ্রাফের মতো (যা অনির্দিষ্ট নেটওয়ার্ক বা ওজনযুক্ত নেটওয়ার্ক হিসাবেও পরিচিত)। ফ্লো নেটওয়ার্কগুলি ওজনযুক্ত নির্দেশিত গ্রাফ যেখানে দুটি নোডকে আলাদা করা হয়, একটি উৎস এবং একটি সিঙ্ক। মূল নির্দেশিত গ্রাফগুলি (ফ্লো গ্রাফ নামেও পরিচিত) হল ডিগ্রাফ যেখানে একটি শীর্ষকে মূল হিসাবে আলাদা করা হয়েছে। কন্ট্রোল-ফ্লো গ্রাফগুলি কম্পিউটার বিজ্ঞানে ব্যবহৃত মূলযুক্ত ডিগ্রাফ যা কোনও প্রোগ্রামের বাস্তবায়নের সময় যে পথগুলি অতিক্রম করা যেতে পারে তার প্রতিনিধিত্ব হিসাবে ব্যবহৃত হয়। সিগন্যাল-ফ্লো গ্রাফগুলি নির্দেশিত গ্রাফ যেখানে নোডগুলি সিস্টেম ভেরিয়েবল এবং শাখাগুলি (প্রান্ত, চাপ বা তীর) নোডের জোড়ার মধ্যে কার্যকরী সংযোগগুলি উপস্থাপন করে। ফ্লো গ্রাফ হল রৈখিক বীজগাণিতিক বা ডিফারেনশিয়াল সমীকরণের একটি সেটের সাথে যুক্ত ডিগ্রাফ। রাষ্ট্রীয় রেখাচিত্রগুলি নির্দেশিত বহু-লিপি যা সীমাবদ্ধ রাষ্ট্রীয় যন্ত্রের প্রতিনিধিত্ব করে। বিনিময়যোগ্য রেখাচিত্রগুলি বিভাগ তত্ত্বে ব্যবহৃত ডিগ্রাফ, যেখানে শীর্ষগুলি (গাণিতিক) বস্তুর প্রতিনিধিত্ব করে এবং তীরগুলি অঙ্গসংস্থানের প্রতিনিধিত্ব করে, এই বৈশিষ্ট্য সহ যে একই শুরু এবং শেষ বিন্দু সহ সমস্ত নির্দেশিত পথ রচনা দ্বারা একই ফলাফলের দিকে পরিচালিত করে। লাই গ্রুপ তত্ত্ব অনুসারে, কুইভার কিউ হল একটি নির্দেশিত গ্রাফ যা একটি ফাংক্টর হিসাবে সংজ্ঞায়িত একটি উপস্থাপনা ভি-এর ডোমেন হিসাবে কাজ করে এবং এইভাবে এর আকারকে চিহ্নিত করে, বিশেষত ফাংক্টর বিভাগ ফিনভিক্টিকেএফ (কিউ)-এর একটি বস্তু যেখানে এফ (কিউ) কিউ-তে মুক্ত বিভাগ যা কিউ-এর পথ নিয়ে গঠিত এবং ফিনভিক্টকে হল একটি ক্ষেত্র কে-এর উপর সীমাবদ্ধ-মাত্রিক ভেক্টর স্পেসের বিভাগ। একটি কুইভারের প্রতিনিধিত্বগুলি ভেক্টর স্পেস এবং তার প্রান্তগুলি (এবং তাই পথগুলি) তাদের মধ্যে রৈখিক রূপান্তরের সাথে সামঞ্জস্যপূর্ণভাবে লেবেল করে এবং প্রাকৃতিক রূপান্তরের মাধ্যমে রূপান্তরিত হয়। মৌলিক পরিভাষা একটি চাপকে x থেকে y পর্যন্ত নির্দেশিত বলে মনে করা হয়; y কে বলা হয় হেড এবং x কে বলা হয় আর্কের লেজ; y কে বলা হয় x এর সরাসরি উত্তরসূরি এবং x কে বলা হয় y এর সরাসরি পূর্বসূরি। যদি একটি পথ x থেকে y-তে যায়, তবে y কে x-এর উত্তরসূরি এবং x থেকে পৌঁছানো যায় এবং x কে y-এর পূর্বসূরি বলা হয়। এই চাপকে বলা হয় এর বিপরীত চাপ। লুপ সহ একটি মাল্টিডিগ্রাফের সংলগ্ন ম্যাট্রিক্স হ 'ল শীর্ষগুলির সাথে সম্পর্কিত সারি এবং কলাম সহ পূর্ণসংখ্যা-মূল্যবান ম্যাট্রিক্স, যেখানে একটি ননডায়াগোনাল এন্ট্রি এআইজে হ' ল শীর্ষ 1 থেকে শীর্ষ 1 পর্যন্ত চাপের সংখ্যা এবং তির্যক এন্ট্রি এআইআই হ 'ল শীর্ষ 1 এ লুপগুলির সংখ্যা। একটি নির্দেশিত গ্রাফের সংলগ্নতা ম্যাট্রিক্স একটি যৌক্তিক ম্যাট্রিক্স, এবং সারি এবং কলামের বিন্যাস পর্যন্ত অনন্য। একটি নির্দেশিত গ্রাফের জন্য আরেকটি ম্যাট্রিক্স উপস্থাপনা হল এর আপতন ম্যাট্রিক্স। আরও সংজ্ঞার জন্য দিকনির্দেশ দেখুন। একটি শীর্ষের জন্য, একটি শীর্ষের সংলগ্ন মাথার প্রান্তের সংখ্যাকে শীর্ষের ইন্ডেগ্রি বলা হয় এবং একটি শীর্ষের সংলগ্ন লেজের প্রান্তের সংখ্যাকে তার আউট ডিগ্রি বলা হয় (গাছগুলিতে শাখা ফ্যাক্টর বলা হয়)। যাক এবং। v-এর ইনডিগ্রি-কে ডিগ্রি − (v) এবং এর আউট ডিগ্রি-কে ডিগ্রি + (v) হিসাবে চিহ্নিত করা হয়। একটি শীর্ষকে একটি উৎস বলা হয়, কারণ এটি তার প্রতিটি বহির্মুখী চাপের উৎস। একইভাবে, একটি শীর্ষকে সিঙ্ক বলা হয়, কারণ এটি তার প্রতিটি আগত বৃত্তের শেষ। ডিগ্রি সমষ্টি সূত্রে বলা হয়েছে যে, একটি নির্দেশিত গ্রাফের জন্য, যদি প্রতিটি শীর্ষের জন্য, গ্রাফটিকে একটি সুষম নির্দেশিত গ্রাফ বলা হয়। ডিগ্রি সিকোয়েন্স একটি নির্দেশিত গ্রাফের ডিগ্রি সিকোয়েন্স হল তার ইনডিগ্রি এবং আউট ডিগ্রি জোড়ার তালিকা; উপরের উদাহরণের জন্য আমাদের ডিগ্রি সিকোয়েন্স ((2,0), (2,2), (0,2), (1,1) রয়েছে। ডিগ্রি সিকোয়েন্স একটি নির্দেশিত গ্রাফ অপরিবর্তনীয় তাই আইসোমরফিক নির্দেশিত গ্রাফগুলির একই ডিগ্রি সিকোয়েন্স থাকে। যাইহোক, ডিগ্রি সিকোয়েন্স, সাধারণভাবে, একটি নির্দেশিত গ্রাফকে অনন্যভাবে চিহ্নিত করে না; কিছু ক্ষেত্রে, অ-আইসোমরফিক ডিগ্রাফগুলির একই ডিগ্রি সিকোয়েন্স থাকে। নির্দেশিত গ্রাফ উপলব্ধি সমস্যা হল ডিগ্রি সিকোয়েন্স সহ একটি নির্দেশিত গ্রাফ খুঁজে বের করার সমস্যা যা ধনাত্মক পূর্ণসংখ্যা জোড়ার একটি প্রদত্ত ক্রম। (শূন্যের পিছনের জোড়া উপেক্ষা করা যেতে পারে কারণ নির্দেশিত আলেখ্যে উপযুক্ত সংখ্যক বিচ্ছিন্ন শীর্ষ যোগ করে এগুলি তুচ্ছভাবে উপলব্ধি করা হয়।) একটি ক্রম যা কোনও নির্দেশিত গ্রাফের ডিগ্রি ক্রম, অর্থাৎ। যার জন্য নির্দেশিত গ্রাফ উপলব্ধি সমস্যার একটি সমাধান রয়েছে, তাকে নির্দেশিত গ্রাফিক বা নির্দেশিত গ্রাফিকাল ক্রম বলা হয়। এই সমস্যাটি হয় ক্লেইটম্যান-ওয়াং অ্যালগরিদম বা ফুলকারসন-চেন-অ্যানস্টি উপপাদ্য দ্বারা সমাধান করা যেতে পারে। নির্দেশিত গ্রাফ সংযোগ একটি নির্দেশিত গ্রাফ দুর্বলভাবে সংযুক্ত (বা কেবল সংযুক্ত) হয় যদি গ্রাফের সমস্ত নির্দেশিত প্রান্তকে অনির্দিষ্ট প্রান্ত দিয়ে প্রতিস্থাপন করে প্রাপ্ত অনির্দিষ্ট অন্তর্নিহিত গ্রাফটি একটি সংযুক্ত গ্রাফ হয়। একটি নির্দেশিত গ্রাফ দৃঢ়ভাবে সংযুক্ত বা শক্তিশালী হয় যদি এতে প্রতিটি জোড়া শীর্ষের জন্য x থেকে y (এবং y থেকে x) পর্যন্ত একটি নির্দেশিত পথ থাকে। শক্তিশালী উপাদানগুলি হল সর্বাধিক দৃঢ়ভাবে সংযুক্ত সাবগ্রাফ। একটি সংযুক্ত মূলযুক্ত গ্রাফ (বা প্রবাহ গ্রাফ) হল এমন একটি যেখানে একটি বিশিষ্ট মূল শীর্ষ থেকে প্রতিটি শীর্ষে যাওয়ার একটি নির্দেশিত পথ রয়েছে। আরও দেখুন নোটস রেফারেন্স (2007 সালের সংশোধিত প্রথম সংস্করণটি এখন লেখকদের সাইটে বিনামূল্যে পাওয়া যায়; দ্বিতীয় সংস্করণটি 2009 সালে প্রকাশিত হয়েছিল)। । । (বৈদ্যুতিন তৃতীয় সংস্করণটি লেখকের সাইটে বিনামূল্যে পাওয়া যায়)। । পূর্ণসংখ্যা অনুক্রমের অন-লাইন এনসাইক্লোপিডিয়া থেকে এন নোড সহ নির্দেশিত গ্রাফের সংখ্যা (বা নির্দেশিত গ্রাফ) বাহ্যিক লিঙ্ক নির্দেশিত গ্রাফ তত্ত্ব গ্রাফ ডেটা স্ট্রাকচার