الرسم البياني الحرج

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

أ${\displaystyle k}$الرسم البياني الحرج هو رسم بياني حرج ذو عدد لوني${\displaystyle k}$رسم بياني${\displaystyle G}$مع العدد اللوني${\displaystyle k}$يكون${\displaystyle k}$تُسمى الرسوم البيانية الحرجة إذا كان كل رأس من رؤوسها عنصرًا حرجًا. الرسوم البيانية الحرجة هي أصغر العناصر من حيث العدد اللوني، وهو مقياس بالغ الأهمية في نظرية الرسوم البيانية.

بعض خصائص أ${\displaystyle k}$الرسم البياني الحرج${\displaystyle G}$مع${\displaystyle n}$الرؤوس و${\displaystyle m}$الحواف:

• ${\displaystyle G}$يحتوي على مكون واحد فقط .
• ${\displaystyle G}$محدودة (هذه هي نظرية De Bruijn – Erdős ). ^{[ 1 ]}
• الحد الأدنى للدرجة${\displaystyle \delta (G)}$يخضع لعدم المساواة${\displaystyle \delta (G)\geq k-1}$أي أن كل رأس مجاور على الأقل${\displaystyle k-1}$آخرون. وبقوة أكبر،${\displaystyle G}$يكون${\displaystyle (k-1)}$- متصلة بالحواف . ^{[ 2 ]}
• لو${\displaystyle G}$هو رسم بياني منتظم من الدرجة${\displaystyle k-1}$وهذا يعني أن كل رأس مجاور لـ بالضبط${\displaystyle k-1}$أما الآخرون، فـ${\displaystyle G}$إما أن يكون الرسم البياني كاملاً${\displaystyle K_{k}}$مع${\displaystyle n=k}$الرؤوس، أو رسم بياني دوري ذو طول فردي . هذه هي نظرية بروكس . ^{[ 3 ]}
• ${\displaystyle 2m\geq (k-1)n+k-3}$[ ^{4 ]​}
• ${\displaystyle 2m\geq (k-1)n+(k-3)/(k^{2}-3)n}$[ ^{5 ]​}
• أيضاً${\displaystyle G}$يمكن تقسيمها إلى رسمين بيانيين حرجين أصغر، مع وجود حافة بين كل زوج من الرؤوس تتضمن رأسًا واحدًا من كل رسم بياني فرعي، أو${\displaystyle G}$لديه على الأقل${\displaystyle 2k-1}$الرؤوس. ^{[ 6 ]} وبقوة أكبر، إما${\displaystyle G}$يحتوي على تفكيك من هذا النوع، أو لكل رأس${\displaystyle v}$ل${\displaystyle G}$يوجد${\displaystyle k}$-تلوين${\displaystyle v}$هو الرأس الوحيد من لونه، وكل فئة لونية أخرى لها رأسان على الأقل. ^{[ 7 ]}

الرسم البياني${\displaystyle G}$تكون حرجة بالنسبة للرأس إذا وفقط إذا كان لكل رأس${\displaystyle v}$يوجد تلوين مثالي مناسب حيث${\displaystyle v}$هو فئة لونية أحادية.

كما أظهر هاجوس (1961) ، كل${\displaystyle k}$يمكن تكوين الرسم البياني الحرج من رسم بياني كامل${\displaystyle K_{k}}$من خلال الجمع بين بناء هاجوس وعملية تحدد رأسين غير متجاورين. تتطلب الرسوم البيانية التي يتم تشكيلها بهذه الطريقة دائمًا${\displaystyle k}$الألوان بأي طريقة تلوين مناسبة. ^{[ 8 ]}

الرسم البياني ذو الأهمية المزدوجة هو رسم بياني متصل يؤدي فيه حذف أي زوج من الرؤوس المتجاورة إلى تقليل العدد اللوني بمقدار اثنين. ولا تزال مسألة تحديد ما إذا كان${\displaystyle K_{k}}$هو الوحيد ذو الأهمية الحرجة المزدوجة${\displaystyle k}$الرسم البياني اللوني. ^{[ 9 ]}

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