الرسم البياني للعوامل الحرجة

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

يُطلق على تطابق جميع رؤوس الرسم البياني باستثناء رأس واحد اسم التطابق شبه الكامل . وبالمثل، فإن الرسم البياني الحرج للعوامل هو رسم بياني توجد فيه تطابقات شبه كاملة تتجنب كل رأس ممكن.

يمكن وصف الرسوم البيانية الحرجة للعوامل بعدة طرق مختلفة، بخلاف تعريفها كرسوم بيانية يسمح فيها حذف كل رأس بمطابقة مثالية:

• أثبت تيبور غالاي أن الرسم البياني يكون حرجًا من حيث العوامل إذا وفقط إذا كان متصلًا ، ولكل عقدة v في الرسم البياني، يوجد تطابق أقصى لا يشمل v . ويترتب على هذه الخصائص أن الرسم البياني يجب أن يحتوي على عدد فردي من الرؤوس، وأن كل تطابق أقصى يجب أن يطابق جميع الرؤوس باستثناء رأس واحد. ^{[ 3 ]}
• أثبت لازلو لوفاس أن الرسم البياني يكون حرجًا من حيث العوامل إذا وفقط إذا كان له تجزئة أذن فردية . هذه التجزئة عبارة عن تقسيم لحواف الرسم البياني إلى سلسلة من الرسوم البيانية الفرعية، كل منها عبارة عن مسار أو دورة فردية الطول ، حيث تكون الأولى في السلسلة دورة، وكل مسار في السلسلة له نقطتا نهاية فقط، ولا توجد به نقاط داخلية على رؤوس الرسوم البيانية الفرعية السابقة، وكل دورة، باستثناء الأولى في السلسلة، لها رأس واحد فقط في الرسوم البيانية الفرعية السابقة. على سبيل المثال، يمكن تقسيم الرسم البياني في الرسم التوضيحي بهذه الطريقة إلى دورة من خمس حواف ومسار من ثلاث حواف. في حالة وجود تطابق شبه تام للرسم البياني الحرج من حيث العوامل، يمكن اختيار تجزئة الأذن بحيث تتناوب كل أذن بين الحواف المتطابقة وغير المتطابقة. ^{[ 4 ] [ 5 ]}
• يُعتبر الرسم البياني حرجًا من حيث العوامل إذا وفقط إذا أمكن اختزاله إلى رأس واحد من خلال سلسلة من انكماشات الدورات ذات الأطوال الفردية. علاوة على ذلك، في هذا الوصف، يُمكن اختيار كل دورة في السلسلة بحيث تحتوي على الرأس الناتج عن انكماش الدورة السابقة. ^{[ 1 ]} على سبيل المثال، إذا تم انكماش أجزاء من تجزئة الأذن، بالترتيب المُحدد في التجزئة، فإن كل جزء منها يُشكل دورة فردية عند انكماشه، وبالتالي يُمكن استخدام وصف تجزئة الأذن لإيجاد سلسلة من الدورات الفردية لانكماشها. وعلى العكس، من سلسلة من انكماشات الدورات الفردية، يحتوي كل منها على الرأس الناتج عن الانكماش السابق، يُمكن تكوين تجزئة للأذن حيث تكون الأجزاء هي مجموعات الحواف المنكمشة في كل خطوة.
• لنفترض أن لدينا رسمًا بيانيًا G مع اختيار رأس v ومطابقة M تغطي جميع الرؤوس الأخرى غير v . عندئذٍ يكون الرسم البياني G حرجًا عامليًا إذا وفقط إذا وُجدت مجموعة من المسارات في G ، تتناوب بين الحواف المتطابقة وغير المتطابقة، تربط v بكل رأس من الرؤوس الأخرى في G. بناءً على هذه الخاصية، يمكن تحديد ما إذا كان الرسم البياني G، مع مطابقة شبه مثالية معينة، حرجًا عامليًا في وقت خطي . ^{[ 6 ]}

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

إذا كان الرسم البياني G حرجًا من حيث العوامل، فإنّ Mycielskian الخاص به يكون حرجًا أيضًا . على سبيل المثال، يُعدّ الرسم البياني Grötzsch ، وهو Mycielskian لرسم بياني دوري ذي خمسة رؤوس، حرجًا من حيث العوامل. ^{[ 8 ]}

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

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

كل رسم بياني حرج عاملي متصل برأسين وله m حافة، يحتوي على m تطابقًا شبه مثالي مختلفًا على الأقل ، وبشكل أعم، كل رسم بياني حرج عاملي له m حافة و c كتلة (مكونات متصلة برأسين) يحتوي على m − c + 1 تطابقًا شبه مثالي مختلفًا على الأقل. يمكن تمييز الرسوم البيانية التي تكون فيها هذه الحدود دقيقة من خلال امتلاكها تحليلات فردية ذات شكل محدد. ^{[ 7 ]}

يمكن تحويل أي رسم بياني متصل إلى رسم بياني حرج عاملي عن طريق تقليص عدد كافٍ من حوافه. تشكل المجموعات الدنيا من الحواف التي يجب تقليصها لجعل رسم بياني معين G حرجًا عامليًا قواعد الماترويد ، مما يعني أنه يمكن استخدام خوارزمية جشعة لإيجاد مجموعة الحواف ذات الوزن الأدنى التي يجب تقليصها لجعل الرسم البياني حرجًا عامليًا، في وقت متعدد الحدود . ^{[ 11 ]}

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

في علم التوافق متعدد السطوح ، تلعب الرسوم البيانية الحرجة للعوامل دورًا مهمًا في وصف أوجه متعدد السطوح المطابق لرسم بياني معين. ^{[ 1 ] [ 2 ]}

يُقال إن الرسم البياني حرج من النوع k -factor-critical إذا كان لكل مجموعة جزئية من n − k رأسًا تطابق تام. وبناءً على هذا التعريف، يكون الرسم البياني القابل للتطابق الجزئي حرجًا من النوع 1-factor-critical. ^{[ 13 ]} وبشكل أعم، يكون الرسم البياني حرجًا من النوع ( r , k ) -factor-critical إذا كان لكل مجموعة جزئية من n − k رأسًا عامل من النوع r -factor، أي أنها مجموعة رؤوس رسم بياني فرعي منتظم من النوع r- من الرسم البياني المعطى.

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

بالإضافة إلى نظرية الرسم البياني، تم توسيع مفهوم الأهمية العاملية ليشمل الماترويدات من خلال تعريف نوع من تفكيك الأذن على الماترويدات، وتعريف الماترويد بأنه ذو أهمية عاملية إذا كان لديه تفكيك أذن تكون فيه جميع الأذنين فردية. ^{[ 16 ]}