Symmetric graph
گراف تھیوری کے ریاضیاتی میدان میں، گراف ہم آہنگ (یا آرک ٹرانزیکٹو) ہوتا ہے اگر، ملحقہ عمودی کے کسی بھی دو جوڑے کو دیکھتے ہوئے، اس میں ایک آٹومورفزم ہوتا ہے اور دوسرے لفظوں میں، ایک گراف ہم آہنگ ہوتا ہے اگر اس کا آٹومورفزم گروپ ملحقہ عمودی کے ترتیب شدہ جوڑوں پر عارضی طور پر کام کرتا ہے (یعنی کناروں پر جسے سمت سمجھا جاتا ہے)۔ اس طرح کے گراف کو بعض اوقات-ٹرانزیکٹو یا فلیگ ٹرانزیٹو بھی کہا جاتا ہے۔ تعریف کے مطابق (نظر انداز کرنا اور)، الگ تھلگ عمودی کے بغیر ایک سمیٹرک گراف بھی ورٹیکس ٹرانزیکٹو ہونا چاہیے۔ چونکہ اوپر کی تعریف ایک کنارے سے دوسرے کنارے کا نقشہ بناتی ہے، اس لیے ایک سمیٹرک گراف بھی ایج ٹرانزیکٹو ہونا چاہیے۔ تاہم، ایک ایج ٹرانزیٹیو گراف کو ہم آہنگ ہونے کی ضرورت نہیں ہے، کیونکہ یہ نقشہ بنا سکتا ہے، لیکن نہیں۔ اسٹار گراف ورٹیکس ٹرانزیکٹو یا سمیٹرک ہوئے بغیر ایج ٹرانزیکٹو ہونے کی ایک سادہ مثال ہیں۔ مزید مثال کے طور پر، نیم ہم آہنگ گراف ایج ٹرانزیکٹو اور باقاعدہ ہوتے ہیں، لیکن ورٹیکس ٹرانزیکٹو نہیں ہوتے۔ اس طرح ہر جڑا ہوا سمیٹرک گراف ورٹیکس-ٹرانزیٹیو اور ایج-ٹرانزیٹیو دونوں ہونا چاہیے، اور اس کے برعکس عجیب ڈگری کے گراف کے لیے درست ہے۔ تاہم، یکساں ڈگری کے لیے، جڑے ہوئے گراف موجود ہیں جو ورٹیکس-ٹرانزیٹیو اور ایج-ٹرانزیٹیو ہیں، لیکن ہم آہنگ نہیں ہیں۔ اس طرح کے گراف کو ہاف ٹرانزیکٹو کہا جاتا ہے۔ سب سے چھوٹا جڑا ہوا نصف منتقلی گراف ہولٹ کا گراف ہے، جس کی ڈگری 4 اور 27 عمودی ہیں۔ الجھن کی بات یہ ہے کہ کچھ مصنفین "سمیٹرک گراف" کی اصطلاح استعمال کرتے ہیں جس کا مطلب ایک ایسا گراف ہے جو آرک-ٹرانزیکٹو گراف کے بجائے ورٹیکس-ٹرانزیکٹو اور ایج-ٹرانزیکٹو ہے۔ اس طرح کی تعریف میں نصف عارضی گراف شامل ہوں گے، جنہیں اوپر کی تعریف کے تحت خارج کر دیا گیا ہے۔ فاصلہ-عارضی گراف وہ ہے جہاں ملحقہ عمودی کے جوڑوں پر غور کرنے کے بجائے (یعنی۔ عمودی طور پر 1 کے فاصلے پر)، تعریف عمودی طور پر دو جوڑوں کا احاطہ کرتی ہے، ہر ایک ایک ہی فاصلے پر ہے۔ تعریف کے مطابق اس طرح کے گراف خود بخود ہم آہنگ ہوتے ہیں۔ A کی تعریف عمودی کے سلسلے کے طور پر کی گئی ہے، اس طرح کہ ترتیب میں کوئی بھی دو مسلسل عمودی ملحقہ ہوں، اور کسی بھی بار بار عمودی کے درمیان 2 قدم سے زیادہ کا فاصلہ ہو۔ گراف ایک ایسا گراف ہے جس پر آٹومورفزم گروپ عارضی طور پر کام کرتا ہے، لیکن اس پر نہیں۔ چونکہ صرف کنارے ہوتے ہیں، ڈگری 3 یا اس سے زیادہ کا ہر سمیٹرک گراف کچھ کے لیے ہونا چاہیے، اور کی قدر سمیٹرک گراف کی مزید درجہ بندی کے لیے استعمال کی جا سکتی ہے۔ مکعب، مثال کے طور پر ہے۔ نوٹ کریں کہ روایتی طور پر "سمیٹرک گراف" کی اصطلاح "غیر متناسب گراف" کی اصطلاح کی تکمیل نہیں ہے، کیونکہ مؤخر الذکر ایک ایسے گراف کی طرف اشارہ کرتا ہے جس میں کوئی غیر معمولی سمیٹریز نہیں ہوتی ہیں۔ مثال کے طور پر کسی بھی تعداد میں عمودی کے لیے متناسب گراف کے دو بنیادی خاندان سائیکل گراف (ڈگری 2 کے) اور مکمل گراف ہیں۔ مزید ہم آہنگ گراف باقاعدہ اور کواسیریگولر پولی ہیڈرا کے عمودی اور کناروں سے تشکیل پاتے ہیں: مکعب، آکٹا ہیڈرون، آئکوساہیڈرون، ڈوڈیکاہیڈرون، کیوبکٹی ہیڈرون، اور آئکوسیڈوڈیکاہیڈرون۔ کیوب کی n طول و عرض تک توسیع ہائپر کیوب گراف (2n عمودی اور ڈگری n کے ساتھ) دیتی ہے۔ اسی طرح آکٹا ہیڈرون کی n طول و عرض تک توسیع کراس پولی ٹاپس کے گراف دیتی ہے، گراف کے اس خاندان (2n عمودی اور ڈگری 2n-2 کے ساتھ) کو بعض اوقات کاک ٹیل پارٹی گراف کہا جاتا ہے-وہ کناروں کے ایک سیٹ کے ساتھ مکمل گراف ہوتے ہیں جو ایک کامل مماثلت کو ہٹا دیتے ہیں۔ متوازی گرافوں کے اضافی خاندان جن میں عمودی 2n کی یکساں تعداد ہوتی ہے، یکساں طور پر تقسیم شدہ مکمل دو طرفہ گراف Kn، n اور 2n عمودی پر تاج گراف ہوتے ہیں۔ بہت سے دوسرے ہم آہنگ گرافوں کو گردشی گرافوں کے طور پر درجہ بند کیا جا سکتا ہے (لیکن سبھی نہیں)۔ ریڈو گراف ایک سمیٹرک گراف کی مثال بناتا ہے جس میں لامحدود بہت سے عمودی اور لامحدود ڈگری کیوبک سمیٹرک گراف ہوتے ہیں۔ سمیٹری کی حالت کو اس پابندی کے ساتھ جوڑنا کہ گراف کیوبک ہوں (یعنی۔ تمام عمودی حصوں میں ڈگری 3 ہوتی ہے) کافی مضبوط حالت پیدا کرتی ہے، اور اس طرح کے گراف درج کیے جانے کے لیے کافی کم ہوتے ہیں۔ ان سب کی عمودی تعداد یکساں ہوتی ہے۔ فوسٹر مردم شماری اور اس کی توسیعات ایسی فہرستیں فراہم کرتی ہیں۔ فوسٹر مردم شماری 1930 کی دہائی میں رونالڈ ایم فوسٹر نے شروع کی تھی جب وہ بیل لیبز میں ملازمت کر رہے تھے، اور 1988 میں (جب فوسٹر 92 سال کے تھے) اس وقت کی موجودہ فوسٹر مردم شماری (512 عمودی تک کے تمام کیوبک سمیٹرک گراف کی فہرست) کتابی شکل میں شائع کی گئی تھی۔ فہرست میں پہلی تیرہ اشیاء کیوبک سمیٹرک گراف ہیں جن میں 30 عمودی تک ہیں (ان میں سے دس فاصلہ-منتقلی بھی ہیں ؛ مستثنیات جیسا کہ اشارہ کیا گیا ہے): دیگر معروف کیوبک سمیٹرک گراف ڈائیک گراف، فوسٹر گراف اور بگز سمتھ گراف ہیں۔ فوسٹر گراف اور بگز سمتھ گراف کے ساتھ اوپر درج دس فاصلہ-منتقلی گراف، واحد کیوبک فاصلہ-منتقلی گراف ہیں۔ خصوصیات سمیٹرک گراف کی ورٹیکس کنیکٹیویٹی ہمیشہ ڈگری d کے برابر ہوتی ہے۔ اس کے برعکس، عام طور پر ورٹیکس ٹرانزیکٹو گراف کے لیے، ورٹیکس کنیکٹیویٹی نیچے 2 (d + 1)/3 سے محدود ہوتی ہے۔ ڈگری 3 یا اس سے زیادہ کے ٹی-ٹرانزیکٹو گراف کا گرتھ کم از کم 2 (ٹی-1) ہوتا ہے۔ تاہم، t ≤ 8 کے لیے ڈگری 3 یا اس سے زیادہ کے کوئی محدود t-ٹرانزیکٹو گراف نہیں ہیں۔ ڈگری کے بالکل 3 ہونے کی صورت میں (کیوبک سمیٹرک گراف)، t ≤ 6 کے لیے کوئی نہیں ہے۔ نام شدہ گرافوں کی الجبرائی گراف تھیوری گیلری باقاعدہ نقشہ حوالہ جات بیرونی روابط کیوبک سمیٹرک گراف (دی فوسٹر مردم شماری) بھی دیکھیں۔ 768 عمودی تک کے تمام کیوبک سمیٹرک گرافوں کے لیے ڈیٹا فائلیں، اور 1000 عمودی تک کے کچھ کیوبک گراف۔ گورڈن روئل، فروری 2001 میں اپ ڈیٹ کیا گیا، بازیافت کیا گیا 2009-04-18۔ 10000 چوٹیوں تک کے سہ رخی (کیوبک) سمیٹرک گراف۔ مارسٹن کونڈر، 2011۔ الجبرائی گراف تھیوری گراف خاندان باقاعدہ گراف