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

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

يمكن وصف الرسم البياني للحياد المحدود بشكل مكافئ على النحو التالي:

• الرسم البياني للتقاطع لمجموعة من فترات الوحدة . ^{[ 1 ]}
• الرسم البياني للتقاطع لمجموعة من الفترات ذات الطول نفسه. ^{[ 2 ]}
• الرسم البياني للتقاطع لمجموعة من الفترات التي لا تحتوي أي فترتين منها على الأخرى. ^{[ 1 ] [ 3 ]}
• رسم بياني لفترات زمنية خالية من المخالب . ^{[ 1 ] [ 3 ]}
• الرسم البياني الذي لا يحتوي على رسم بياني فرعي مستحث متماثل مع مخلب${\displaystyle K_{1,3}}$، الشبكة (مثلث له رأس من الدرجة الأولى مجاور لكل رأس من رؤوس المثلث)، أو الشمس (مثلث محاط بثلاثة مثلثات أخرى يشترك كل منها في ضلع واحد مع المثلث المركزي)، أو الثقب (دورة طولها أربعة أو أكثر). ^{[ 4 ]}
• رسم بياني لعدم قابلية المقارنة من الرتبة شبه . ^{[ 1 ]}
• رسم بياني غير موجه له ترتيب خطي بحيث يكون لكل ثلاثة رؤوس مرتبة${\displaystyle u}$–${\displaystyle v}$–${\displaystyle w}$، لو${\displaystyle uw}$إذا كانت ميزة، فكذلك${\displaystyle uv}$و${\displaystyle vw}$[ ^{5 ]​}
• الرسم البياني الذي لا يحتوي على ثلاثية نجمية ، يتكون من ثلاثة رؤوس متصلة بشكل ثنائي بواسطة مسارات تتجنب الرأس الثالث ولا تحتوي أيضًا على جارين متتاليين للرأس الثالث. ^{[ 6 ]}
• رسم بياني يحتوي فيه كل مكون متصل على مسار تشكل فيه كل زمرة قصوى من المكون مسارًا فرعيًا متجاورًا. ^{[ 7 ]}
• الرسم البياني الذي يمكن ترقيم رؤوسه بطريقة تجعل كل مسار أقصر يشكل متتالية رتيبة . ^{[ 7 ]}
• رسم بياني يمكن ترتيب مصفوفة التجاور الخاصة به بحيث تشكل العناصر غير الصفرية في كل صف وكل عمود فترة متصلة مجاورة للقطر الرئيسي للمصفوفة. ^{[ 8 ]}
• رسم بياني فرعي مستحث لقوة مسار بدون وتر. ^{[ 9 ]}
• قوة ورقية ذات جذر ورقي وهي اليرقة. ^{[ 9 ]}

بالنسبة للرسم البياني اللانهائي، قد تختلف بعض هذه التعريفات.

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

في نموذج Erdős-Rényi للرسوم البيانية العشوائية ،${\displaystyle n}$الرسم البياني ذو الرؤوس الذي يكون عدد حوافه أقل بكثير من${\displaystyle n^{2/3}}$سيكون الرسم البياني للحياد ذا احتمالية عالية، بينما${\displaystyle n}$الرسم البياني ذو الرؤوس الذي يكون عدد حوافه أكبر بكثير من${\displaystyle n^{2/3}}$لن يكون رسمًا بيانيًا للحياد باحتمالية عالية. ^{[ 10 ]}

عرض النطاق الترددي لرسم بياني عشوائي${\displaystyle G}$يكون${\displaystyle 1}$أقل من حجم أكبر مجموعة فرعية في رسم بياني للحياد يحتوي على${\displaystyle G}$يُختار الرسم البياني الجزئي لتقليل حجم الزمرة القصوى. ^{[ 11 ]} تُشابه هذه الخاصية العلاقات بين عرض المسار ورسوم الفترات ، وبين عرض الشجرة ورسوم الأوتار . قد يكون مفهوم أضعف للعرض، وهو عرض الزمرة ، كبيرًا بشكل تعسفي على رسوم اللامبالاة. ^{[ 12 ]} مع ذلك، فإن أي فئة فرعية مناسبة (أي أصغر تمامًا) من رسوم اللامبالاة المغلقة تحت الرسوم البيانية الجزئية المستحثة لها حد أعلى لعرض الزمرة في رسومها البيانية. ^{[ 13 ]}

يحتوي الرسم البياني المتصل للحياد على مسار هاميلتوني . ^{[ 14 ]} يحتوي الرسم البياني للحياد على دورة هاميلتونية إذا وفقط إذا كان ثنائي الاتصال . ^{[ 15 ]}

يخضع الرسم البياني للحياد لفرضية إعادة البناء : فهو يتحدد بشكل فريد من خلال الرسوم البيانية الفرعية المحذوفة منها الرؤوس. ^{[ 16 ]}

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

من الممكن اختبار ما إذا كان رسم بياني معين رسمًا بيانيًا غير مبالٍ في زمن خطي، وذلك باستخدام أشجار PQ لإنشاء تمثيل فاصل زمني للرسم البياني، ثم اختبار ما إذا كان ترتيب الرؤوس المستمد من هذا التمثيل يحقق خصائص الرسم البياني غير المبالٍ. ^{[ 5 ]} كما يمكن أيضًا بناء خوارزمية التعرف على الرسوم البيانية غير المبالية على خوارزميات التعرف على الرسوم البيانية الوترية . ^{[ 15 ]} وتعتمد العديد من خوارزميات التعرف البديلة ذات الزمن الخطي على البحث بالعرض أولًا أو البحث بالعرض أولًا المعجمي، بدلًا من العلاقة بين الرسوم البيانية غير المبالية والرسوم البيانية الفاصلية. ^{[ 18 ] [ 19 ] [ 20 ] [ 21 ]}

بعد فرز الرؤوس وفقًا للقيم العددية التي تصف مخطط اللامبالاة (أو وفقًا لتسلسل فترات الوحدة في تمثيل الفترات)، يمكن استخدام الترتيب نفسه لإيجاد تلوين أمثل لهذه المخططات، وحل مشكلة أقصر مسار ، وبناء مسارات هاميلتونية ومطابقات قصوى ، كل ذلك في زمن خطي. ^{[ 5 ]} يمكن إيجاد دورة هاميلتونية من تمثيل فترات مناسب للمخطط في الزمن${\displaystyle O(n\log n)}$[ ^{14 ]} ولكن عندما يُعطى الرسم البياني نفسه كمدخل، فإن نفس المشكلة تقبل حلاً خطيًا زمنيًا يمكن تعميمه على الرسوم البيانية الفاصلية ^{. [ 22 ] [ 23 ]}

تظل مسألة تلوين القوائم مسألةً من فئة NP-complete حتى عند اقتصارها على الرسوم البيانية غير المبالية. ^{[ 24 ]} ومع ذلك، يمكن حلها باستخدام معلمات ثابتة عند تحديدها بعدد الألوان الإجمالي في المدخلات. ^{[ 13 ]}

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

في المعلوماتية الحيوية ، يمكن استخدام مشكلة زيادة الرسم البياني الملون إلى رسم بياني ذي فترات وحدة ملونة بشكل صحيح لنمذجة اكتشاف النتائج السلبية الخاطئة في تجميع تسلسل الحمض النووي من عمليات الهضم الكاملة . ^{[ 26 ]}

• الرسوم البيانية العتبية ، وهي رسوم بيانية يتم تحديد حوافها من خلال مجموع تسميات الرؤوس بدلاً من الفروق بين التسميات.
• الرسوم البيانية المثالية البسيطة ، وهي رسوم بيانية لفترات زمنية يكون فيها كل زوج من الفترات متداخلاً أو منفصلاً بدلاً من أن يتقاطع بشكل صحيح.
• رسوم بيانية قرص الوحدة ، وهي نظائر ثنائية الأبعاد لرسوم بيانية اللامبالاة.

• نظام معلومات حول تضمين فئات الرسوم البيانية : رسم بياني لفترة الوحدة