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