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