نظرية تلوين الطريق

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

تم وضع هذه النظرية لأول مرة من قبل روي أدلر وبنيامين فايس . ^{[ 2 ]} وقد تم إثباتها من قبل أبراهام تراهتمان في عام 2009. ^{[ 3 ]}

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

على سبيل المثال، لنفترض الرأس المُميز باللون الأصفر. بغض النظر عن نقطة البداية في الرسم البياني، إذا اجتزت جميع الحواف التسعة في المسار "أزرق-أحمر-أحمر—أزرق-أحمر-أحمر—أزرق-أحمر-أحمر"، فستنتهي عند الرأس الأصفر. وبالمثل، إذا اجتزت جميع الحواف التسعة في المسار "أزرق-أزرق-أحمر—أزرق-أزرق-أحمر—أزرق-أزرق-أحمر"، فستنتهي دائمًا عند الرأس المُميز باللون الأخضر، بغض النظر عن نقطة البداية.

تنص نظرية تلوين الطريق على أنه بالنسبة لفئة معينة من الرسوم البيانية الموجهة، فمن الممكن دائمًا إنشاء مثل هذا التلوين.

تشمل النتائج الجزئية أو الخاصة السابقة ما يلي:

• إذا كان G عبارة عن رسم بياني موجه غير دوري متصل بقوة ومحدود بدون حواف متعددة ، ويحتوي G على دورة بسيطة ذات طول أولي وهي مجموعة جزئية فعلية من G ، فإن G يمتلك تلوينًا متزامنًا. ^{[ 5 ]}
• إذا كان G عبارة عن رسم بياني موجه غير دوري متصل بقوة ومحدود (يسمح بوجود حواف متعددة) وكان لكل رأس نفس درجة الدخول ودرجة الخروج k ، فإن G يحتوي على تلوين متزامن. ^{[ 6 ]}

• نظرية الألوان الأربعة
• تلوين الرسوم البيانية

• أدلر، روي ل.؛ فايس ، بنجامين (1970)، تشابه التشاكلات الذاتية للسطح الحلقي ، مذكرات الجمعية الرياضية الأمريكية ، المجلد  98، doi : 10.1090/memo/0098.
• هيجدي، راجنيش؛ جاين، كمال ( 2005)، "نظرية الحد الأدنى والحد الأقصى حول تخمين تلوين الطريق"، وقائع مؤتمر EuroComb 2005 ، الرياضيات المتقطعة وعلوم الحاسوب النظرية، ص 279-284 .
• كاري، جاركو (2003)، "مزامنة الأوتوماتا المحدودة على الرسوم البيانية الموجهة الأويلرية"، علوم الحاسوب النظرية ، 295 ( 1-3 ): 223-232 ، doi : 10.1016/S0304-3975(02)00405-X.
• أوبراين، جي إل (1981)، "مشكلة تلوين الطرق"، مجلة إسرائيل للرياضيات ، 39 ( 1-2 ): 145-154 ، doi : 10.1007/BF02762860.
• تراهتمان، أفراهام ن. (2009)، "مسألة تلوين الطرق"، مجلة إسرائيل للرياضيات ، 172 (1): 51-60 ، arXiv : 0709.0099 ، doi : 10.1007/s11856-009-0062-5.