رسم بياني لوحدة القرص

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

تتشكل عادةً من عملية بواسون النقطية ، مما يجعلها مثالاً بسيطاً على بنية عشوائية.

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

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

كل رسم بياني فرعي مستحث من رسم بياني قرصي هو أيضًا رسم بياني قرصي. مثال على رسم بياني ليس رسمًا بيانيًا قرصيًا هو النجمة${\displaystyle K_{1,6}}$مع وجود عقدة مركزية واحدة متصلة بستة أوراق: إذا لامس كل قرص من الأقراص الستة قرصًا مشتركًا، فلا بد أن يلامس قرصان من الأقراص الستة بعضهما البعض. لذلك، لا يمكن أن تحتوي رسوم بيانية الأقراص على عقدة مستحثة${\displaystyle K_{1,6}}$الرسم البياني الفرعي. ^{[ 1 ]} هناك عدد لا نهائي من الرسوم البيانية الفرعية المستحثة المحظورة الأخرى المعروفة. ^{[ 2 ]}

عدد الرسوم البيانية للقرص الوحدوي على${\displaystyle n}$تقع الرؤوس المصنفة ضمن عامل أسي من${\displaystyle n^{2n}}$[ ^{3 ] يشير هذا النمو السريع إلى أن الرسوم البيانية ذات} القرص الواحد لا تمتلك عرضًا مزدوجًا محدودًا . ^{[ 4 ]}

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

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

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

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

• مرونة الحاجز ، وهي مشكلة خوارزمية لكسر الحلقات في رسوم بيانية قرص الوحدة
• الرسم البياني للحياد ، وهو نظير أحادي البعد للرسوم البيانية للقرص الواحد
• الرسم البياني ذو القرص الواحد ، وهو الرسم البياني للقرص الواحد الذي يمكن أن تكون فيه الأقراص متماسّة ولكن لا تتداخل ( الرسم البياني للتماس ).
• الرسم البياني للعملة ، وهو الرسم البياني للتلامس بين الأقراص (ليس بالضرورة ذات الحجم الموحد).
• مُركَّب فيتوريس-ريبس ، وهو تعميم لمخطط القرص الواحد الذي يُنشئ فضاءات طوبولوجية من الرتبة العليا من مسافات الوحدة في فضاء متري
• الرسم البياني ذو المسافة الوحدوية ، هو رسم بياني يتكون من توصيل النقاط التي تبعد مسافة وحدة واحدة بالضبط بدلاً من (كما هو الحال هنا) مسافة لا تتجاوز عتبة معينة.

• أتمناس، أيستيس؛ زاماراييف، فيكتور (2018)، "حول الرسوم البيانية الفرعية المستحثة المحظورة لرسوم بيانية القرص الواحد"، الهندسة المنفصلة والحسابية ، 60 (1): 57-97 ، arXiv : 1602.08148 ، doi : 10.1007/s00454-018-9968-1 ، MR 3807349 ، S2CID 254025741  
• بنتلي، جون ل .؛ ستانات، دونالد ف.؛ ويليامز، إي. هولينز الابن (1977)، "تعقيد إيجاد الجيران القريبين ذوي نصف القطر الثابت"، رسائل معالجة المعلومات ، 6 (6): 209-212 ، doi : 10.1016/0020-0190(77)90070-9 ، MR 0489084 .
• بونيه، إدوارد؛ جينيت، كولن؛ كيم، إيون جونغ؛ توماسي، ستيفان؛ Watrigant، Rémi (2022)، “Twin-width II: Small Classes”، النظرية التوافقية ، 2 (2): P10:1 – P10:42، أرخايف : 2006.09877 ، دوى : 10.5070 / C62257876 ، MR 4449818 
• برو، هاينز؛ كيركباتريك، ديفيد ج. (1998)، "التعرف على الرسم البياني للقرص الواحد هو مسألة صعبة من نوع NP"، الهندسة الحسابية: النظرية والتطبيقات ، 9 ( 1-2 ): 3-24 ، doi : 10.1016/s0925-7721(97)00014-x.
• كلارك، برنت ن.؛ كولبورن، تشارلز ج .؛ جونسون، ديفيد س. (1990)، "رسوم بيانية للقرص الواحد"، الرياضيات المتقطعة ، 86 ( 1-3 ): 165-177 ، doi : 10.1016/0012-365X(90)90358-O.
• دال، جيسبر؛ كريستنسن، مايكل (2002)، "الرسوم البيانية الهندسية العشوائية"، مجلة Physical Review E ، 66 (1) 016121، arXiv : cond-mat/0203026 ، Bibcode : 2002PhRvE..66a6121D ، doi : 10.1103/PhysRevE.66.016121 ، PMID 12241440 ، S2CID 15193516  .
• ديبسكي، ميشال؛ جونوسزا-سزانيافسكي، كونستانتي؛ Śleszyńska-Nowak، Małgorzata (2020)، “مؤشر لوني قوي لـ${\displaystyle K_{1,t}}$الرسوم البيانية الخالية من التعقيد، الرياضيات التطبيقية المنفصلة ، ​​284 : 53-60 ، doi : 10.1016/j.dam.2020.03.024 ، MR 4115456 ، S2CID 216369782  
• غراف، أ. شتومبف، م. Weißenfels، G. (1998)، “On Coloring Unit Disk graphs”، الخوارزمية ، 20 (3): 277–293 ، دوى : 10.1007/PL00009196 ، MR 1489033 ، S2CID 36161020  .
• هوسون، مارك L.؛ سين، أرونابها (1995)، “خوارزميات جدولة البث لشبكات الراديو”، مؤتمر الاتصالات العسكرية، IEEE MILCOM '95 ، المجلد.  2، الصفحات من 647 إلى 651، دوى : 10.1109/MILCOM.1995.483546 ، ISBN  0-7803-2489-7، S2CID 62039740 .
• كانغ، روس جيه؛ مولر، توبياس (2011)، "تمثيلات الكرة والضرب النقطي للرسوم البيانية"، وقائع الندوة السنوية السابعة والعشرين حول الهندسة الحسابية (SoCG'11)، 13-15 يونيو 2011، باريس، فرنسا ، ص 308-314 .
• ماراثي، مادهاف ف.؛ بريو، هاينز؛ هانت الثالث، هاري ب.؛ رافي، إس إس؛ روزنكرانتز، دانيال ج. (1994)، طرق استدلالية قائمة على الهندسة لرسوم بيانية القرص الواحد ، arXiv : math.CO/9409226 ، Bibcode : 1994math......9226M.
• ماتسوي، تومومي (2000)، "خوارزميات التقريب لمسائل المجموعة المستقلة القصوى ومسائل التلوين الجزئي على رسوم بيانية قرص الوحدة"، الهندسة المنفصلة والحسابية ، سلسلة محاضرات في علوم الحاسوب، المجلد  1763، الصفحات 194-200 ، doi : 10.1007/978-3-540-46515-7_16 ، ISBN  978-3-540-67181-7.
• مكديارميد، كولين؛ مولر، توبياس (2013)، "التحقيقات العددية لرسوم بيانية القرص والقطاع"، مجلة نظرية التوافيق ، السلسلة ب، 103 (1): 114-143 ، arXiv : 1111.2931 ، Bibcode : 2011arXiv1111.2931M ، doi : 10.1016/j.jctb.2012.09.004
• مكديارميد، كولين؛ مولر، توبياس (2014)، "عدد الرسوم البيانية القرصية"، المجلة الأوروبية للتوافقية ، 35 : 413-431 ، doi : 10.1016/j.ejc.2013.06.037 ، MR 3090514 
• راغافان، فيجاي؛ سبينراد، جيريمي (2003)، "خوارزميات قوية للمجالات المحدودة"، مجلة الخوارزميات ، 48 (1): 160-172 ، doi : 10.1016/S0196-6774(03)00048-8 ، MR 2006100 ، S2CID 16327087  .