رقم هادويجر

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

وصف فاغنر (1937) الرسوم البيانية التي لا يتجاوز عدد هادويغر فيها أربعة . أما الرسوم البيانية التي يكون عدد هادويغر فيها محدودًا، فهي رسوم بيانية متفرقة، ولها عدد لوني صغير. يُعدّ تحديد عدد هادويغر للرسم البياني مسألة صعبة الحل (NP-hard)، ولكنها قابلة للحل باستخدام معلمات ثابتة .

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

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

تنص نظرية فاغنر ، التي تُعرّف الرسوم البيانية المستوية بواسطة قواطعها المحظورة ، على أن عدد هادويغر للرسوم البيانية المستوية لا يتجاوز أربعة. وفي الورقة البحثية نفسها التي أثبتت هذه النظرية، وصف فاغنر (1937) الرسوم البيانية التي لا يتجاوز عدد هادويغر فيها أربعة بدقة أكبر: فهي رسوم بيانية يمكن تكوينها من خلال عمليات جمع الزمر التي تجمع بين الرسوم البيانية المستوية ورسم فاغنر ذي الرؤوس الثمانية .

تتضمن الرسوم البيانية التي يكون عدد هادويجر فيها خمسة على الأكثر الرسوم البيانية للقمة والرسوم البيانية القابلة للتضمين بدون روابط ، وكلاهما يحتوي على الرسم البياني الكامل K ₆ من بين الرسوم البيانية الصغرى المحظورة. ^{[ 3 ]}

كل رسم بياني يحتوي على n رأسًا وعدد هادويجر k له ⁠${\displaystyle O(nk{\sqrt {\log k}})}$الحواف . هذا الحد دقيق: لكل k ، توجد رسوم بيانية ذات عدد هادويجر k والتي لها${\displaystyle \Omega (nk{\sqrt {\log k}})}$الحواف. [ ^{4 ] إذا} كان للرسم البياني G عدد هادويجر k ، فإن جميع رسوماته البيانية الفرعية لها أيضًا عدد هادويجر لا يتجاوز k ، ويترتب على ذلك أن G يجب أن يكون لديه انحلال .${\displaystyle O(k{\sqrt {\log k}})}$لذلك ، فإن الرسوم البيانية ذات عدد هادويجر المحدود هي رسوم بيانية متفرقة .

تنصّ حدسية هادويغر على أن عدد هادويغر يكون دائمًا أكبر من أو يساوي العدد اللوني للرسم البياني G. أي أن كل رسم بياني ذي عدد هادويغر k يجب أن يكون له تلوين بياني بأكثر من k لونًا. الحالة k = 4 مكافئة (بحسب توصيف فاغنر للرسوم البيانية ذات عدد هادويغر هذا) لنظرية الألوان الأربعة لتلوين الرسوم البيانية المستوية ، وقد تم إثبات الحدسية أيضًا لـ k ≤ 5 ، ولكنها لا تزال غير مثبتة للقيم الأكبر من k . ^{[ 5 ]}  

بسبب انخفاض درجة انحلالها، يمكن تلوين الرسوم البيانية التي يكون عدد هادويجر فيها على الأكثر k باستخدام خوارزمية تلوين جشعة .${\displaystyle O(k{\sqrt {\log k}})}$الألوان .

يُعد اختبار ما إذا كان عدد هادويغر لرسم بياني مُعطى يساوي على الأقل قيمة مُعطاة k مسألةً كاملةً من فئة NP ، ^{[ 6 ]} ومن ثمّ يُستنتج أن تحديد عدد هادويغر مسألةٌ صعبةٌ من فئة NP . مع ذلك، يُمكن حلّ هذه المسألة باستخدام مُعاملات ثابتة : إذ توجد خوارزمية لإيجاد أكبر مُصغّر للزمرة في وقت يعتمد فقط على حجم الرسم البياني بشكلٍ كثير الحدود، ولكنه يعتمد أُسّيًا على h ( G ) . ^{[ 7 ]} إضافةً إلى ذلك، يُمكن للخوارزميات ذات الوقت كثير الحدود تقريب عدد هادويغر بنسبة تقريب تبلغ${\displaystyle O({\sqrt {n}})}$، بدقة أكبر بكثير من أفضل تقريب زمني متعدد الحدود (بافتراض أن P  ≠  NP ) لحجم أكبر رسم بياني فرعي كامل . ^{[ 7 ]}

العدد اللوني للرسم البياني G هو حجم أكبر زمرة يمكن تشكيلها عن طريق تقليص مجموعة من المجموعات المستقلة في G.

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

كل رسم بياني ذو عدد هادويجر k يحتوي على ما لا يزيد عن n 2 ^{O ( k log(log k ))} من الزمر (الرسوم البيانية الفرعية الكاملة). ^{[ 9 ]}

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