الحي (نظرية الرسم البياني)

في نظرية الرسم البياني ، فإن جوار الرأس v في الرسم البياني G هو الرسم البياني الفرعي لـ G الناتج عن جميع الرؤوس المتصلة بـ v بواسطة حافة (الرؤوس المجاورة لـ v )، أي الرسم البياني المكون من جميع الرؤوس المجاورة لـ v وجميع الحواف التي تربطها.

يُشار إلى الحي غالبًا بـ ⁠${\displaystyle N_{G}(v)}$أو (عندما يكون الرسم البياني واضحاً لا لبس فيه )${\displaystyle N(v)}$يمكن استخدام نفس ترميز الجوار للإشارة إلى مجموعة الرؤوس المتجاورة بدلاً من الرسم البياني الفرعي المُستحث المقابل. لا يشمل الجوار الموصوف أعلاه الرأس v نفسه ، وهو تحديدًا الجوار المفتوح للرأس v ؛ ومن الممكن أيضًا تعريف جوار يشمل الرأس v نفسه، ويُسمى الجوار المغلق للرأس v ويُرمز له بـ${\displaystyle N_{G}[v]}$. عندما يُذكر ذلك دون أي قيد، يُفترض أن الحي مفتوح.

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

الرأس المنعزل ليس له رؤوس مجاورة. درجة الرأس v هي عدد الرؤوس المجاورة له . الحالة الخاصة هي الحلقة ، أي الحافة التي تربط رأسًا بنفسه؛ إذا وُجدت مثل هذه الحافة، فإن الرأس ينتمي إلى جواره الخاص.

إذا كانت جميع رؤوس الرسم البياني G لها جوارات متماثلة مع نفس الرسم البياني H ، يُقال إن G محليًا H ، وإذا كانت جميع رؤوس الرسم البياني G لها جوارات تنتمي إلى عائلة رسم بياني F ، يُقال إن G محليًا F. [ ^{1 ] على} سبيل المثال، في الرسم البياني ثماني الأوجه ، الموضح في الشكل، لكل رأس جوار متماثل مع دورة من أربعة رؤوس، لذا فإن ثماني الأوجه محليًا C4 _.

على سبيل المثال:

• أي رسم بياني كامل K _n يكون محليًا K _n−1 . الرسوم البيانية الوحيدة الكاملة محليًا هي اتحادات منفصلة لرسوم بيانية كاملة.
• الرسم البياني لتوران T ( rs , r ) هو محليًا T (( r −1) s , r −1). وبشكل أعم، أي رسم بياني لتوران هو محليًا توران.
• كل رسم بياني مستوٍ يكون محليًا خارجيًا مستويًا . ومع ذلك، ليس كل رسم بياني خارجي مستوي محليًا يكون مستويًا.
• يكون الرسم البياني خالياً من المثلثات إذا وفقط إذا كان مستقلاً محلياً .
• كل رسم بياني من الرتبة k يكون محليًا من الرتبة ( k -1). كل رسم بياني محلي من الرتبة k له عدد لوني${\displaystyle O({\sqrt {kn}})}$[ ^{2 ]​}
• إذا كانت عائلة الرسوم البيانية F مغلقة تحت عملية أخذ الرسوم البيانية الفرعية المستحثة، فإن كل رسم بياني في F يكون أيضًا F محليًا . على سبيل المثال، كل رسم بياني وتري هو وتري محليًا؛ كل رسم بياني مثالي هو مثالي محليًا؛ كل رسم بياني قابل للمقارنة هو قابل للمقارنة محليًا؛ كل رسم بياني متجانس (k)-(فائق)- هو متجانس (k)-(فائق)- محليًا.
• يكون الرسم البياني دوريًا محليًا إذا كانت كل جوار له دورة . على سبيل المثال، يُعدّ المجسم الثماني الأوجه الرسم البياني الوحيد المتصل محليًا من _النوع C⁴ ، والمجسم العشري الأوجه الرسم البياني الوحيد المتصل محليًا من _النوع C⁵ ، ورسم بالي البياني من الرتبة 13 هو من النوع C⁶ محليًا _. الرسوم البيانية الدورية محليًا، باستثناء K⁴ _، هي تحديدًا الرسوم البيانية الأساسية لتثليثات ويتني ، وهي عبارة عن تضمينات للرسوم البيانية على أسطح بحيث تكون أوجه التضمين هي زمر الرسم البياني. ^{[ 3 ]} يمكن أن تحتوي الرسوم البيانية الدورية محليًا على ما يصل إلى${\displaystyle n^{2-o(1)}}$الحواف. ^{[ 4 ]}
• الرسوم البيانية الخالية من المخالب هي الرسوم البيانية الخالية محليًا من المثلثات المشتركة ؛ أي أنه بالنسبة لجميع الرؤوس، لا يحتوي الرسم البياني المكمل لجوار الرأس على مثلث. الرسم البياني الذي يكون محليًا من النوع H يكون خاليًا من المخالب إذا وفقط إذا _كان عدد استقلال H لا يتجاوز اثنين؛ على سبيل المثال، الرسم البياني للمجسم العشري الوجوه المنتظم خالٍ من المخالب لأنه محليًا من النوع C5، وعدد _{استقلال} C5 هو اثنان .
• الرسوم البيانية الخطية المحلية هي الرسوم البيانية التي يكون فيها كل جوار عبارة عن مطابقة مستحثة . ^{[ 5 ]}
• تُعتبر رسوم جونسون البيانية شبكية محلية، مما يعني أن كل جوار هو رسم بياني للرخ . ^{[ 6 ]}

بالنسبة لمجموعة A من الرؤوس، فإن جوار A هو اتحاد جوارات الرؤوس، وبالتالي فهو مجموعة جميع الرؤوس المجاورة لعنصر واحد على الأقل من A. 

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

• بطانية ماركوف
• حي مور
• حي فون نيومان
• مشاكل الحي الثاني
• شكل الرأس ، وهو مفهوم ذو صلة في المجسمات متعددة الأوجه
• الرابط (المركب التبسيطي) ، وهو تعميم للجوار إلى المركبات التبسيطية.

• كوهين، أرجيه م. (1990)، "التعرف الموضعي على الرسوم البيانية والمباني والأشكال الهندسية ذات الصلة" (ملف PDF) ، في كانتور، ويليام م.؛ ليبلر، روبرت أ.؛ باين، ستانلي إي.؛ شولت، إرنست إي. (محررون)، الأشكال الهندسية المحدودة والمباني والمواضيع ذات الصلة: أوراق من مؤتمر المباني والأشكال الهندسية ذات الصلة الذي عُقد في بينغري بارك، كولورادو، 17-23 يوليو 1988 ، منشورات أكسفورد للعلوم، مطبعة جامعة أكسفورد، الصفحات 85-94 ، MR 1072157  انظر على وجه الخصوص الصفحات 89-90
• فرونتشيك، داليبور (1989)، “الرسوم البيانية الخطية محليًا”، Mathematica Slovaca ، 39 (1): 3– 6، hdl : 10338.dmlcz/136481 ، MR 1016323 
• هارتسفيلد، نورا. رينجل، جيرهارد (1991)، “التثليث النظيف”، Combinatorica ، 11 (2): 145–155 ، دوى : 10.1007 / BF01206358 ، S2CID 28144260 .
• الجحيم، بافول (1978)، “الرسوم البيانية مع الأحياء المحددة I”، Problèmes combinatoires et théorie des graphes ، Colloques internationaux CNRS، vol.  260، ص 219 – 223 .
• لاريون، ف.؛ نيومان-لارا، ف .؛ بيزانا، م.أ. (2002)، "تثليثات ويتني، والمحيط المحلي، ورسوم بيانية الزمر المتكررة" ، الرياضيات المتقطعة ، 258 ( 1-3 ): 123-135 ، doi : 10.1016/S0012-365X(02)00266-2.
• مالنيتش، ألكسندر؛ موهار، بويان (1992)، "توليد التثليثات الدورية المحلية للأسطح"، مجلة نظرية التوافيق، السلسلة ب ، 56 (2): 147-164 ، doi : 10.1016/0095-8956(92)90015-P.
• سيدلاسيك، ج. (1983)، "حول الخصائص المحلية للرسوم البيانية المحدودة"، نظرية الرسوم البيانية، لاغوف ، سلسلة محاضرات في الرياضيات، المجلد  1018، سبرينغر-فيرلاغ، الصفحات 242-247 ، doi : 10.1007/BFb0071634 ، ISBN  978-3-540-12687-4.
• سيريس، أكوس؛ سابو، تيبور (1995)، "الرسوم البيانية الكثيفة ذات الجوار الدوري"، مجلة نظرية التوافيق، السلسلة ب ، 63 (2): 281-293 ، doi : 10.1006/jctb.1995.1020.
• ويغدرسون، آفي (1983)، "تحسين ضمان الأداء لتلوين الرسوم البيانية التقريبي"، مجلة ACM ، 30 (4): 729-735 ، doi : 10.1145/2157.2158 ، S2CID 32214512 .