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