Forcing graph
গ্রাফ তত্ত্বে, একটি বল প্রয়োগকারী গ্রাফ হল এমন একটি গ্রাফ যার ঘনত্ব নির্ধারণ করে যে একটি গ্রাফ ক্রম আধা-এলোমেলো কিনা। 1989 সালে চুং, গ্রাহাম এবং উইলসন এই শব্দটি প্রথম উদ্ভাবন করেন এবং গ্রাফ ক্রমের ছদ্মবেশীতা অধ্যয়নে জোরপূর্বক গ্রাফ গুরুত্বপূর্ণ ভূমিকা পালন করে। সংজ্ঞাগুলি আসুন, যা সাবগ্রাফ ঘনত্ব হিসাবে পরিচিত (বিশেষত, এর প্রান্তের ঘনত্ব)। গ্রাফের একটি ক্রমকে আধা-এলোমেলো বলা হয় যদি, সমস্ত গ্রাফের জন্য, প্রান্তের ঘনত্ব কিছুর কাছে পৌঁছায় এবং বৃদ্ধির সাথে সাথে পৌঁছায়, যেখানে প্রান্তের সংখ্যা থাকে। স্বজ্ঞাতভাবে, এর অর্থ হল একটি প্রদত্ত প্রান্ত ঘনত্ব সহ একটি গ্রাফ ক্রমের গ্রাফ সমরূপতার সংখ্যা রয়েছে যা একটি এলোমেলো গ্রাফ ক্রমে আশা করা যায়। একটি গ্রাফকে বলপ্রয়োগ বলা হয় যদি সমস্ত গ্রাফ ক্রমের জন্য যেখানে অসীমের দিকে যায়, তা যদি কাছে আসে তবে তা আধা-এলোমেলো হয়। অন্য কথায়, একটি একক গ্রাফের সমরূপতার ঘনত্ব পরীক্ষা করে কেউ যাচাই করতে পারে যে গ্রাফের একটি ক্রম আধা-এলোমেলো। গ্রাফনের ভাষা ব্যবহার করে গ্রাফ জোর করার একটি দ্বিতীয় সংজ্ঞা রয়েছে। আনুষ্ঠানিকভাবে, একটি গ্রাফকে ফোর্সিং বলা হয় যদি প্রতিটি গ্রাফন ধ্রুবক হয়। স্বজ্ঞাতভাবে, এটি বোধগম্য যে এই সংজ্ঞাগুলি সম্পর্কিত। ধ্রুবক গ্রাফনটি এরদোস-রেনি র্যান্ডম গ্রাফের প্রতিনিধিত্ব করে, তাই কেউ আশা করতে পারে যে এটি আধা-র্যান্ডম গ্রাফের সাথে ঘনিষ্ঠ সম্পর্ক রাখবে। প্রকৃতপক্ষে, এই সংজ্ঞাগুলি সমতুল্য। উদাহরণস্বরূপ, বিবেচনা করার মতো প্রথম বল প্রয়োগকারী গ্রাফটি হল 4-চক্র, কারণ এটি আধা-যাদৃচ্ছিকতার অন্যান্য অবস্থার সাথে ঘনিষ্ঠ সম্পর্ক বহন করে। চুং, গ্রাহাম এবং উইলসন একই গবেষণাপত্রে দেখিয়েছিলেন যে ফর্মের প্রতিটি জোড় চক্র এবং সম্পূর্ণ দ্বিদলীয় গ্রাফ জোরালো। কনলন, ফক্স এবং সুদাকভ এই শেষ ফলাফলটি প্রসারিত করে এক অংশে দুটি শীর্ষ সহ সমস্ত দ্বিদলীয় গ্রাফ অন্তর্ভুক্ত করেন যা অন্য অংশে সম্পূর্ণ হয়। গ্রাফের একটি পরিবার যখনই সকলের কাছে আসে তখন জোর করে অর্ধ-এলোমেলো হয়। জোরপূর্বক গ্রাফগুলি চিহ্নিত করার চেয়ে জোরপূর্বক পরিবারগুলিকে চিহ্নিত করা অনেক বেশি চ্যালেঞ্জিং, তাই খুব কমই জানা যায়। পরিচিত বল প্রয়োগকারী পরিবারগুলির মধ্যে রয়েছেঃ, যেখানে একটি ধনাত্মক পূর্ণসংখ্যা;, যেখানে এবং সঙ্গে ধনাত্মক পূর্ণসংখ্যা;, যেখানে; এবং, যেখানে এবং। জোরপূর্বক অনুমান 2004 সালে স্কোকান এবং থোমা দ্বারা জোরপূর্বক অনুমান করা হয়েছিল এবং 2010 সালে কনলন, ফক্স এবং সুদাকভ দ্বারা আনুষ্ঠানিক করা হয়েছিল। এটি গ্রাফগুলিকে জোর করার জন্য একটি বৈশিষ্ট্য প্রদান করে, যা নিম্নরূপ আনুষ্ঠানিক করা হয়েছেঃ এই দাবির একটি দিক সুপরিচিত। চুং, গ্রাহাম এবং উইলসন দেখিয়েছেন যে যদি একটি গ্রাফের একটি বিজোড় চক্র থাকে তবে এটি জোর করা যায় না, তাই যদি একটি গ্রাফ জোর দেয় তবে এটি অবশ্যই দ্বিদলীয় হতে হবে। এছাড়াও, কনলন, ফক্স এবং সুদাকভ যুক্তি দিয়েছিলেন যে প্রতিটি বনের জন্য প্রায় নিয়মিত (এবং অগত্যা আধা-এলোমেলো নয়) গ্রাফ সিকোয়েন্স থাকে। সুতরাং, একটি ফোর্সিং গ্রাফ অবশ্যই দ্বিদলীয় হতে হবে এবং কমপক্ষে একটি চক্র থাকতে হবে। অন্য দিকটি এখনও প্রমাণিত হয়নি, তবে এই দুটি বৈশিষ্ট্য নেই এমন কোনও জোরপূর্বক গ্রাফ পাওয়া যায়নি। জোরপূর্বক অনুমানটি সিডোরেঙ্কোর অনুমানকেও বোঝায়, যা ক্ষেত্রের একটি দীর্ঘস্থায়ী অনুমান। এটি জানা যায় যে সমস্ত বল প্রয়োগকারী গ্রাফগুলি সিডোরেঙ্কো, তাই যদি বল প্রয়োগকারী অনুমানটি সত্য হয়, তবে কমপক্ষে একটি চক্র সহ সমস্ত দ্বিদলীয় গ্রাফগুলি সিডোরেঙ্কো হবে। যেহেতু গাছগুলি সিডোরেঙ্কো, তাই সমস্ত দ্বিদলীয় গ্রাফ সিডোরেঙ্কো হবে। তথ্যসূত্র গ্রাফ পরিবার