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