الرسم البياني للربح

الرسم البياني للمكسب هو رسم بياني يتم تمييز حوافه "بشكل عكسي" أو "باتجاه محدد" بواسطة عناصر المجموعة G. وهذا يعني أنه إذا كان للحافة e في اتجاه واحد التسمية g (عنصر مجموعة)، فإنها في الاتجاه الآخر لها التسمية g  ⁻¹ . وبالتالي فإن دالة التسمية φ لها الخاصية التي تجعلها محددة بشكل مختلف، ولكن ليس بشكل مستقل، في الاتجاهين المختلفين أو الاتجاهين للحافة e . تسمى المجموعة G مجموعة المكسب ، وφ هي دالة المكسب ، والقيمة φ ( e ) هي مكسب e (في اتجاه معين). الرسم البياني للمكسب هو تعميم للرسم البياني الموقّع ، حيث تحتوي مجموعة المكسب G على عنصرين فقط. انظر Zaslavsky (1989، 1991).

لا ينبغي الخلط بين المكسب والوزن على الحافة، حيث تكون قيمته مستقلة عن اتجاه الحافة.

بعض الأسباب التي قد تدفعك للاهتمام برسوم بيانية للمكاسب هي ارتباطها بنظرية تدفق الشبكة في التحسين التوافقي ، والهندسة ، والفيزياء .

• ترتبط رياضيات الشبكة ذات المكاسب ، أو الشبكة المعممة ، بمصفوفة الإطار لرسم المكاسب.
• لنفترض أن لدينا بعض المستويات الفائقة في R  ⁿ المعطاة بمعادلات من النموذج x _j = g x _i . يمكن معالجة هندسة المستويات الفائقة باستخدام الرسم البياني للمكسب التالي: مجموعة الرؤوس هي {1,2,..., n }. يوجد حافة ij بمكسب g (في الاتجاه من i إلى j ) لكل مستوى فائق بالمعادلة x _j = gx _i . تتم معالجة هذه المستويات الفائقة من خلال الماترويد الإطاري لرسم بياني للمكسب (Zaslavsky 2003).
• أو لنفترض أن لدينا مستويات فائقة معطاة بمعادلات من النموذج x _j = x _i + g . يمكن معالجة هندسة هذه المستويات الفائقة باستخدام مخطط المكسب بنفس مجموعة الرؤوس والحافة ij مع المكسب g (في الاتجاه من i إلى j ) لكل مستوى فائق بالمعادلة x _j = x _i + g . تتم دراسة هذه المستويات الفائقة عبر مصفوفة الرفع لمخطط المكسب (Zaslavsky 2003).
• افترض أن مجموعة المكسب لها إجراء على مجموعة Q. يؤدي تعيين عنصر s _i من Q لكل رأس إلى حالة رسم بياني للمكسب. يتم تلبية الحافة إذا تم تلبية المعادلة s _j = s _i  g لكل حافة ij مع مكسب g (في الاتجاه من i إلى j )؛ وإلا فإنها تكون محبطة . يتم تلبية الحالة إذا تم تلبية كل حافة. ​​في الفيزياء يتوافق هذا مع الحالة الأساسية (حالة الطاقة الأدنى)، إذا كانت هذه الحالة موجودة. تتمثل إحدى المشكلات المهمة في الفيزياء، وخاصة في نظرية النظارات الدورانية ، في تحديد الحالة التي تحتوي على أقل عدد من الحواف المحبطة.

تُعرف الرسوم البيانية للمكسب المستخدمة في نظرية الرسوم البيانية الطوبولوجية كوسيلة لبناء تضمينات الرسوم البيانية في الأسطح باسم " رسوم الجهد " (جروس 1974؛ جروس وتوكر 1977). مصطلح "رسم بياني للمكسب" أكثر شيوعًا في سياقات أخرى، على سبيل المثال، نظرية الرسوم البيانية المتحيزة ونظرية الماترويد . كما تم استخدام مصطلح الرسم البياني المسمى بالمجموعة ، ولكنه غامض نظرًا لأن "علامات المجموعة" قد يتم التعامل معها - وقد تم التعامل معها - كأوزان.

نظرًا لأن الكثير من نظرية الرسوم البيانية للمكسب هي حالة خاصة من نظرية الرسوم البيانية المتحيزة (والكثير من نظرية الرسوم البيانية المتحيزة هي تعميم لنظرية الرسوم البيانية للمكسب)، فيجب على القارئ الرجوع إلى المقال حول الرسوم البيانية المتحيزة للحصول على مزيد من المعلومات والأمثلة.

• جوناثان إل. جروس (1974)، الرسوم البيانية للجهد. الرياضيات المنفصلة ، ​​المجلد 9، ص 239-246.
• JL Gross و TW Tucker (1977)، توليد جميع أغلفة الرسوم البيانية عن طريق تعيينات جهد التبديل. الرياضيات المنفصلة ، ​​المجلد 18، ص 273-283.
• توماس زاسلافسكي (1989)، الرسوم البيانية المتحيزة. 1. التحيز والتوازن والمكاسب. مجلة النظرية التوافقية، السلسلة ب ، المجلد 47، 32-52.
• توماس زاسلافسكي (1991)، الرسوم البيانية المتحيزة. الجزء الثاني. الماترويدات الثلاثة. مجلة النظرية التوافقية، السلسلة ب ، المجلد 51، ص 46-72.
• توماس زاسلافسكي (1999). قائمة مرجعية رياضية للرسوم البيانية الموقعة والمكاسب والمناطق المرتبطة بها. المجلة الإلكترونية للتوافقيات، المسوحات الديناميكية في التوافقيات، #DS8.
• توماس زاسلافسكي (2003)، الرسوم البيانية المتحيزة، المجلد الرابع: التنفيذات الهندسية. مجلة النظرية التوافقية، السلسلة ب ، المجلد 89، العدد 2، ص 231-297.