Strongly regular graph
গ্রাফ তত্ত্বে, একটি দৃঢ় নিয়মিত গ্রাফ (এস. আর. জি) হল শীর্ষ এবং ডিগ্রি সহ একটি নিয়মিত গ্রাফ যাতে কিছু প্রদত্ত পূর্ণসংখ্যার জন্য প্রতিটি দুটি সংলগ্ন শীর্ষের সাধারণ প্রতিবেশী থাকে এবং প্রতিটি দুটি অ-সংলগ্ন শীর্ষের সাধারণ প্রতিবেশী থাকে। এই ধরনের একটি দৃঢ় নিয়মিত গ্রাফ চিহ্নিত করা হয়। এর পরিপূরকও দৃঢ়ভাবে নিয়মিতঃ একটি দৃঢ় নিয়মিত গ্রাফ হল 2 ব্যাস সহ একটি দূরত্ব-নিয়মিত গ্রাফ যখনই μ অ-শূন্য হয়। যখনই এটি একটি স্থানীয়ভাবে রৈখিক গ্রাফ। ব্যুৎপত্তি একটি দৃঢ় নিয়মিত গ্রাফকে সাহিত্যে একটি srg (v, k, λ, μ) হিসাবে চিহ্নিত করা হয়। প্রচলিত রীতি অনুসারে, যে গ্রাফগুলি তুচ্ছভাবে সংজ্ঞাটিকে সন্তুষ্ট করে সেগুলি বিস্তারিত অধ্যয়ন এবং দৃঢ়ভাবে নিয়মিত গ্রাফের তালিকা থেকে বাদ দেওয়া হয়। এর মধ্যে রয়েছে এক বা একাধিক সমান আকারের সম্পূর্ণ গ্রাফের বিচ্ছিন্ন মিলন এবং তাদের পরিপূরক, সমান আকারের স্বাধীন সেট সহ সম্পূর্ণ মাল্টিপার্টাইট গ্রাফ। অ্যান্ড্রিস ব্রাউয়ার এবং হেন্ড্রিক ভ্যান মালদেগেম (দেখুন #References) বর্ণালী গ্রাফ তত্ত্বের উপর ভিত্তি করে একটি দৃঢ় নিয়মিত গ্রাফের একটি বিকল্প কিন্তু সম্পূর্ণ সমতুল্য সংজ্ঞা ব্যবহার করেনঃ একটি দৃঢ় নিয়মিত গ্রাফ হল একটি সীমাবদ্ধ নিয়মিত গ্রাফ যার ঠিক তিনটি আইগেনভ্যালু রয়েছে, যার মধ্যে শুধুমাত্র একটি গুণ 1-এর ডিগ্রি কে-এর সমান। এটি স্বয়ংক্রিয়ভাবে সম্পূর্ণরূপে সংযুক্ত গ্রাফগুলি (যার তিনটি নয়, কেবল দুটি স্বতন্ত্র আইগেনভ্যালু রয়েছে) এবং বিচ্ছিন্ন গ্রাফগুলি (যার ডিগ্রি k-এর গুণিতক বিভিন্ন সংযুক্ত উপাদানগুলির সংখ্যার সমান, যা তাই একটির বেশি হবে) বাতিল করে দেয়। ব্রাউয়ার সহ বেশিরভাগ সাহিত্য বৃহত্তর আইগেনভ্যালু কে r (বহুগুণ f সহ) এবং ছোটটিকে s (বহুগুণ g সহ) হিসাবে উল্লেখ করে। ইতিহাস দৃঢ়ভাবে নিয়মিত গ্রাফ আর. সি দ্বারা চালু করা হয়েছিল। 1963 সালে বোস। তারা 1950-এর দশকে বর্ণালী গ্রাফ তত্ত্বের তৎকালীন নতুন ক্ষেত্রে পূর্ববর্তী কাজের উপর ভিত্তি করে গড়ে তুলেছিল। উদাহরণ 5 দৈর্ঘ্যের চক্রটি একটি এস. আর. জি (5,2,0,1)। পিটারসেন গ্রাফটি একটি এস. আর. জি (10,3,0,1)। ক্লেবশ গ্রাফ একটি এস. আর. জি (16,5,0,2)। শ্রীখণ্ডে গ্রাফটি একটি এস. আর. জি (16,6,2,2) যা একটি দূরত্ব-ক্ষণস্থায়ী গ্রাফ নয়। n × n বর্গাকার রুকের গ্রাফ, অর্থাৎ, একটি ভারসাম্যপূর্ণ সম্পূর্ণ দ্বিদলীয় গ্রাফ Kn, n-এর লাইন গ্রাফ হল একটি srg (n2,2n−2, n−2,2)। এর জন্য পরামিতিগুলি শ্রীখণ্ডে গ্রাফের সাথে মিলে যায়, তবে দুটি গ্রাফ সমরূপ নয়। একটি সম্পূর্ণ গ্রাফের লাইন গ্রাফ হল একটি। চ্যাং গ্রাফগুলি এস. আর. জি (28,12,6,4), কে8-এর লাইন গ্রাফের মতোই, তবে এই চারটি গ্রাফ সমরূপ নয়। (s, t) ক্রমের প্রতিটি সাধারণীকৃত চতুর্ভুজ তার রেখাচিত্র হিসাবে একটি srg ((s + 1) (st + 1), s (t + 1), s-1, t + 1) দেয়। উদাহরণস্বরূপ, জিকিউ (2,4) তার লাইন গ্রাফ হিসাবে এসআরজি (27,10,1,5) দেয়। শ্লাফলি গ্রাফ একটি এস. আর. জি (27,16,10,8)। হফম্যান-সিঙ্গেলটন গ্রাফটি একটি এস. আর. জি (50,7,0,1)। সিমস-গিউয়ার্টজ গ্রাফটি একটি (56,10,0,2)। এম22 গ্রাফ বা মেসনার গ্রাফ একটি এস. আর. জি (77,16,0,4)। ব্রাউয়ার-হেমারের গ্রাফটি একটি এস. আর. জি (81,20,1,6)। হিগম্যান-সিমস গ্রাফটি একটি এস. আর. জি (100,22,0,6)। স্থানীয় ম্যাকলাফলিন গ্রাফ একটি এস. আর. জি (162,56,10,24)। ক্যামেরন গ্রাফটি একটি এস. আর. জি (239,30,9,3)। বার্লেক্যাম্প-ভ্যান লিন্ট-সিডেল গ্রাফটি একটি এস. আর. জি (243,22,1,2)। ম্যাকলাফলিন গ্রাফ একটি এস. আর. জি (275,112,30,56)। q ক্রমের পালে গ্রাফ হল একটি srg (q, (q−1)/2, (q−5)/4, (q−1)/4)। সবচেয়ে ছোট পেলি গ্রাফটি হল 5-চক্র (উপরে)। স্ব-পরিপূরক আর্ক-ট্রানজিটিভ গ্রাফগুলি দৃঢ়ভাবে নিয়মিত। একটি দৃঢ় নিয়মিত গ্রাফকে আদিম বলা হয় যদি গ্রাফ এবং এর পরিপূরক উভয়ই সংযুক্ত থাকে। উপরের সমস্ত গ্রাফ আদিম, অন্যথায় বা। কনওয়ের 99-গ্রাফ সমস্যা একটি এস. আর. জি (99,14,1,2) নির্মাণের জন্য জিজ্ঞাসা করে। এই পরামিতিগুলির সাথে একটি গ্রাফ বিদ্যমান কিনা তা অজানা, এবং জন হর্টন কনওয়ে এই সমস্যার সমাধানের জন্য $1000 পুরস্কারের প্রস্তাব দিয়েছিলেন। ত্রিভুজ-মুক্ত গ্রাফ λ = 0 সহ দৃঢ়ভাবে নিয়মিত গ্রাফগুলি ত্রিভুজ মুক্ত। 3 টিরও কম শীর্ষে সম্পূর্ণ গ্রাফ এবং সমস্ত সম্পূর্ণ দ্বিদলীয় গ্রাফ ছাড়াও, আগে তালিকাভুক্ত সাতটি (পেন্টাগন, পিটারসেন, ক্লেবশ, হফম্যান-সিঙ্গেলটন, গেইয়ার্টজ, মেসনার-এম22 এবং হিগম্যান-সিমস) শুধুমাত্র পরিচিত। জিওডেটিক গ্রাফ প্রতিটি দৃঢ় নিয়মিত গ্রাফ একটি জিওডেটিক গ্রাফ, একটি গ্রাফ যেখানে প্রতিটি দুটি শীর্ষে একটি অনন্য ওজনহীন সংক্ষিপ্ততম পথ থাকে। একমাত্র পরিচিত দৃঢ়ভাবে নিয়মিত গ্রাফগুলি হল যেখানে 0, তাই ত্রিভুজ-মুক্ত। এগুলিকে মুর গ্রাফ বলা হয় এবং নীচে আরও বিস্তারিতভাবে অনুসন্ধান করা হয়েছে। অন্যান্য পরামিতিগুলির সংমিশ্রণ যেমন (400,21,2,1) এখনও বাতিল করা হয়নি। একটি দৃঢ় নিয়মিত গ্রাফের বৈশিষ্ট্যগুলির উপর চলমান গবেষণা সত্ত্বেও, এটি আর বিদ্যমান কিনা বা এমনকি তাদের সংখ্যা সীমাবদ্ধ কিনা তা জানা যায় না। শুধুমাত্র প্রাথমিক ফলাফল জানা যায়, যা এই ধরনের গ্রাফের জন্য 1 হতে পারে না। দৃঢ়ভাবে নিয়মিত গ্রাফের বীজগাণিতিক বৈশিষ্ট্য পরামিতিগুলির মধ্যে মৌলিক সম্পর্ক একটি এস. আর. জি (v, k, λ, μ)-এর চারটি পরামিতি স্বাধীন নয়। তাদের অবশ্যই নিম্নলিখিত সম্পর্কটি মেনে চলতে হবেঃ উপরের সম্পর্কটি নিম্নরূপ একটি গণনা যুক্তির মাধ্যমে উদ্ভূত হয়েছেঃ গ্রাফের শীর্ষগুলি তিনটি স্তরে অবস্থিত বলে কল্পনা করুন। 0 স্তরে মূল হিসাবে যে কোনও শীর্ষ বেছে নিন। তারপর এর 'কে' প্রতিবেশীরা স্তর 1-এ থাকে এবং অন্যান্য সমস্ত শীর্ষ স্তর 2-এ থাকে। স্তর 1-এর ভার্টিসগুলি সরাসরি মূলের সাথে সংযুক্ত, তাই তাদের অবশ্যই মূলের সাথে সাধারণ λ অন্যান্য প্রতিবেশী থাকতে হবে, এবং এই সাধারণ প্রতিবেশীদের অবশ্যই স্তর 1-এর মধ্যে থাকতে হবে। যেহেতু প্রতিটি শীর্ষে ডিগ্রি k থাকে, তাই প্রতিটি স্তর 1 নোডের জন্য স্তর 2-এর শীর্ষগুলির সাথে সংযুক্ত হওয়ার জন্য প্রান্তগুলি অবশিষ্ট থাকে। অতএব, স্তর 1 এবং স্তর 2-এর মধ্যে প্রান্ত রয়েছে। স্তর 2-এর ভার্টিসগুলি সরাসরি মূলের সাথে সংযুক্ত নয়, তাই তাদের অবশ্যই মূলের সাথে সাধারণ প্রতিবেশী থাকতে হবে এবং এই সাধারণ প্রতিবেশীদের অবশ্যই স্তর 1-এ থাকতে হবে। স্তর 2-এ শীর্ষগুলি রয়েছে এবং প্রতিটি স্তর 1-এ মাইক্রো শীর্ষগুলির সাথে সংযুক্ত। অতএব স্তর 1 এবং স্তর 2-এর মধ্যে প্রান্তের সংখ্যা হল। স্তর 1 এবং স্তর 2-এর মধ্যে প্রান্তের জন্য দুটি অভিব্যক্তি সমান করে, সম্পর্কটি অনুসরণ করে। অ্যাডজ্যাসেন্সি ম্যাট্রিক্স সমীকরণগুলি ধরা যাক আমি আইডেন্টিটি ম্যাট্রিক্সকে নির্দেশ করি এবং J একের ম্যাট্রিক্সকে নির্দেশ করে, উভয় ম্যাট্রিক্স ক্রম v। একটি দৃঢ় নিয়মিত গ্রাফের অ্যাডজ্যাসেন্সি ম্যাট্রিক্স A দুটি সমীকরণকে সন্তুষ্ট করে। প্রথমতঃ যা নিয়মিততার প্রয়োজনীয়তার পুনর্বিবেচনা। এটি দেখায় যে k হল অল-ওয়ান আইগেনভেক্টরের সাথে সংলগ্ন ম্যাট্রিক্সের একটি আইগেনভ্যালু। দ্বিতীয়তঃ যা দৃঢ় নিয়মিততা প্রকাশ করে। বাম দিকের ij-th উপাদানটি i থেকে j পর্যন্ত দুই ধাপের পথের সংখ্যা দেয়। ডান দিকের প্রথম পদটি i থেকে i পর্যন্ত দুই ধাপের পথের সংখ্যা দেয়, যথা k প্রান্তগুলি বাইরে এবং পিছনে। দ্বিতীয় পদটি দুই ধাপের পথের সংখ্যা দেয় যখন আই এবং জে সরাসরি সংযুক্ত থাকে। তৃতীয় পদটি সংশ্লিষ্ট মান দেয় যখন i এবং j সংযুক্ত থাকে না। যেহেতু তিনটি কেস পারস্পরিক একচেটিয়া এবং সমষ্টিগতভাবে সম্পূর্ণ, তাই সহজ যোগাত্মক সমতা অনুসরণ করে। বিপরীতভাবে, একটি গ্রাফ যার সংলগ্নতা ম্যাট্রিক্স উপরের উভয় শর্তকে সন্তুষ্ট করে এবং যা একটি সম্পূর্ণ বা শূন্য গ্রাফ নয়, এটি একটি দৃঢ় নিয়মিত গ্রাফ। আইগেনভ্যালু এবং গ্রাফ বর্ণালী যেহেতু সংলগ্ন ম্যাট্রিক্স এ প্রতিসম, তাই এর আইগেনভেক্টরগুলি অর্থোগোনাল। আমরা ইতিমধ্যেই একটি আইগেনভেক্টর পর্যবেক্ষণ করেছি যার উপরে সবগুলিই গঠিত, যা আইগেনভ্যালু k-এর সঙ্গে সামঞ্জস্যপূর্ণ। অতএব অন্যান্য আইগেনভেক্টর x-কে অবশ্যই সন্তুষ্ট করতে হবে যেখানে J হল আগের মতোই সর্বজনীন ম্যাট্রিক্স। পূর্বে প্রতিষ্ঠিত সমীকরণটি গ্রহণ করুনঃ এবং উপরের সমীকরণটিকে আইগেনভেক্টর x দ্বারা গুণ করুনঃ সংশ্লিষ্ট আইগেনভ্যালু p কল করুন (গ্রাফ প্যারামিটারের সাথে বিভ্রান্ত হবেন না) এবং প্রতিস্থাপন করুন, এবংঃ x বাদ দিন এবং একটি দ্বিঘাত পেতে পুনর্বিন্যাস করুনঃ এটি দুটি অতিরিক্ত আইগেনভ্যালু দেয়। সুতরাং একটি দৃঢ় নিয়মিত ম্যাট্রিক্সের জন্য ঠিক তিনটি আইগেনভ্যালু রয়েছে। বিপরীতভাবে, শুধুমাত্র তিনটি আইগেনভ্যালু সহ একটি সংযুক্ত নিয়মিত গ্রাফ দৃঢ়ভাবে নিয়মিত। বেশিরভাগ নিয়মিত গ্রাফ সাহিত্যে পরিভাষা অনুসরণ করে, বৃহত্তর আইগেনভ্যালুটি গুণিতক f সহ r বলা হয় এবং ছোটটিকে গুণিতক g সহ s বলা হয়। যেহেতু সমস্ত আইগেনভ্যালুগুলির যোগফল সংলগ্ন ম্যাট্রিক্সের ট্রেস, যা এই ক্ষেত্রে শূন্য, তাই সংশ্লিষ্ট গুণিতক f এবং g গণনা করা যেতে পারেঃ আইগেনভ্যালু k-এর গুণিতক 1 রয়েছে। আইগেনভ্যালুতে বহুগুণ রয়েছে। আইগেনভ্যালুতে বহুগুণ রয়েছে। যেহেতু গুণগুলি অবশ্যই পূর্ণসংখ্যা হতে হবে, তাই তাদের অভিব্যক্তিগুলি v, k, μ এবং λ-এর মানগুলির উপর আরও সীমাবদ্ধতা প্রদান করে। দৃঢ়ভাবে নিয়মিত গ্রাফগুলির জন্য অসম গুণমান সহ পূর্ণসংখ্যা আইগেনভ্যালু রয়েছে। দৃঢ়ভাবে নিয়মিত গ্রাফগুলি যার জন্য প্রতিসম সম্মেলন ম্যাট্রিক্সের সাথে সংযোগের কারণে সম্মেলন গ্রাফ বলা হয়। তাদের প্যারামিটারগুলি কমে যায় তাদের আইগেনভ্যালুগুলি হল এবং, যার উভয় গুণই সমান। উপরন্তু, এই ক্ষেত্রে, v অবশ্যই ব্রুক-রিসার-চাওলা উপপাদ্যের সাথে সম্পর্কিত দুটি বর্গের যোগফলের সমান হতে হবে। আইগেনভ্যালু এবং তাদের গুণের আরও বৈশিষ্ট্যগুলি হলঃ, তাই আইগেনভ্যালু r এবং s সহ an দেওয়া হলে, এর পরিপূরকের আইগেনভ্যালু-1-s এবং-1-r থাকে। গুণের জন্য বিকল্প সমীকরণগুলি হল এবং ফ্রেম ভাগফল শর্তঃ একটি ফলস্বরূপ, যদি এবং শুধুমাত্র যদি কিছু ক্রমে। ক্রেইন শর্তঃ এবং পরম বদ্ধঃ এবং। নখবন্ধিতঃ যদি, তাহলে বা। যদি উপরের শর্তগুলি কোনও পরামিতিগুলির জন্য লঙ্ঘন করা হয়, তবে সেই পরামিতিগুলির জন্য কোনও দৃঢ় নিয়মিত গ্রাফ বিদ্যমান নেই। ব্রাউয়ার অস্তিত্বহীনতার কারণ সহ অস্তিত্ব বা অস্তিত্বহীনতার এই ধরনের তালিকা এখানে সংকলন করেছেন। হফম্যান-সিঙ্গেলটন উপপাদ্য যেমন উপরে উল্লেখ করা হয়েছে, আইগেনভ্যালুগুলির গুণফল দেওয়া হয়েছে যার দ্বারা অবশ্যই পূর্ণসংখ্যা হতে হবে। 1960 সালে, অ্যালান হফম্যান এবং রবার্ট সিঙ্গলটন মুর গ্রাফগুলিতে প্রয়োগ করার সময় এই অভিব্যক্তিগুলি পরীক্ষা করেছিলেন যার λ = 0 এবং μ = 1 রয়েছে। এই ধরনের গ্রাফগুলি ত্রিভুজ (অন্যথায় λ শূন্য অতিক্রম করবে) এবং চতুর্ভুজ (অন্যথায় μ 1 অতিক্রম করবে) থেকে মুক্ত, তাই তাদের পরিধি (ক্ষুদ্রতম চক্র দৈর্ঘ্য) 5। সমীকরণে λ এবং μ-এর মানগুলি প্রতিস্থাপন করলে, এটি দেখা যায় যে, এবং আইগেনভ্যালু গুণগুলি কমে যায়। যদি সংখ্যাটি শূন্য হয়, তবে সম্ভাবনাগুলি হলঃ k = 0 এবং v = 1 একটি শীর্ষ এবং কোনও প্রান্ত সহ একটি তুচ্ছ গ্রাফ দেয় এবং k = 2 এবং v = 5 5-ভার্টেক্স চক্র গ্রাফ দেয়, যা সাধারণত নিয়মিত পঞ্চভুজ হিসাবে আঁকা হয়। যদি হরটি একটি পূর্ণসংখ্যা t হয়, তাহলে এটি একটি নিখুঁত বর্গক্ষেত্র। প্রতিস্থাপনঃ যেহেতু উভয় পক্ষই পূর্ণসংখ্যা, তাই অবশ্যই একটি পূর্ণসংখ্যা হতে হবে, তাই t হল 15-এর একটি গুণক, অর্থাৎ। ফলস্বরূপঃ k = 1 এবং v = 2 একটি প্রান্ত দ্বারা যুক্ত দুটি শীর্ষের একটি তুচ্ছ গ্রাফ দেয়, k = 3 এবং v = 10 পিটারসেনের গ্রাফ দেয়, k = 7 এবং v = 50 হফম্যান-সিঙ্গেলটন গ্রাফ দেয়, যা এই বিশ্লেষণের সময় হফম্যান এবং সিঙ্গেলটন আবিষ্কার করেছিলেন, এবং k = 57 এবং v = 3250 একটি বিখ্যাত গ্রাফের পূর্বাভাস দেয় যা 1960 সাল থেকে আবিষ্কৃত হয়নি, বা এর অস্তিত্ব অস্বীকার করা হয়নি। হফম্যান-সিঙ্গেলটন উপপাদ্য বলে যে উপরে তালিকাভুক্ত গ্রাফগুলি ছাড়া কোনও দৃঢ় নিয়মিত ঘের-5 মুর গ্রাফ নেই। আরও দেখুন আংশিক জ্যামিতি সিডেল অ্যাডজাসেন্সি ম্যাট্রিক্স টু-গ্রাফ নোটস রেফারেন্স অ্যান্ড্রিস ব্রাউয়ার এবং হেন্ড্রিক ভ্যান মালডেগেম (2022), স্ট্রংলি রেগুলার গ্রাফ। কেমব্রিজঃ কেমব্রিজ ইউনিভার্সিটি প্রেস। । এ. ই. ব্রাউয়ার, এ. এম. কোহেন, এবং এ. নিউমেয়ার (1989), দূরত্ব নিয়মিত গ্রাফ। বার্লিন, নিউ ইয়র্কঃ স্প্রিঙ্গার-ভার্লাগ। , ক্রিস গডসিল এবং গর্ডন রয়লে (2004), বীজগাণিতিক গ্রাফ তত্ত্ব। নিউ ইয়র্কঃ স্প্রিংগার-ভার্লাগ। বাহ্যিক লিঙ্কগুলি এরিক ডব্লিউ. ওয়েইসস্টেইন, অসংখ্য উদাহরণ সহ ম্যাথওয়ার্ল্ড নিবন্ধ। গর্ডন রয়লে, বৃহত্তর গ্রাফ এবং পরিবারের তালিকা। অ্যান্ড্রিস ই. ব্রাউয়ার, দৃঢ়ভাবে নিয়মিত গ্রাফের পরামিতি। ব্রেন্ডন ম্যাককে, গ্রাফের কিছু সংগ্রহ। টেড স্পেন্স, সর্বাধিক 64টি শীর্ষে দৃঢ়ভাবে নিয়মিত গ্রাফ। গ্রাফ পরিবার বীজগাণিতিক গ্রাফ তত্ত্ব নিয়মিত গ্রাফ