توجيه غير دوري

في نظرية الرسوم البيانية ، يُعرف التوجيه غير الدوري للرسم البياني غير الموجه بأنه تعيين اتجاه لكل حافة ( توجيه ) لا يشكل أي دورة موجهة ، وبالتالي يجعله رسمًا بيانيًا موجهًا غير دوري . كل رسم بياني له توجيه غير دوري.

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

تكون اتجاهات الأشجار دائمًا غير دورية، وتُنتج أشجارًا متعددة . تُسمى الاتجاهات غير الدورية للرسوم البيانية الكاملة بالبطولات المتعدية . تُعد الاتجاهات ثنائية القطب حالة خاصة من الاتجاهات غير الدورية، حيث يوجد مصدر واحد ومصب واحد فقط؛ كل بطولة متعدية هي ثنائية القطب.

بناء

لكل رسم بياني اتجاه غير دوري. إحدى طرق توليد هذا الاتجاه هي ترتيب الرؤوس في تسلسل، ثم توجيه كل حافة من أقرب نقطة نهاية لها في التسلسل إلى أقرب نقطة نهاية لها. يصبح تسلسل الرؤوس حينها ترتيبًا طوبولوجيًا للرسم البياني الموجه غير الدوري الناتج، وكل ترتيب طوبولوجي لهذا الرسم البياني يولد نفس الاتجاه.

بما أن لكل رسم بياني موجه غير دوري ترتيبًا طوبولوجيًا، فإنه يمكن إنشاء كل اتجاه غير دوري بهذه الطريقة. مع ذلك، من الممكن أن تؤدي تسلسلات رؤوس مختلفة إلى نفس الاتجاه غير الدوري، عندما يكون للرسم البياني الموجه غير الدوري الناتج ترتيبات طوبولوجية متعددة. على سبيل المثال، بالنسبة لرسم بياني دوري بأربعة رؤوس (كما هو موضح)، يوجد 24 تسلسلًا مختلفًا للرؤوس، ولكن 14 اتجاهًا غير دوري ممكنًا فقط.

العلاقة بالتلوين

تنص نظرية جالاي -هاس-روي-فيتافر على أن الرسم البياني له اتجاه غير دوري بحيث يكون أطول مسار فيه على الأكثر $k$ رأسًا إذا وفقط إذا كان من الممكن تلوينه على الأكثر $k$ لونًا. ^{[ 1 ]}

يمكن حساب عدد التوجهات غير الدورية باستخدام متعدد الحدود اللوني $\chi _{G}$ ، وقيمتها عند عدد صحيح موجب $k$ هي عدد تلوينات الرسم البياني بـ $k لونًا . كل رسم بياني$ $G$ يحتوي بالضبط على $|\chi _{G}(-1)|$ ^{[ 2 ]} لذلك يمكن تفسير التوجه غير الدوري بهذا المعنى على أنه تلوين بـ $-1$ $لون$ .

الازدواجية

بالنسبة للرسوم البيانية المستوية ، فإن التوجهات غير الدورية هي ثنائية للتوجهات الدورية تمامًا ، وهي التوجهات التي ينتمي فيها كل ضلع إلى دورة موجهة: إذا $G$ هو رسم بياني مستوٍ ، واتجاهات $G$ يتم نقلها إلى اتجاهات الرسم البياني الثنائي المستوي لـ $G$ عن طريق تدوير كل حافة 90 درجة في اتجاه عقارب الساعة، ثم توجيه دوري كامل لـ $G$ يتوافق هذا مع التوجه غير الدوري للرسم البياني الثنائي والعكس صحيح. ^{[ 3 ]}

ومثل متعددة الحدود اللونية، متعددة حدود توت $T_{G}$ رسم بياني $G$ ، ويمكن استخدامها لحساب عدد التوجهات غير الدورية لـ $G$ مثل $T_{G}(2,0)$ تمتد الازدواجية بين التوجهات غير الدورية والدورية تمامًا للرسوم البيانية المستوية بهذا الشكل إلى الرسوم البيانية غير المستوية أيضًا: يتم الحصول على متعددة حدود توت للرسم البياني المزدوج للرسم البياني المستوي عن طريق تبديل وسيطات $T_{G}$ وعدد التوجهات الدورية الكاملة للرسم البياني $G$ يكون $T_{G}(0,2)$ ويمكن الحصول عليها أيضًا عن طريق تبديل وسيطات الصيغة لعدد التوجهات غير الدورية. ^{[ 4 ]}

تقليب الحواف

يمكن تمثيل مجموعة جميع التوجهات غير الدورية لرسم بياني معين ببنية مكعب جزئي ، حيث يكون توجهان غير دوريين متجاورين عندما يختلفان في اتجاه حافة واحدة. ^{[ 5 ]} وهذا يعني أنه عندما يختلف توجهان غير دوريين مختلفان لنفس الرسم البياني في اتجاهات $k$ من الحواف، فمن الممكن تحويل أحد التوجهين إلى الآخر من خلال سلسلة من $k$ تغييرات في اتجاه حافة واحدة، بحيث تكون كل حالة وسيطة من حالات هذه السلسلة من التحويلات غير دورية أيضًا.

حالات خاصة

شجرة متعددة، وهي نتيجة توجيه الشجرة بشكل غير دوري

كل اتجاه من اتجاهات الشجرة يكون غير دوري. يُطلق على الرسم البياني الموجه غير الدوري الناتج عن هذا الاتجاه اسم الشجرة المتعددة . ^{[ 6 ]}

يُطلق على التوجيه غير الدوري للرسم البياني الكامل اسم " الترتيب المتعدي" ، وهو يُعادل الترتيب الكلي لرؤوس الرسم البياني. في هذا التوجيه، يوجد مصدر واحد ومصب واحد فقط.

وبشكل عام، يُطلق على التوجه غير الدوري لأي رسم بياني والذي يحتوي على مصدر فريد ومصب فريد اسم التوجه ثنائي القطب . ^{[ 7 ]}

التوجيه المتعدي للرسم البياني هو توجيه غير دوري يساوي إغلاقه المتعدي . ليس لكل رسم بياني توجيه متعدٍ؛ الرسوم البيانية التي تمتلك هذا التوجيه هي رسوم بيانية للمقارنة . ^{[ 8 ]} الرسوم البيانية الكاملة هي حالات خاصة من رسوم بيانية للمقارنة، والبطولات المتعدية هي حالات خاصة من التوجيهات المتعدية.

مراجع

↑ نيشيتريل، ياروسلاف ؛ أوسونا دي مينديز، باتريس (2012)، "النظرية 3.13"، التناثر: الرسوم البيانية، والهياكل، والخوارزميات ، الخوارزميات والتوافقية، المجلد 28، هايدلبرغ: سبرينغر، ص 42، doi : 10.1007/978-3-642-27875-4 (غير نشط في 30 يناير 2026)، ISBN 978-3-642-27874-7MR 2920058 {{citation}}: CS1 maint: DOI غير نشط اعتبارًا من يناير 2026 ( رابط ) .
↑ ستانلي، ريتشارد ب. (1973)، "التوجهات غير الدورية للرسوم البيانية"، الرياضيات المتقطعة ، 5 (2): 171-178 ، doi : 10.1016/0012-365X(73)90108-8 .
↑ ويلش، دومينيك (1997)، "العد التقريبي"، دراسات في التوافقية، 1997 (لندن) ، سلسلة محاضرات جمعية لندن الرياضية، المجلد 241، كامبريدج: مطبعة جامعة كامبريدج، الصفحات 287-323 ، doi : 10.1017/CBO9780511662119.010 ، ISBN 978-0-521-59840-8MR 1477750 .
↑ لاس فيرغناس، ميشيل (1980)، "التحدب في المصفوفات الموجهة"، مجلة نظرية التوافيق ، السلسلة ب، 29 (2): 231-243 ، doi : 10.1016/0095-8956(80)90082-9 ، MR 0586435 .
↑ فوكودا، كومي ؛ برودون، آلان؛ ساكوما، تاداشي (2001)، "ملاحظات حول التوجهات غير الدورية ونظرية التغليف"، علوم الحاسوب النظرية ، 263 ( 1-2 ): 9-16 ، doi : 10.1016/S0304-3975(00)00226-7 ، MR 1846912
↑ داسغوبتا، سانجوي ( 1999)، "تعلم الأشجار المتعددة"، وقائع المؤتمر الخامس عشر حول عدم اليقين في الذكاء الاصطناعي (UAI 1999)، ستوكهولم، السويد، يوليو-أغسطس 1999 (PDF) ، الصفحات 134-141 .
↑ دي فرايسيكس، هوبرت؛ دي مينديز، باتريس أوسونا؛ روزنستيل، بيير (1995)، "إعادة النظر في التوجهات ثنائية القطب"، الرياضيات التطبيقية المنفصلة ، 56 ( 2-3 ): 157-179 ، doi : 10.1016/0166-218X(94)00085-R ، MR 1318743 .
↑ غويلة حوري، آلان (1962)، "Caractérisation des graphes Non Orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une communication d'ordre"، Les Comptes rendus de l'Académie des Sciences ، 254 : 1370–1371 ، MR 0172275 .

[1] نيشيتريل، ياروسلاف ؛ أوسونا دي مينديز، باتريس (2012)، "النظرية 3.13"، التناثر: الرسوم البيانية، والهياكل، والخوارزميات ، الخوارزميات والتوافقية، المجلد 28، هايدلبرغ: سبرينغر، ص 42، doi : 10.1007/978-3-642-27875-4 (غير نشط في 30 يناير 2026)، ISBN 978-3-642-27874-7MR 2920058 {{citation}}: CS1 maint: DOI غير نشط اعتبارًا من يناير 2026 ( رابط ) .

[2] ستانلي، ريتشارد ب. (1973)، "التوجهات غير الدورية للرسوم البيانية"، الرياضيات المتقطعة ، 5 (2): 171-178 ، doi : 10.1016/0012-365X(73)90108-8 .

[3] ويلش، دومينيك (1997)، "العد التقريبي"، دراسات في التوافقية، 1997 (لندن) ، سلسلة محاضرات جمعية لندن الرياضية، المجلد 241، كامبريدج: مطبعة جامعة كامبريدج، الصفحات 287-323 ، doi : 10.1017/CBO9780511662119.010 ، ISBN 978-0-521-59840-8MR 1477750 .

[4] لاس فيرغناس، ميشيل (1980)، "التحدب في المصفوفات الموجهة"، مجلة نظرية التوافيق ، السلسلة ب، 29 (2): 231-243 ، doi : 10.1016/0095-8956(80)90082-9 ، MR 0586435 .

[5] فوكودا، كومي ؛ برودون، آلان؛ ساكوما، تاداشي (2001)، "ملاحظات حول التوجهات غير الدورية ونظرية التغليف"، علوم الحاسوب النظرية ، 263 ( 1-2 ): 9-16 ، doi : 10.1016/S0304-3975(00)00226-7 ، MR 1846912

[6] داسغوبتا، سانجوي ( 1999)، "تعلم الأشجار المتعددة"، وقائع المؤتمر الخامس عشر حول عدم اليقين في الذكاء الاصطناعي (UAI 1999)، ستوكهولم، السويد، يوليو-أغسطس 1999 (PDF) ، الصفحات 134-141 .

[7] دي فرايسيكس، هوبرت؛ دي مينديز، باتريس أوسونا؛ روزنستيل، بيير (1995)، "إعادة النظر في التوجهات ثنائية القطب"، الرياضيات التطبيقية المنفصلة ، 56 ( 2-3 ): 157-179 ، doi : 10.1016/0166-218X(94)00085-R ، MR 1318743 .

[8] غويلة حوري، آلان (1962)، "Caractérisation des graphes Non Orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une communication d'ordre"، Les Comptes rendus de l'Académie des Sciences ، 254 : 1370–1371 ، MR 0172275 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]