Tournament (graph theory)
ٹورنامنٹ ایک ہدایت شدہ گراف (ڈیگراف) ہے جو ایک غیر ہدایت شدہ مکمل گراف میں ہر کنارے کے لیے ایک سمت تفویض کر کے حاصل کیا جاتا ہے۔ یعنی، یہ ایک مکمل گراف کی سمت ہے، یا مساوی طور پر ایک ہدایت شدہ گراف ہے جس میں مختلف عمودی کا ہر جوڑا دو ممکنہ سمتوں میں سے کسی ایک کے ساتھ ایک سمت والے کنارے (جسے اکثر آرک کہا جاتا ہے) سے جڑا ہوتا ہے۔ ٹورنامنٹ کی بہت سی اہم خصوصیات کی تحقیقات سب سے پہلے ایچ جی لینڈو نے 2006 میں مرغیوں کے جھنڈوں میں غلبہ کے تعلقات کو ماڈل بنانے کے لیے کی تھی۔ ٹورنامنٹ کے موجودہ استعمال میں دیگر چیزوں کے علاوہ ووٹنگ تھیوری اور سوشل چوائس تھیوری کا مطالعہ شامل ہے۔ نام کا ٹورنامنٹ راؤنڈ رابن ٹورنامنٹ کے نتیجے کے طور پر اس طرح کے گراف کی تشریح سے شروع ہوتا ہے جس میں ہر کھلاڑی کا مقابلہ ہر دوسرے کھلاڑی سے بالکل ایک بار ہوتا ہے، اور جس میں کوئی ڈرا نہیں ہوتا ہے۔ ٹورنامنٹ کے ڈیگراف میں، عمودی حصے کھلاڑیوں سے مطابقت رکھتے ہیں۔ کھلاڑیوں کی ہر جوڑی کے درمیان کنارے کا رخ فاتح سے ہارنے والے تک ہوتا ہے۔ اگر کھلاڑی کھلاڑی کو مارتا ہے، تو کہا جاتا ہے کہ غالب ہوتا ہے۔ اگر ہر کھلاڑی دوسرے کھلاڑیوں کی ایک ہی تعداد کو شکست دیتا ہے (انڈیگری = آؤٹ ڈگری)، تو ٹورنامنٹ کو باقاعدہ کہا جاتا ہے۔ راستے اور سائیکل ٹورنامنٹ کا ایک اور بنیادی نتیجہ یہ ہے کہ ہر مضبوطی سے جڑے ہوئے ٹورنامنٹ میں ہیملٹنین سائیکل ہوتا ہے۔ زیادہ مضبوطی سے، ہر مضبوطی سے جڑا ہوا ٹورنامنٹ ورٹیکس پینسیکلک ہوتا ہے: ہر ورٹیکس کے لیے، اور ٹورنامنٹ میں تین سے لے کر عمودی تعداد تک کی حد میں، لمبائی کا ایک چکر ہوتا ہے۔ ایک ٹورنامنٹ مضبوطی سے جڑا ہوا ہے اگر کے عمودی حصوں کے ہر سیٹ کے لیے، مضبوطی سے جڑا ہوا ہے۔ اگر ٹورنامنٹ 4-مضبوطی سے جڑا ہوا ہے، تو عمودی کے ہر جوڑے کو ہیملٹنین راستے سے جوڑا جا سکتا ہے۔ مضبوط طور پر جڑے ہوئے ٹورنامنٹ کے زیادہ تر آرکس کے ہر سیٹ کے لیے، ہمارے پاس ہیملٹنین سائیکل ہے۔ اس نتیجے میں توسیع کی گئی۔ ٹرانزیٹیویٹی ایک ایسا ٹورنامنٹ جس میں اور جسے ٹرانزیٹیو کہا جاتا ہے۔ دوسرے لفظوں میں، ایک عارضی ٹورنامنٹ میں، عمودی حصے (سختی سے) کنارے کے تعلق کے مطابق مکمل طور پر ترتیب دیے جا سکتے ہیں، اور کنارے کا تعلق رسائی کے برابر ہوتا ہے۔ مساوی حالات عمودی مقابلوں کے لیے درج ذیل بیانات مساوی ہیں: عارضی ہے۔ ایک سخت کل آرڈر ہے۔ ایسائکلک ہے۔ لمبائی 3 کے چکر پر مشتمل نہیں ہے۔ اسکور کی ترتیب (آؤٹ ڈگریوں کا مجموعہ) ہے۔ بالکل ایک ہیملٹنین راستہ ہے۔ رمسی تھیوری ٹرانزیٹو ٹورنامنٹ رمسی تھیوری میں ایک کردار ادا کرتے ہیں جو غیر ہدایت شدہ گرافوں میں گروہوں کے مترادف ہے۔ خاص طور پر، عمودی پر ہر ٹورنامنٹ عمودی پر ایک عارضی ذیلی ٹورنامنٹ پر مشتمل ہوتا ہے۔ ثبوت آسان ہے: اس ذیلی ٹورنامنٹ کا حصہ بننے کے لیے کسی بھی ایک سرے کا انتخاب کریں، اور باقی ذیلی ٹورنامنٹ کو یا تو آنے والے پڑوسیوں کے سیٹ پر یا باہر جانے والے پڑوسیوں کے سیٹ پر، جو بھی بڑا ہو، بار بار بنائیں۔ مثال کے طور پر، سات عمودی پر ہونے والے ہر ٹورنامنٹ میں تھری ورٹیکس ٹرانزیٹیو سب ٹورنامنٹ ہوتا ہے ؛ سات عمودی پر ہونے والے پیلے ٹورنامنٹ سے پتہ چلتا ہے کہ اس کی سب سے زیادہ ضمانت دی جا سکتی ہے۔ تاہم، ظاہر ہوا کہ یہ حد کچھ بڑی اقدار کے لیے سخت نہیں ہے۔ یہ ثابت کیا کہ سائز کے عارضی ذیلی ٹورنامنٹ کے بغیر عمودی پر ٹورنامنٹ ہوتے ہیں ان کا ثبوت ایک گنتی دلیل کا استعمال کرتا ہے: ان طریقوں کی تعداد جو ایک عنصر عارضی ٹورنامنٹ لیبل والے عمودی پر ایک بڑے ٹورنامنٹ کے ذیلی ٹورنامنٹ کے طور پر ہو سکتا ہے اور جب اس سے بڑا ہوتا ہے، تو یہ تعداد بہت کم ہوتی ہے جو لیبل والے عمودی کے ایک ہی سیٹ پر مختلف ٹورنامنٹس میں سے ہر ایک کے اندر عارضی ٹورنامنٹ کے انعقاد کی اجازت دیتی ہے۔ متضاد ٹورنامنٹ ایک کھلاڑی جو تمام کھیل جیتتا ہے وہ فطری طور پر ٹورنامنٹ کا فاتح ہوگا۔ تاہم، جیسا کہ غیر عارضی ٹورنامنٹس کا وجود ظاہر کرتا ہے، ہو سکتا ہے کہ ایسا کھلاڑی نہ ہو۔ ایک ٹورنامنٹ جس کے لیے ہر کھلاڑی کم از کم ایک گیم ہار جاتا ہے اسے 1-پیراڈوکسکل ٹورنامنٹ کہا جاتا ہے۔ زیادہ عام طور پر، ایک ٹورنامنٹ کو-پیراڈوکسکل کہا جاتا ہے اگر اس کے ہر عنصر کے ذیلی سیٹ کے لیے اس طرح کا ایک ورٹیکس ہو کہ سب کے لیے ہو۔ ممکنہ طریقہ کار کے ذریعے، پال ایرڈس نے دکھایا کہ کسی بھی مقررہ قیمت کے لیے، اگر، تو تقریبا ہر ٹورنامنٹ-پیراڈوکسکل ہے۔ دوسری طرف، ایک آسان دلیل سے پتہ چلتا ہے کہ کسی بھی پیراڈوکسکل ٹورنامنٹ میں کم از کم کھلاڑی ہونے چاہئیں، جسے ایسٹر اور جارج زیکیرس (1965) نے بہتر بنایا تھا۔ گراہم اور اسپینسر (1971) کے ذریعہ کھلاڑیوں کے ساتھ پیراڈوکسکل ٹورنامنٹس کی ایک واضح تعمیر ہے یعنی پیلے ٹورنامنٹ۔ کنڈینسیشن کسی بھی ٹورنامنٹ کا کنڈینسیشن خود ایک عارضی ٹورنامنٹ ہوتا ہے۔ اس طرح، ان ٹورنامنٹس کے لیے بھی جو عارضی نہیں ہیں، ٹورنامنٹ کے مضبوطی سے جڑے ہوئے اجزاء کو مکمل طور پر ترتیب دیا جا سکتا ہے۔ اسکور سیکوینس اور اسکور سیٹ ٹورنامنٹ کا اسکور سیکوینس ٹورنامنٹ کے عمودی حصوں کی آؤٹ ڈگری کی غیر بڑھتی ہوئی ترتیب ہے۔ ٹورنامنٹ کا اسکور سیٹ انٹیجرز کا مجموعہ ہوتا ہے جو اس ٹورنامنٹ میں عمودی ڈگریوں سے باہر ہوتے ہیں۔ لینڈو کا نظریہ (1953) انٹیجرز کی ایک غیر گھٹتی ہوئی ترتیب ایک اسکور کی ترتیب ہے اگر اور صرف اس صورت میں: سائز کے مختلف اسکور کے سلسلے کی تعداد ہو۔ ترتیب اس طرح شروع ہوتی ہے: 1، 1، 1، 2، 4، 9، 22، 59، 167، 490، 1486، 4639، 14805، 48107،۔ ونسٹن اور کلیٹ مین نے ثابت کیا کہ کافی بڑے n کے لیے: جہاں تکاکس نے بعد میں کچھ معقول لیکن غیر ثابت شدہ مفروضوں کا استعمال کرتے ہوئے دکھایا، کہ جہاں یہ ایک ساتھ مل کر ثبوت فراہم کرتے ہیں کہ: یہاں ایک غیر علامتی طور پر تنگ باؤنڈ کی نشاندہی ہوتی ہے۔ یاؤ نے دکھایا کہ غیر منفی انٹیجرز کا ہر غیر خالی سیٹ کسی ٹورنامنٹ کے لیے مقرر کردہ اسکور ہوتا ہے۔ اکثریت کے تعلقات سماجی انتخاب کے نظریہ میں، ٹورنامنٹ قدرتی طور پر ترجیحی پروفائلز کے اکثریت کے تعلقات کے طور پر پیدا ہوتے ہیں۔ آئیے متبادلات کا ایک محدود مجموعہ بنیں، اور لکیری آرڈرز کی فہرست پر غور کریں۔ ہم ہر آرڈر کی تشریح ووٹر کی ترجیحی درجہ بندی کے طور پر کرتے ہیں۔ اس کے بعد اوور کے (سخت) اکثریت کے تعلق کی وضاحت کی جاتی ہے تاکہ اگر اور صرف اس صورت میں جب ووٹرز کی اکثریت پسند کرے، یعنی۔ اگر ووٹرز کی تعداد عجیب ہے، تو اکثریت کا رشتہ ورٹیکس سیٹ پر ٹورنامنٹ کا غلبہ رشتہ بناتا ہے۔ میک گاروے کے ایک لیما کے ذریعہ، عمودی طور پر ہر ٹورنامنٹ کو زیادہ تر ووٹرز کے اکثریتی تعلق کے طور پر حاصل کیا جا سکتا ہے۔ سٹیرنز اور ایرڈس اینڈ موزر کے نتائج نے بعد میں یہ ثابت کیا کہ ہر ٹورنامنٹ کو عمودی طور پر راغب کرنے کے لیے ووٹرز کی ضرورت ہوتی ہے۔ لاسلیئر (1997) اس بات کا مطالعہ کرتا ہے کہ عمودی حصوں کے ایک سیٹ کو ٹورنامنٹ کے "فاتحین" کا مجموعہ کس معنی میں کہا جا سکتا ہے۔ یہ پولیٹیکل سائنس میں اس بات کا مطالعہ کرنے کے لیے مفید ثابت ہوا کہ سیاسی معیشت کے رسمی نمونوں میں، جمہوری عمل کا نتیجہ کیا ہو سکتا ہے۔ اورینٹڈ گراف پیلے ٹورنامنٹ سمنر کا قیاس ٹورنامنٹ حل نوٹ حوالہ جات بھی دیکھیں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ہدایت شدہ گراف