Common graph
گراف تھیوری میں، جو ریاضی کا ایک شعبہ ہے، عام گرافوں کا تعلق انتہائی گراف تھیوری کی ایک شاخ سے ہے جو ہومومورفزم کثافت میں عدم مساوات سے متعلق ہے۔ موٹے طور پر، ایک عام گراف ہے اگر یہ "عام طور پر" ذیلی گراف کے طور پر ظاہر ہوتا ہے، اس لحاظ سے کہ کسی بھی گراف اور اس کی تکمیل میں نقلوں کی کل تعداد ایک ہی عمودی پر موجود تمام ممکنہ نقلوں کا ایک بڑا حصہ ہے۔ بدیہی طور پر، اگر اس کی چند کاپیاں ہیں، تو اس کی تکمیل میں اس کی تلافی کے لیے اس کی بہت سی کاپیاں ہونی چاہئیں۔ عام گرافوں کا ہومومورفزم کثافت کی عدم مساوات سے نمٹنے والے دیگر گراف تصورات سے گہرا تعلق ہے۔ مثال کے طور پر، عام گراف سڈورنکو گراف کا ایک زیادہ عام معاملہ ہے۔ تعریف ایک گراف عام ہے اگر عدم مساوات: کسی بھی گرافون کے لیے ہو، جہاں کناروں کی تعداد ہے اور ہومومورفزم کثافت ہے۔ عدم مساوات سخت ہے کیونکہ نچلی حد ہمیشہ اس وقت تک پہنچ جاتی ہے جب مستقل گرافون ہوتا ہے۔ تعریف کی تشریحات گراف کے لیے، ہمارے پاس اور اس سے وابستہ گرافون کے لیے، چونکہ تکمیل سے وابستہ گرافون ہے۔ لہذا، یہ فارمولا ہمیں بہت ہی غیر رسمی انترجشتھان فراہم کرتا ہے کہ ہم کافی قریب سے تخمینہ لگائیں، چاہے اس کا مطلب کچھ بھی ہو، اور "لگ بھگ" گراف میں گراف کی لیبل شدہ کاپیوں کے تقریبا حصے کے طور پر دیکھیں۔ پھر، ہم فرض کر سکتے ہیں کہ مقدار تقریبا ہے اور مؤخر الذکر کی تشریح ان اور کی نقلوں کی مشترکہ تعداد کے طور پر کر سکتے ہیں۔ لہذا، ہم دیکھتے ہیں کہ یہ برقرار ہے۔ اس کا مطلب یہ ہے کہ عام گراف عام طور پر ذیلی گراف کے طور پر ظاہر ہوتا ہے۔ دوسرے لفظوں میں، اگر ہم کناروں اور غیر کناروں کو ایک ہی عمودی پر مکمل گراف کے کناروں کے 2 رنگ کے طور پر سوچتے ہیں، تو ان کی تمام ممکنہ نقلوں کا کم از کم حصہ یک رنگ ہوتا ہے۔ نوٹ کریں کہ ایرڈس-رینی بے ترتیب گراف میں ہر کنارے کے ساتھ امکانات کے ساتھ تیار کیا گیا ہے، ہر گراف ہومومورفزم میں یک رنگ ہونے کا امکان ہوتا ہے۔ لہذا، عام گراف ایک ایسا گراف ہے جہاں یہ گراف پر گراف کے یک رنگ ذیلی گراف کے طور پر اپنی کم از کم تعداد میں ظاہری شکل حاصل کرتا ہے۔ عمومی ہومومورفزم کثافت کا استعمال کرتے ہوئے مندرجہ بالا تعریف کو اس طرح سے سمجھا جا سکتا ہے۔ مثال جیسا کہ اوپر بیان کیا گیا ہے، تمام سڈورنکو گراف عام گراف ہیں۔ لہذا، کوئی بھی معروف سڈورنکو گراف ایک عام گراف کی مثال ہے، اور، خاص طور پر، یکساں لمبائی کے چکر عام ہیں۔ تاہم، یہ محدود مثالیں ہیں کیونکہ تمام سڈورنکو گراف دو طرفہ گراف ہیں جبکہ غیر دو طرفہ عام گراف موجود ہیں، جیسا کہ ذیل میں دکھایا گیا ہے۔ مثلث گراف غیر دو طرفہ عام گراف کی ایک سادہ مثال ہے۔ 4 عمودی حصوں پر مکمل گراف کے کنارے کو ہٹا کر حاصل کیا گیا گراف عام ہے۔ غیر مثال: ایک وقت کے لیے یہ خیال کیا جاتا تھا کہ تمام گراف مشترک ہیں۔ تاہم، یہ پتہ چلتا ہے کہ یہ عام نہیں ہے۔ خاص طور پر، عام نہیں ہے حالانکہ یہ عام ہے۔ ثبوت سڈورنکو گراف عام ہیں ایک گراف سڈورنکو گراف ہے اگر یہ تمام گرافون کے لیے مطمئن ہو۔ اس صورت میں،. مزید برآں، جو ہومومورفزم ڈینسٹی کی تعریف سے ملتا ہے۔ فنکشن کے لیے جینسن کی عدم مساوات کے ساتھ اس کا امتزاج: اس طرح، مشترکہ گراف کے لیے شرائط پوری ہوتی ہیں۔ مثلث گراف عام ہے متغیرات کے درمیان ہم آہنگی کے لیے لازمی اظہار کو وسعت دیں اور اسے مدنظر رکھیں: اظہار میں ہر اصطلاح کو چھوٹے گرافوں کی ہومومورفزم کثافت کے لحاظ سے لکھا جا سکتا ہے۔ ہومومورفزم ڈینسٹیز کی تعریف کے مطابق: جہاں ایک حصے پر ورٹیکس اور دوسرے پر ورٹیکس پر مکمل دو طرفہ گراف کی نشاندہی کرتا ہے۔ یہ اس طرح ہے: متغیرات کے درمیان ہم آہنگی کی بدولت اس سے متعلق ہو سکتا ہے اور: جہاں آخری مرحلہ لازمی کاچی-شوارز عدم مساوات کی پیروی کرتا ہے۔ آخر میں: یہ ثبوت نظریہ 1 کے مسلسل ینالاگ کو "کسی بھی پارٹی میں جاننے والوں اور اجنبیوں کے سیٹوں پر" میں لینے سے حاصل کیا جا سکتا ہے۔ سڈورنکو کے قیاس آرائی حوالہ جات گراف خاندانوں کا ایکسٹریم گراف تھیوری بھی دیکھیں۔