نظرية فيزينغ

في نظرية المخططات ، تنص نظرية فيزينغ على أنه يمكن تلوين حواف أي مخطط بسيط غير موجه باستخدام عدد من الألوان يزيد على الأكثر بمقدار لون واحد عن الدرجة القصوى Δ للمخطط. ويلزم دائمًا استخدام Δ لونًا على الأقل، لذا يمكن تقسيم المخططات غير الموجهة إلى فئتين: مخططات "الفئة الأولى" التي يكفيها Δ لونًا، ومخططات "الفئة الثانية" التي يلزمها Δ + 1 لونًا. وتنص صيغة أعم لنظرية فيزينغ على أنه يمكن تلوين أي مخطط متعدد غير موجه بدون حلقات باستخدام Δ + µ لونًا على الأكثر، حيث µ هي تعدد المخطط المتعدد. ^{[ 1 ]} سُميت النظرية نسبةً إلى فاديم ج. فيزينغ الذي نشرها عام 1964.

نُشرت النظرية التي اكتشفها عالم الرياضيات السوفيتي فاديم ج. فيزينغ عام 1964 عندما كان فيزينغ يعمل في نوفوسيبيرسك ^{[ 2 ] [ 3 ]} ، وعُرفت باسم نظرية فيزينغ. واكتشف عالم الرياضيات الهندي آر بي غوبتا النظرية بشكل مستقل أثناء دراسته للدكتوراه (1965-1967). ^{[ 4 ] [ 5 ]}

عندما تكون قيمة Δ تساوي 1 ، يجب أن يكون الرسم البياني G نفسه رسمًا متطابقًا، بحيث لا يوجد ضلعان متجاوران، ويكون عدد ألوان ضلعه واحدًا. أي أن جميع الرسوم البيانية التي تحقق Δ( G ) = 1 تنتمي إلى الفئة الأولى.

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

هذا البرهان مستوحى من ديستل (2000) . ^{[ 6 ]}

ليكن G  =  ( V , E )  رسمًا بيانيًا بسيطًا غير موجه. نعتمد على الاستقراء الرياضي على m ، وهو عدد الحواف. إذا كان الرسم البياني فارغًا، فإن النظرية صحيحة بشكل بديهي. ليكن m >  0  ولنفترض وجود تلوين مناسب للحواف من الرتبة (Δ+1) لجميع G − xy   حيث xy ∈ E.  

نقول إن اللون α ∈ {1,...,Δ+1   } مفقود في x ∈ V   بالنسبة لتلوين الحواف الصحيح (Δ+1) c إذا كان c ( xy ) ≠ α   لكل y ∈ N( x )   . كذلك، لنفترض أن المسار α / β من x هو المسار الأقصى الوحيد الذي يبدأ في x بحافة ملونة باللون α ، مع تبديل ألوان الحواف (الحافة الثانية لونها β ، والحافة الثالثة لونها α، وهكذا)، ويمكن أن يكون طوله صفرًا . لاحظ أنه إذا كان c تلوينًا صحيحًا للحواف (Δ+1) للرسم البياني G ، فإن كل رأس من رؤوس الرسم البياني G يكون له لون مفقود بالنسبة لـ c .

لنفترض أنه لا يوجد تلوين مناسب لحواف الرسم البياني G بمقدار (Δ+1) . هذا يكافئ العبارة التالية:

(1) ليكن xy ∈ E   وليكن c تلوينًا مناسبًا عشوائيًا للحواف (Δ+1) لـ G − xy   وليكن α مفقودًا من x و β مفقودًا من y بالنسبة إلى c . عندئذٍ ينتهي المسار α / β من y في x .

هذا مكافئ، لأنه إذا لم يتحقق الشرط (1)، فيمكننا تبديل اللونين α و β على المسار α / β وتعيين لون xy ليكون α ، وبالتالي إنشاء تلوين مناسب لحواف G من c بمقدار (Δ+1) . وبالعكس، إذا وُجد تلوين مناسب لحواف G بمقدار (Δ+1) ، فيمكننا حذف xy ، وتقييد التلوين، ولن يتحقق الشرط (1) أيضًا.

الآن، ليكن xy₀ ∈ E   و c₀ تلوينًا صحيحًا _لحواف G − xy₀ _بمقدار (Δ+1) _، وليكن α مفقودًا في x بالنسبة إلى c₀ _. نُعرّف y₀ _, ... , yₖ _على أنها سلسلة قصوى من جيران x بحيث يكون c₀ ( xyᵢ ) _{مفقودًا} في yᵢ₋₁ بالنسبة إلى c₀ لجميع _{0 < i ≤ k} .      

نُعرّف التلوينات c ₁ ,..., c _k على النحو التالي:

c _i ( xy _j )= c ₀ ( xy _{j +1} ) لجميع 0 ≤ j < i     ،

c _i ( xy _i ) غير مُعرّف،

c _i ( e )= c ₀ ( e ) خلاف ذلك.

إذن ، يُعدّ c _i تلوينًا صحيحًا لحواف G − xy _i بمقدار (Δ+1) نظرًا لتعريف y ₀ ,..., y _k . لاحظ أيضًا أن الألوان المفقودة في x هي نفسها بالنسبة إلى c _i لجميع قيم 0 ≤ i ≤ k .      

ليكن β اللون المفقود في y_{_k} بالنسبة إلى c_₀ ، عندئذٍ يكون β مفقودًا أيضًا في y_{_k} بالنسبة إلى c _{_i} لجميع قيم i ≤ 0 ≤ i ≤ k     . لاحظ أن β لا يمكن أن يكون مفقودًا في x ، وإلا لكان بإمكاننا بسهولة تمديد c_{_k} ، وبالتالي فإن أي حافة بلون β متصلة بـ x لجميع قيم c _{_j} . من خلال مبدأ أقصىية k ، يوجد 1 ≤ i < k     بحيث يكون c _₀ ( xy _{_i} )  = β  . من تعريف c _₁ ، ...، c_{_k،} يتحقق ما يلي:

c₀ ( xyᵢ ₎ = cᵢ₋₁ ( xyᵢ ₎ = cₖ ( _{xyᵢ₋₁ )} = _β​_​​​_​​​​​​      

ليكن P المسار α / β من y_{_k} بالنسبة إلى c_{_k} . من (1)، يجب أن ينتهي P عند x . لكن α غير موجود في x ، لذا يجب أن ينتهي بحافة لونها β . بالتالي، الحافة الأخيرة من P هي y _{_{i - 1}} x . الآن، ليكن P ' المسار α / β من y _{_{i - 1}} بالنسبة إلى c _{_{i - 1}} . بما أن P' محدد بشكل فريد، والحواف الداخلية لـ P لا تتغير في c _₀ ، ...، c_{_k} ، فإن المسار P' يستخدم نفس حواف P بترتيب عكسي ويمر بـ y _{_k} . من الواضح أن الحافة المؤدية إلى y _{_k} لونها α . لكن β غير موجود في y_{_k} ، لذا ينتهي P' عند y_{_k} . وهذا يتناقض مع (1) أعلاه.

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

أظهر إردوش وويلسون (1977) أن جميع الرسوم البيانية تقريبًا من الفئة الأولى. أي، في نموذج إردوش-ريني للرسوم البيانية العشوائية ، حيث تكون احتمالية جميع الرسوم البيانية ذات n رأس متساوية، ليكن p ( n ) احتمال أن يكون رسم بياني ذو n رأس مُختار من هذا التوزيع من الفئة الأولى؛ عندئذٍ يقترب p ( n ) من الواحد في النهاية عندما يؤول n إلى اللانهاية. ^{[ 8 ]} لمزيد من الحدود الدقيقة لمعدل تقارب p ( n ) إلى الواحد، انظر فريز وآخرون (1988) . ^{[ 9 ]}

تم إثبات أن مشكلة التصنيف العامة للرسوم البيانية إلى الفئة الأولى أو الفئة الثانية في عام 1981 هي مشكلة NP-كاملة . ^{[ 10 ]}

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

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

الرسوم البيانية المستوية من الفئة الثانية، المُنشأة بتقسيم المجسمات الأفلاطونية، ليست منتظمة: إذ تحتوي على رؤوس من الدرجة الثانية، بالإضافة إلى رؤوس من درجات أعلى. وتُكافئ نظرية الألوان الأربعة (التي أثبتها أبيل وهاكن عام ١٩٧٦ ) حول تلوين رؤوس الرسوم البيانية المستوية، ^{[ ١٣ ]} ، القول بأن كل رسم بياني مستوٍ منتظم من الدرجة الثالثة بدون جسور هو من الفئة الأولى. ^{[ ١٤ ]}

في عام 1969، افترض برانكو غرونباوم أن كل رسم بياني منتظم من الدرجة الثالثة ذي تضمين متعدد السطوح على أي مشعب ثنائي الأبعاد موجه ، مثل الطارة، يجب أن يكون من الفئة الأولى. في هذا السياق، التضمين متعدد السطوح هو تضمين للرسم البياني بحيث يكون كل وجه من أوجهه قرصًا من الناحية الطوبولوجية، ويكون الرسم البياني الثنائي للتضمين بسيطًا، دون حلقات ذاتية أو تجاورات متعددة. لو صحّ هذا الافتراض، لكان تعميمًا لنظرية الألوان الأربعة، التي أثبت تايت أنها مكافئة للقول بأن الرسوم البيانية المنتظمة من الدرجة الثالثة ذات التضمين متعدد السطوح على كرة هي من الفئة الأولى. مع ذلك، أثبت كوخول (2009) خطأ هذا الافتراض من خلال إيجاد رسوم بيانية متعددة السطوح ذات تضمينات متعددة السطوح على أسطح قابلة للتوجيه من رتبة عالية. ^{[ 15 ]} بناءً على هذا البناء، أظهر أيضًا أن تحديد ما إذا كان الرسم البياني المضمن متعدد الأوجه من الفئة الأولى هو مسألة كاملة من نوع NP. ^{[ 16 ]}

بما أن مشكلة التصنيف العامة، إما إلى الفئة الأولى أو الفئة الثانية، هي مسألة NP-كاملة، فلا أمل في إيجاد خوارزمية ذات زمن متعدد الحدود لأفضل تلوين للحواف. مع ذلك، فإن برهان فيزينغ الأصلي لنظريته هو برهان خوارزمي، يصف خوارزمية ذات زمن متعدد الحدود لتلوين حواف أي رسم بياني بـ Δ + 1 لونًا، حيث Δ هي الدرجة القصوى للرسم البياني. أي أن الخوارزمية تستخدم العدد الأمثل من الألوان للرسوم البيانية من الفئة الثانية، وتستخدم لونًا واحدًا على الأكثر أكثر من اللازم لجميع الرسوم البيانية: تبدأ برسم بياني غير ملون، ثم تجد بشكل متكرر طريقة لإعادة تلوين الرسم البياني لزيادة عدد الحواف الملونة بمقدار واحد. وهكذا، تقوم الخوارزمية بتلوين${\displaystyle m}$الحواف، مع كل عملية إعادة تلوين من هذا القبيل تأخذ${\displaystyle O(n)}$الزمن، ليصبح إجمالي التعقيد الزمني من${\displaystyle O(mn)}$.

يصف ميسرا وغريس (1992) خوارزمية تتبع نفس استراتيجية خوارزمية فيزينغ الأصلية. تحديدًا، لنفترض أن uv حافة غير ملونة في رسم بياني ملون جزئيًا. يمكن تفسير خوارزمية ميسرا وغريس على أنها إنشاء غابة زائفة موجهة P (رسم بياني لكل رأس فيه حافة واحدة على الأكثر) على جيران u : لكل جار p لـ u ، تجد الخوارزمية لونًا c غير مستخدم من قبل أي من الحواف المتصلة بـ p ، وتجد الرأس q (إن وجد) الذي تكون الحافة uq الخاصة به باللون c ، وتضيف pq كحافة إلى P. هناك حالتان:

• إذا احتوت الغابة الزائفة P المُنشأة بهذه الطريقة على مسار من الرأس v إلى الرأس w الذي لا يحتوي على أي حواف صادرة في P ، فسيكون هناك لون c متاح عند كل من الرأسين u و w . إعادة تلوين الحافة uw باللون c يسمح بإزاحة ألوان الحواف المتبقية خطوة واحدة على طول هذا المسار: لكل رأس p في المسار، تأخذ الحافة up اللون الذي كان يستخدمه الرأس التالي للرأس p في المسار. يؤدي هذا إلى تلوين جديد يشمل الحافة uv . ^{[ 17 ]}
• من ناحية أخرى، إذا كان المسار المبدئي من v في شبه الغابة P يؤدي إلى دورة، فلنفترض أن w هو جارة u التي ينضم عندها المسار إلى الدورة، ولنفترض أن c هو لون الحافة uw ، ولنفترض أن d هو لون غير مستخدم من قبل أي من الحواف عند الرأس u . عندئذٍ، يؤدي تبديل اللونين c و d على سلسلة كيمب إما إلى كسر الدورة أو الحافة التي ينضم عندها المسار إلى الدورة، مما يؤدي إلى الحالة السابقة. ^{[ 17 ]}

باستخدام بعض هياكل البيانات البسيطة لتتبع الألوان المستخدمة والمتاحة عند كل رأس، يمكن تنفيذ خطوات بناء P وإعادة تلوين الرسم البياني في خوارزمية الرسم البياني في زمن O( n ) ، حيث n هو عدد الرؤوس في الرسم البياني المُدخل. وبما أن هذه الخطوات تحتاج إلى التكرار m مرة، مع زيادة عدد الحواف الملونة بمقدار واحد في كل تكرار، فإن الزمن الإجمالي هو O( mn ) . ^{[ 17 ]}

في تقرير فني غير منشور، ادعى جابو وآخرون (1985) سرعة أكبر${\displaystyle O(m{\sqrt {n}}\log n)}$الحد الزمني لنفس مشكلة التلوين باستخدام Δ + 1 لونًا. ^{[ 18 ]} يظهر نفس الحد أيضًا في ورقة بحثية لأرجوماندي عام 1982 ^{[ 19 ]}

في عام 2024، تم تطوير العديد من الخوارزميات المحسّنة، وبلغت ذروتها بخوارزمية زمنية شبه خطية احتمالية ،${\displaystyle O(m\log \Delta )={\widetilde {O}}(m)}$التعقيد الزمني. ^{[ 20 ] [ 21 ]}

في كلٍّ من غوتين وتوفت (2000) وسويفر (2008) ، يذكر فيزينغ أن عمله كان مدفوعًا بنظرية شانون (1949) ^{[ 22 ]} التي تُبين أنه يُمكن تلوين الرسوم البيانية المتعددة بما لا يزيد عن (3/2)Δ لونًا. ^{[ 23 ] [ 24 ]} على الرغم من أن نظرية فيزينغ أصبحت الآن مادة أساسية في العديد من كتب نظرية الرسوم البيانية، إلا أن فيزينغ واجه صعوبة في نشر النتيجة في البداية، ونُشرت ورقته البحثية حولها في مجلة غير معروفة، وهي مجلة التحليل المنفصل . ^{[ 25 ]}

• نظرية بروكس التي تربط تلوين الرؤوس بالدرجة القصوى

• برهان نظرية فيزينغ على موقع PlanetMath .