BEST theorem
گراف تھیوری میں، مجرد ریاضی کا ایک حصہ، بیسٹ تھیوریم ہدایت شدہ (مبنی) گرافوں میں یولیرین سرکٹس کی تعداد کے لیے ایک پروڈکٹ فارمولا دیتا ہے۔ یہ نام ان لوگوں کے ناموں کا مخفف ہے جنہوں نے اسے دریافت کیا: ڈی بروجن، وین آرڈین-ایہرن فیسٹ، اسمتھ اور ٹوٹے۔ درست بیان G = (V، E) کو ایک ہدایت شدہ گراف ہونے دیں۔ یولیرین سرکٹ ایک ہدایت شدہ بند راستہ ہے جو ہر کنارے پر بالکل ایک بار آتا ہے۔ 1736 میں، اویلر نے دکھایا کہ G کا یولیرین سرکٹ صرف اس صورت میں ہوتا ہے جب G جڑا ہوا ہو اور ہر سرے پر انڈیگری آؤٹ ڈگری کے برابر ہو۔ اس صورت میں G کو یولیرین کہا جاتا ہے۔ ہم ڈیگ (v) کے ذریعہ ایک ورٹیکس v کی شناخت کی نشاندہی کرتے ہیں۔ بیسٹ تھیوریم میں کہا گیا ہے کہ منسلک یولیرین گراف G میں یولیرین سرکٹس کا نمبر ec (G) اس فارمولے کے ذریعے دیا جاتا ہے۔ یہاں ٹو (G) آربوریسینسز کی تعداد ہے، جو کہ G میں ایک مقررہ ورٹیکس پر جڑ کی طرف جانے والے درخت ہیں۔ نمبر ٹو (G) کو ڈائرکٹڈ گراف کے لیے میٹرکس ٹری تھیوریم کے ورژن کے ذریعے ایک ڈیٹرمیننٹ کے طور پر شمار کیا جا سکتا ہے۔ یہ یولیرین گراف کی ایک خاصیت ہے کہ جڑے ہوئے یولیرین گراف جی میں ہر دو عمودی v اور w کے لیے ٹی وی (جی) = ٹو (جی)۔ ایپلی کیشنز بیسٹ تھیوریم سے پتہ چلتا ہے کہ ہدایت شدہ گراف میں یولیرین سرکٹس کی تعداد کو کثیر الجہتی وقت میں شمار کیا جا سکتا ہے، یہ ایک مسئلہ ہے جو غیر ہدایت شدہ گراف کے لیے #P-مکمل ہے۔ یہ مکمل اور مکمل دو طرفہ گراف کے یولیرین سرکٹس کی غیر علامتی گنتی میں بھی استعمال ہوتا ہے۔ تاریخ بیسٹ تھیوریم وین آرڈین ایہرن فیسٹ اور ڈی بروجن (1951)، § 6، تھیوریم 6 کی وجہ سے ہے۔ ان کا ثبوت دو طرفہ ہے اور ڈی بروجن ترتیب کو عام کرتا ہے۔ "ثبوت میں شامل نوٹ" میں، وہ اسمتھ اور ٹوٹے (1941) کے پہلے کے نتیجے کا حوالہ دیتے ہیں جو ہر سرے پر ڈیگ (v) = 2 کے ساتھ گراف کے فارمولے کو ثابت کرتا ہے۔ حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ نظریہ 5.6.2۔ گراف تھیوری میں ڈائریکٹڈ گراف تھیوریمز