رسم بياني ممتلئ للغاية

مشكلة لم تُحل في الرياضيات

الفرضية: رسم بياني G مع${\displaystyle \Del (G)>n/3}$تكون الفئة 2 إذا وفقط إذا كان لها رسم بياني فرعي ممتلئ S بحيث${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$.

المزيد من المسائل غير المحلولة في الرياضيات

في نظرية الرسوم البيانية ، يُعرف الرسم البياني الممتلئ بأنه الرسم البياني الذي يزيد حجمه عن حاصل ضرب درجته القصوى في نصف رتبته بعد تقريبها إلى أقرب عدد صحيح أصغر، أي${\displaystyle |E|>\Delta (G)\lfloor |V|/2\rfloor }$أين${\displaystyle |E|}$حجمها G ،${\displaystyle \displaystyle \Delta (G)}$هي الدرجة القصوى لـ G ، و${\displaystyle |V|}$هو ترتيب G. ويتبع ذلك مباشرةً مفهوم الرسم البياني الفرعي الممتلئ ، وهو رسم بياني ممتلئ يُعد رسمًا بيانيًا فرعيًا . ويتطلب تعريف بديل وأكثر دقة للرسم البياني الفرعي الممتلئ S من الرسم البياني G${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$.

كل رسم بياني دوري فردي بطول ثلاثة أو أكثر يكون مكتظًا. حاصل ضرب درجته (اثنان) في نصف طوله (مقربًا إلى أقرب عدد صحيح أصغر) يكون أقل بواحد من عدد حواف الدورة. وبشكل أعم، كل رسم بياني منتظم ذي عدد فردي من الحواف يكون مكتظًا.${\displaystyle n}$عدد الرؤوس زائد، بسبب عدد حوافها.${\displaystyle \Delta n/2}$(أين${\displaystyle \Delta }$(درجتها)، أكبر من${\displaystyle \Delta \lfloor n/2\rfloor }$.

بعض خصائص الرسوم البيانية الممتلئة:

1. تكون الرسوم البيانية الممتلئة للغاية ذات رتبة غريبة.
2. الرسوم البيانية الممتلئة هي من الفئة 2. أي أنها تتطلب على الأقل Δ + 1 لونًا في أي تلوين للحواف .
3. رسم بياني G ، مع رسم بياني فرعي S ممتلئ بشكل زائد بحيث${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$، من الفئة 2.

في عام 1986، طرحت أماندا تشيتويند وأنتوني هيلتون التخمين التالي الذي يُعرف الآن باسم تخمين الامتلاء الزائد . ^{[ 1 ]}

رسم بياني G مع${\displaystyle \Del (G)>n/3}$تكون الفئة 2 إذا وفقط إذا كان لها رسم بياني فرعي ممتلئ S بحيث${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$.

إذا صحت هذه الفرضية، فسيكون لها آثار عديدة في نظرية الرسم البياني، بما في ذلك فرضية التحليل إلى عامل واحد . ^{[ 2 ]}

بالنسبة للرسوم البيانية التي${\displaystyle \Delta \geq n/3}$يوجد على الأكثر ثلاثة رسوم بيانية فرعية ممتلئة مستحثة ، ومن الممكن إيجاد رسم بياني فرعي ممتلئ في وقت متعدد الحدود . عندما${\displaystyle \Delta \geq n/2}$، يوجد على الأكثر رسم بياني فرعي واحد ممتلئ بشكل زائد، ومن الممكن إيجاده في وقت خطي . ^{[ 3 ]}