معضلة المصافحة

رسم تخطيطي لجسور كونيغسبرغ السبعة

رسم بياني برؤوس لكل كتلة أرضية وحافة لكل جسر

أثبت ليونارد أويلر لأول مرة معضلة المصافحة في بحثه عن جسور كونيغسبرغ السبعة ، حيث طلب إيجاد مسار سير في مدينة كونيغسبرغ ( كالينينغراد حاليًا ) يعبر كل جسر من جسورها السبعة مرة واحدة. يمكن ترجمة هذا إلى مصطلحات نظرية المخططات على أنه طلب إيجاد مسار أويلر أو جولة أويلر لمخطط متصل يمثل المدينة وجسورها: أي مسار عبر المخطط يعبر كل حافة مرة واحدة، إما أن ينتهي عند رأس مختلف عن رأس البداية في حالة مسار أويلر، أو يعود إلى نقطة البداية في حالة جولة أويلر. حدد أويلر النتائج الأساسية لهذه المسألة بدلالة عدد الرؤوس الفردية في المخطط، والذي تقصره معضلة المصافحة على أن يكون عددًا زوجيًا. إذا كان هذا العدد صفرًا، توجد جولة أويلر، وإذا كان اثنين، يوجد مسار أويلر. خلاف ذلك، لا يمكن حل المسألة. في حالة جسور كونيغسبرغ السبعة، يحتوي الرسم البياني الذي يمثل المسألة على أربعة رؤوس فردية، ولا يوجد به مسار أويلر ولا جولة أويلر. ^{[ 3 ]} لذلك كان من المستحيل المرور على جميع الجسور السبعة في كونيغسبرغ دون تكرار أحدها.

في خوارزمية كريستوفيدس-سيرديوكوف لتقريب مسألة البائع المتجول ، تلعب الآثار الهندسية لصيغة مجموع الدرجات دورًا حيويًا، مما يسمح للخوارزمية بربط الرؤوس في أزواج من أجل إنشاء رسم بياني تشكل عليه جولة أويلر جولة تقريبية لمسألة البائع المتجول. ^{[ 10 ]}

يمكن إثبات أن العديد من البنى التوافقية زوجية العدد من خلال ربطها بالرؤوس الفردية في "مخطط التبادل" المناسب. ^{[ 11 ]}

فعلى سبيل المثال، كما أثبت سي إيه بي سميث ، في أي رسم بياني مكعب${\displaystyle G}$يجب أن يكون هناك عدد زوجي من دورات هاميلتونية عبر أي حافة ثابتة${\displaystyle uv}$هذه دورات تمر بكل رأس مرة واحدة فقط. استخدم توماسون (1978) برهانًا قائمًا على معضلة المصافحة لتوسيع هذه النتيجة لتشمل الرسوم البيانية التي تكون فيها جميع الرؤوس ذات درجة فردية. يُعرّف توماسون رسمًا بيانيًا للتبادل.${\displaystyle H}$، والتي تتطابق رؤوسها تطابقًا تامًا مع مسارات هاميلتون في${\displaystyle G}$ابتداءً من${\displaystyle u}$والاستمرار عبر الحافة${\displaystyle uv}$مساران من هذا القبيل${\displaystyle p_{1}}$و${\displaystyle p_{2}}$تُعرَّف بأنها متصلة بحافة في${\displaystyle H}$إذا كان بإمكان المرء الحصول${\displaystyle p_{2}}$بإضافة حافة جديدة إلى نهاية${\displaystyle p_{1}}$وإزالة حافة أخرى من منتصف${\displaystyle p_{1}}$هذه العملية قابلة للعكس، مما يُشكل علاقة متناظرة ، لذا${\displaystyle H}$هو رسم بياني غير موجه. إذا كان المسار${\displaystyle p}$ينتهي عند الرأس${\displaystyle w}$ثم الرأس المقابل لـ${\displaystyle p}$في${\displaystyle H}$لها درجة تساوي عدد الطرق التي${\displaystyle p}$قد يتم تمديدها بواسطة حافة لا تتصل مرة أخرى بـ${\displaystyle u}$أي درجة هذا الرأس في${\displaystyle H}$إما${\displaystyle \deg(w)-1}$(عدد زوجي) إذا${\displaystyle p}$لا يشكل جزءًا من دورة هاميلتونية من خلال${\displaystyle uv}$، أو${\displaystyle \deg(w)-2}$(عدد فردي) إذا${\displaystyle p}$هو جزء من دورة هاميلتونية عبر${\displaystyle uv}$. منذ${\displaystyle H}$يحتوي على عدد زوجي من الرؤوس الفردية،${\displaystyle G}$يجب أن يكون هناك عدد زوجي من دورات هاميلتونيان${\displaystyle uv}$[ ^{12 ]​}

تُستخدم مبرهنة المصافحة (أو صيغة مجموع الدرجات) أيضًا في براهين العديد من النتائج الأخرى في الرياضيات. وتشمل هذه النتائج ما يلي:

• تنصّ مبرهنة سبيرنر على أنه إذا قُسِّم مثلث كبير إلى مثلثات أصغر تتقاطع حوافها، ووُضِعَت ثلاثة ألوان على رؤوسها بحيث يُستخدم لونان فقط على كل ضلع من أضلاع المثلث الكبير، فإنّ مثلثًا واحدًا على الأقل من المثلثات الأصغر يحتوي على رؤوس من الألوان الثلاثة جميعها. ولها تطبيقات في نظريات النقطة الثابتة ، وخوارزميات إيجاد الجذور ، والقسمة العادلة . أحد براهين هذه المبرهنة هو رسم بياني للتبادل رؤوسه هي المثلثات (الصغيرة والكبيرة) وحوافه تربط أزواجًا من المثلثات التي تشترك في رأسين من لونين محددين. بالضرورة، يكون للمثلث الكبير درجة فردية في هذا الرسم البياني، وكذلك المثلث الصغير ذو الألوان الثلاثة، ولكن ليس المثلثات الصغيرة الأخرى. وبحسب مبرهنة المصافحة، يجب أن يكون عدد المثلثات الصغيرة ذات الألوان الثلاثة فرديًا، وبالتالي يجب أن يوجد مثلث واحد على الأقل من هذا النوع. ^{[ 13 ]}

• تنص مسألة تسلق الجبال على أنه بالنسبة للدوال المنتظمة على فترة الوحدة ، والتي تتساوى قيمها عند طرفي الفترة، فإنه من الممكن تنسيق حركة نقطتين، تبدآن من طرفي الفترة المتقابلين، بحيث تلتقيان في مكان ما في المنتصف مع بقائهما عند نقاط متساوية القيمة طوال الحركة. يتضمن أحد البراهين على ذلك تقريب الدالة بدالة خطية متقطعة لها نفس النقاط القصوى، وتحديد موضع النقطتين المتحركتين بإحداثيات نقطة واحدة في مربع الوحدة ، وإثبات أن المواضع المتاحة للنقطتين تُشكل رسمًا بيانيًا محدودًا، مُضمنًا في هذا المربع، حيث يكون موضع البداية وانعكاسه فقط هما الرأسين الفرديين. وبحسب نظرية المصافحة، ينتمي هذان الموضعان إلى نفس المكون المتصل من الرسم البياني، ويمر المسار من أحدهما إلى الآخر بالضرورة عبر نقطة الالتقاء المطلوبة. ^{[ 14 ]}
• تتعلق فرضية إعادة البناء بمشكلة تحديد بنية الرسم البياني بشكل فريد من مجموعة الرسوم البيانية الفرعية الناتجة عن إزالة رأس واحد منه. وبناءً على هذه المعلومات، يمكن استخدام صيغة مجموع الدرجات لاستعادة عدد الحواف في الرسم البياني المعطى ودرجات كل رأس. ومن ثم، يمكن تحديد ما إذا كان الرسم البياني المعطى منتظمًا ، وإذا كان كذلك، فيمكن تحديده بشكل فريد من أي رسم بياني فرعي محذوف منه رأس، وذلك بإضافة جار جديد لجميع رؤوس الرسم البياني الفرعي ذات الدرجة المنخفضة جدًا. وبالتالي، يمكن إعادة بناء جميع الرسوم البيانية المنتظمة. ^{[ 15 ]}
• لعبة هيكس هي لعبة ثنائية اللاعبين، حيث يضع كل لاعب قطعًا من لونه على لوحة متوازية الأضلاع مُرصّعة بمضلعات سداسية حتى يُكوّن أحد اللاعبين مسارًا متصلًا من القطع المتجاورة من جانب اللوحة إلى الجانب الآخر. لا يمكن أن تنتهي اللعبة بالتعادل أبدًا: فبحلول الوقت الذي تمتلئ فيه اللوحة بالقطع، يكون أحد اللاعبين قد كوّن مسارًا فائزًا. أحد الأدلة على ذلك هو رسم بياني للوحة اللعبة الممتلئة، برؤوس عند زوايا المضلعات السداسية، وحواف على جوانب المضلعات السداسية التي تفصل بين لوني اللاعبين. يحتوي هذا الرسم البياني على أربعة رؤوس فردية عند زوايا اللوحة، ورؤوس زوجية في باقي أجزائها، لذا يجب أن يحتوي على مسار يربط بين زاويتين، وهذا المسار بالضرورة يحتوي على مسار فائز لأحد اللاعبين على أحد جوانبه. ^{[ 16 ]}

تشير صيغة مجموع الدرجات إلى أن كل${\displaystyle r}$- رسم بياني منتظم مع${\displaystyle n}$الرؤوس${\displaystyle nr/2}$الحواف. ^{[ 18 ]} بما أن عدد الحواف يجب أن يكون عددًا صحيحًا ، فإنه يترتب على ذلك أنه عندما${\displaystyle r}$إذا كان عدد الرؤوس فرديًا، فيجب أن يكون عدد الرؤوس زوجيًا. ^{[ 19 ]} بالإضافة إلى ذلك، بالنسبة للقيم الفردية لـ${\displaystyle r}$يجب أن يكون عدد الحواف قابلاً للقسمة على${\displaystyle r}$[ ^{20 ]​}

يُقسّم الرسم البياني ثنائي الأجزاء رؤوسه إلى مجموعتين فرعيتين، ولكل ضلع طرف في كل مجموعة فرعية. وبناءً على نفس حجة العد المزدوج، فإن مجموع درجات كل مجموعة فرعية يساوي عدد الأضلاع في الرسم البياني. وعلى وجه الخصوص، تتساوى مجموع درجات المجموعتين الفرعيتين. ^{[ 21 ]} بالنسبة للرسوم البيانية ثنائية الانتظام ، مع تقسيم الرؤوس إلى مجموعات فرعية${\displaystyle V_{1}}$و${\displaystyle V_{2}}$مع كل رأس في مجموعة جزئية${\displaystyle V_{i}}$حاصل على درجة علمية${\displaystyle r_{i}}$، لا بد أن يكون الأمر كذلك${\displaystyle |V_{1}|r_{1}=|V_{2}|r_{2}}$كلاهما يساوي عدد الحواف. ^{[ 22 ]}

لا تنطبق معضلة المصافحة بصيغتها المعتادة على الرسوم البيانية اللانهائية، حتى عندما تحتوي على عدد محدود فقط من الرؤوس ذات الدرجة الفردية. على سبيل المثال، يحتوي الرسم البياني للمسارات اللانهائية ذو نقطة النهاية الواحدة على رأس واحد فقط ذي درجة فردية، بدلاً من أن يحتوي على عدد زوجي من هذه الرؤوس. مع ذلك، من الممكن صياغة نسخة من معضلة المصافحة باستخدام مفهوم النهاية ، وهي فئة تكافؤ للمسارات شبه اللانهائية ("الأشعة")، حيث يُعتبر شعاعان متكافئين عندما يوجد شعاع ثالث يستخدم عددًا لا نهائيًا من الرؤوس من كل منهما. درجة النهاية هي الحد الأقصى لعدد الأشعة غير المتداخلة التي تحتويها، وتكون النهاية فردية إذا كانت درجتها محدودة وفردية. بشكل أعم، من الممكن تعريف النهاية بأنها فردية أو زوجية، بغض النظر عما إذا كانت ذات درجة لانهائية، في الرسوم البيانية التي تكون فيها جميع الرؤوس ذات درجة محدودة. ثم، في مثل هذه الرسوم البيانية، يكون مجموع عدد الرؤوس الفردية والنهايات الفردية إما زوجيًا أو لانهائيًا. ^{[ 23 ]}

بحسب نظرية جالاي، يمكن تقسيم رؤوس أي رسم بياني إلى${\displaystyle V=V_{e}\cup V_{o}}$أين في الرسمين البيانيين الفرعيين الناتجين ،${\displaystyle G[V_{e}]}$جميع درجاته زوجية و${\displaystyle G[V_{o}]}$جميع درجاتها فردية. هنا،${\displaystyle |V_{o}|}$يجب أن يكون زوجيًا وفقًا لفرضية المصافحة. من الممكن أيضًا إيجاد رسوم بيانية فرعية مستحثة ذات درجة زوجية وفردية تحتوي على العديد من الرؤوس. يمكن إيجاد رسم بياني فرعي مستحث ذي درجة زوجية يحتوي على نصف الرؤوس على الأقل، ويمكن إيجاد رسم بياني فرعي مستحث ذي درجة فردية (في رسم بياني لا يحتوي على رؤوس معزولة ) يحتوي على${\displaystyle |V_{o}|/|V|>1/10000}$[ ^{24 ] [ 25 ]​}