نظرية بيست

في نظرية المخططات ، وهي فرع من الرياضيات المتقطعة ، تُقدّم نظرية BEST صيغةً لحساب عدد الدوائر الأويلرية في المخططات الموجهة . ويُشير الاسم إلى أسماء مكتشفيها: إن جي دي بروين ، وتاتيانا فان آردين-إهرنفست ، وسيدريك سميث، و دبليو تي توت .

ليكن G  =  ( V , E ) رسمًا بيانيًا موجهًا. الدائرة الإيلرية هي مسار مغلق موجه يمر بكل حافة مرة واحدة فقط. في عام 1736، أثبت أويلر أن G يمتلك دائرة إيلرية إذا وفقط إذا كان G متصلًا وكانت درجة الدخول مساوية لدرجة الخروج عند كل رأس. في هذه الحالة، يُسمى G رسمًا بيانيًا إيلريًا. نرمز إلى درجة الدخول للرأس v بالرمز deg( v ). 

تنص نظرية BEST على أن عدد الدوائر الأويلرية ec( G ) في رسم بياني أويلري متصل G يُعطى بالصيغة التالية:

${\displaystyle \operatorname {ec} (G)=t_{w}(G)\prod _{v\in V}{\bigl (}\deg(v)-1{\bigr )}!.}$

هنا، يُمثل t_{_w} ( G ) عدد التفرعات الشجرية ، وهي أشجار موجهة نحو الجذر عند رأس ثابت w في G. يمكن حساب العدد t_{_w} (G) كمحدد ، باستخدام صيغة نظرية شجرة المصفوفة للرسوم البيانية الموجهة. ومن خصائص الرسوم البيانية الأويلرية أن t _{_v} ( G )  = t_{_w} ( G ) لكل رأسين v و w في رسم بياني أويلري متصل G. 

تُبيّن نظرية BEST أنه يُمكن حساب عدد الدوائر الأويلرية في الرسوم البيانية الموجهة في وقت متعدد الحدود ، وهي مسألة تُصنّف ضمن فئة #P-complete للرسوم البيانية غير الموجهة. ^{[ 1 ]} كما تُستخدم هذه النظرية في التعداد التقاربي للدوائر الأويلرية للرسوم البيانية الكاملة والثنائية الكاملة . ^{[ 2 ] [ 3 ]}

تُعزى نظرية BEST إلى فان آردين-إهرنفست ودي بروين (1951)، ^{[ 4 ]} §6، النظرية 6. برهانهما تقابلي ويُعمم متتاليات دي بروين . في "ملاحظة أُضيفت أثناء البرهان"، يشيران إلى نتيجة سابقة لسميث وتوت (1941) تُثبت صيغة الرسوم البيانية التي يكون فيها deg(v)=2 عند كل رأس.

• Euler, L. (1736), “Solutio issuesatis ad Geometriam situs pertinentis” ، Commentarii Academiae Scientiarum Petropolitanae (باللاتينية)، 8 : 128– 140.
• توتي، دبليو تي ؛ سميث، سي إيه بي (1941)، "حول المسارات أحادية الاتجاه في شبكة من الدرجة 4"، المجلة الرياضية الأمريكية الشهرية ، 48 (4): 233-237 ، doi : 10.2307/2302716 ، JSTOR 2302716 .
• فان آردين-إهرينفيست، تي . de Bruijn، NG ( 1951)، “الدوائر والأشجار في الرسوم البيانية الخطية الموجهة” (PDF) ، سيمون ستيفين ، 28 : 203–217.
• توتي، دبليو تي (1984)، نظرية الرسم البياني ، ريدينغ، ماساتشوستس: أديسون-ويسلي.
• ستانلي، ريتشارد ب. (1999)، التوافقية العددية ، المجلد  2، مطبعة جامعة كامبريدج ، رقم ISBN 0-521-56069-1النظرية 5.6.2
• أيغنر، مارتن (2007)، دورة في التعداد ، نصوص الدراسات العليا في الرياضيات، المجلد  238، سبرينغر، ISBN 978-3-540-39032-9.