Degree (graph theory)
গ্রাফ তত্ত্বে, একটি গ্রাফের শীর্ষের ডিগ্রি (বা ভ্যালেন্সি) হল শীর্ষে আপতিত প্রান্তের সংখ্যা; একটি মাল্টিগ্রাফিতে, একটি লুপ প্রান্তের দুটি প্রান্তের জন্য একটি শীর্ষের ডিগ্রিতে 2 অবদান রাখে। একটি শীর্ষের মাত্রা চিহ্নিত করা হয় বা। একটি গ্রাফের সর্বোচ্চ ডিগ্রি, যার দ্বারা চিহ্নিত করা হয়, এবং একটি গ্রাফের সর্বনিম্ন ডিগ্রি, যার দ্বারা চিহ্নিত করা হয়, তার শীর্ষগুলির সর্বোচ্চ এবং সর্বনিম্ন ডিগ্রি। ডানদিকে দেখানো মাল্টিগ্রাফিতে সর্বোচ্চ ডিগ্রি হল 5 এবং সর্বনিম্ন ডিগ্রি হল 0। একটি নিয়মিত গ্রাফে, প্রতিটি শীর্ষের একই ডিগ্রি থাকে, এবং তাই আমরা গ্রাফের ডিগ্রির কথা বলতে পারি। একটি সম্পূর্ণ গ্রাফ (সূচিত, যেখানে গ্রাফের শীর্ষগুলির সংখ্যা) একটি বিশেষ ধরনের নিয়মিত গ্রাফ যেখানে সমস্ত শীর্ষগুলির সর্বাধিক সম্ভাব্য ডিগ্রি থাকে। একটি স্বাক্ষরিত আলেখে, শীর্ষের সাথে সংযুক্ত ধনাত্মক প্রান্তের সংখ্যাকে ধনাত্মক ডিগ্রি বলা হয় এবং সংযুক্ত ঋণাত্মক প্রান্তের সংখ্যাকে ঋণাত্মক ডিগ্রি বলা হয়। হ্যান্ডশেকিং লেম্মা ডিগ্রি সমষ্টি সূত্রটি বলে যে, একটি গ্রাফ দেওয়া হলে, সূত্রটি বোঝায় যে কোনও অনির্দিষ্ট গ্রাফে, বিজোড় ডিগ্রি সহ শীর্ষগুলির সংখ্যা জোড়। এই বিবৃতিটি (পাশাপাশি ডিগ্রি সমষ্টি সূত্র) হ্যান্ডশেকিং লেম্মা নামে পরিচিত। পরের নামটি একটি জনপ্রিয় গাণিতিক সমস্যা থেকে এসেছে, যা প্রমাণ করে যে, যে কোনও গোষ্ঠীর মানুষের মধ্যে, দলের বিজোড় সংখ্যক মানুষের সঙ্গে হাত মেলানো মানুষের সংখ্যা সমান। ডিগ্রি সিকোয়েন্স একটি অনির্দিষ্ট গ্রাফের ডিগ্রি সিকোয়েন্স হল তার ভার্টেক্স ডিগ্রির অ-বৃদ্ধি ক্রম; উপরের গ্রাফের জন্য এটি হল (5,3,3,2,1,0)। ডিগ্রি সিকোয়েন্স একটি গ্রাফ অপরিবর্তনীয়, তাই আইসোমরফিক গ্রাফের একই ডিগ্রি সিকোয়েন্স থাকে। যাইহোক, ডিগ্রি সিকোয়েন্স, সাধারণভাবে, একটি গ্রাফকে অনন্যভাবে চিহ্নিত করে না; কিছু ক্ষেত্রে, অ-সমরূপ গ্রাফের একই ডিগ্রি সিকোয়েন্স থাকে। ডিগ্রি সিকোয়েন্স সমস্যা হল কিছু বা সমস্ত গ্রাফ খুঁজে বের করার সমস্যা যেখানে ডিগ্রি সিকোয়েন্সটি ধনাত্মক পূর্ণসংখ্যার একটি প্রদত্ত অ-ক্রমবর্ধমান ক্রম। (পিছনের শূন্যগুলিকে উপেক্ষা করা যেতে পারে কারণ গ্রাফটিতে উপযুক্ত সংখ্যক বিচ্ছিন্ন শীর্ষ যোগ করে এগুলি তুচ্ছভাবে উপলব্ধি করা হয়।) একটি ক্রম যা কোনও গ্রাফের ডিগ্রি ক্রম, অর্থাৎ। যার জন্য ডিগ্রি সিকোয়েন্স সমস্যার একটি সমাধান রয়েছে, তাকে গ্রাফিক বা গ্রাফিকাল সিকোয়েন্স বলা হয়। ডিগ্রি যোগফল সূত্রের ফলস্বরূপ, বিজোড় যোগফল সহ যে কোনও ক্রম, যেমন (3,3,1), একটি গ্রাফের ডিগ্রি ক্রম হিসাবে উপলব্ধি করা যায় না। বিপরীতটিও সত্যঃ যদি একটি ক্রমের জোড় থাকে, তবে এটি একটি মাল্টিগ্রাফ-এর ডিগ্রি ক্রম। এই ধরনের গ্রাফের নির্মাণ সহজবোধ্যঃ জোড়ায় বিজোড় ডিগ্রির সাথে শীর্ষগুলিকে সংযুক্ত করুন (একটি মিল তৈরি করে), এবং অবশিষ্ট জোড় ডিগ্রি গণনাগুলি স্ব-লুপ দ্বারা পূরণ করুন। একটি প্রদত্ত ডিগ্রি ক্রম একটি সহজ গ্রাফ দ্বারা উপলব্ধি করা যেতে পারে কিনা তা আরও চ্যালেঞ্জিং। এই সমস্যাটিকে গ্রাফ উপলব্ধি সমস্যাও বলা হয় এবং এরদোস-গাল্লাই উপপাদ্য বা হাভেল-হাকিমি অ্যালগরিদম দ্বারা সমাধান করা যেতে পারে। একটি প্রদত্ত ডিগ্রি সিকোয়েন্স সহ গ্রাফের সংখ্যা খুঁজে বের করা বা অনুমান করার সমস্যাটি গ্রাফ গণনার ক্ষেত্র থেকে একটি সমস্যা। আরও সাধারণভাবে, একটি হাইপারগ্রাফ-এর ডিগ্রি সিকোয়েন্স হল তার ভার্টেক্স ডিগ্রির অ-বৃদ্ধি ক্রম। একটি ক্রম-গ্রাফিক হয় যদি এটি কোনও-ইউনিফর্ম হাইপারগ্রাফ-এর ডিগ্রি ক্রম হয়। বিশেষ করে, একটি-গ্রাফিক ক্রম গ্রাফিক হয়। একটি প্রদত্ত ক্রম-গ্রাফিক কিনা তা নির্ধারণ করা এরদোস-গাল্লাই উপপাদ্যের মাধ্যমে বহুপদী সময়ে করা যায় তবে সকলের জন্য এনপি-সম্পূর্ণ। বিশেষ মান 0 ডিগ্রি সহ একটি শীর্ষকে একটি বিচ্ছিন্ন শীর্ষ বলা হয়। 1 ডিগ্রি সহ একটি শীর্ষকে পাতার শীর্ষ বা শেষ শীর্ষ বা ঝুলন্ত শীর্ষ বলা হয় এবং সেই শীর্ষের সাথে প্রান্তের ঘটনাকে ঝুলন্ত প্রান্ত বলা হয়। ডানদিকে গ্রাফটিতে, {3,5} একটি ঝুলন্ত প্রান্ত। গ্রাফ তত্ত্বের গাছ এবং বিশেষত উপাত্ত কাঠামো হিসাবে গাছগুলির অধ্যয়নে এই পরিভাষাটি প্রচলিত। n শীর্ষে একটি গ্রাফে n-1 ডিগ্রি সহ একটি শীর্ষকে একটি প্রভাবশালী শীর্ষ বলা হয়। গ্লোবাল বৈশিষ্ট্য গ্রাফের প্রতিটি শীর্ষে যদি একই ডিগ্রি k থাকে, তবে গ্রাফটিকে কে-রেগুলার গ্রাফ বলা হয় এবং গ্রাফটি নিজেই ডিগ্রি k বলে বলা হয়। একইভাবে, একটি দ্বিদলীয় গ্রাফ যেখানে দ্বিদলীয় বিভাজনের একই দিকে প্রতিটি দুটি শীর্ষে একই ডিগ্রি থাকে তাকে দ্বিমুখী গ্রাফ বলা হয়। একটি অনির্দিষ্ট, সংযুক্ত গ্রাফের একটি ইউলারিয়ান পথ থাকে যদি এবং শুধুমাত্র যদি এটির বিজোড় মাত্রার 0 বা 2টি শীর্ষ থাকে। যদি এটির বিজোড় মাত্রার 0টি শীর্ষ থাকে, তবে ইউলেরিয়ান পথটি একটি ইউলেরিয়ান সার্কিট। একটি নির্দেশিত গ্রাফ একটি নির্দেশিত সিউডোফরেস্ট হয় যদি এবং শুধুমাত্র যদি প্রতিটি শীর্ষে সর্বাধিক 1 ডিগ্রি থাকে। একটি কার্যকরী গ্রাফ একটি সিউডোফরেস্টের একটি বিশেষ কেস যেখানে প্রতিটি শীর্ষে ঠিক 1 ডিগ্রি থাকে। ব্রুকসের উপপাদ্য অনুসারে, একটি চক্র বা একটি বিজোড় চক্র ব্যতীত যে কোনও গ্রাফ জি-এর সর্বাধিক ক্রোমাটিক সংখ্যা রয়েছে এবং ভাইজিংয়ের উপপাদ্য অনুসারে যে কোনও গ্রাফের সর্বাধিক ক্রোমাটিক সূচক রয়েছে δ (জি) + 1। একটি কে-ডিজেনারেট গ্রাফ হল এমন একটি গ্রাফ যেখানে প্রতিটি সাবগ্রাফ সর্বাধিক কে-তে ডিগ্রির একটি শীর্ষ থাকে। দ্বিদলীয় গ্রাফের নোট রেফারেন্সের জন্য ডিগ্রাফ ডিগ্রি ডিস্ট্রিবিউশন ডিগ্রি সিকোয়েন্সের জন্য আউট ডিগ্রি ইনডিগ্রি দেখুন। । । গ্রাফ তত্ত্ব