جوار (نظرية البيان)
{{عن|3=جوار (توضيح)}}
{{لا صندوق معلومات}}
{{عن|3=الجوار (توضيح)}}
[[ملف:6n-graf.svg|تصغير|رسم مكون من <math>6</math> رؤوس و<math>7</math> أضلاع.]]

: ''لتوضيحات أخرى لمفهوم الجوارات في الرياضيات، يرجى الرجوع لـ [[جوار (رياضيات)]] .''
: لمفهوم الجوارات الغير متعلق بمجال الرياضيات يرجى زيارة ''[[:en:Neighbourhood (disambiguation)|Neighbourhood (disambiguation)]].''

في نظرية الرسومات، يقال عن رأس انه '''رأس مجاور''' ('''adjacent vertex''') للرأس <math>v</math> في [[رسم بياني|الرسم]] إذا كان مرتبط بالرأس <math>v</math> بواسطة ضلع. '''الجوار (neighbourhood)''' للرأس <math>v </math> في الرسم <math>G </math>هي [[رسم جزئي مولد]] بواسطة كل الرؤوس المجاورة لـ <math>v</math> . بمعنى آخر، جوار الرأس <math>v</math> هو الرسم المكون من الرؤوس المجاورة لهذا الرأس <math>v</math> وجميع الأضلاع التي تربط الرؤوس المجاورة بـ <math>v</math>. على سبيل المثال، بالصورة المرفقة هنا، الجوار للرأس<math>5</math> يتكون من الرؤوس <math>1</math> و<math>2 </math> و <math>4</math> والضلع الذي يربط الرأسين <math>1</math> و<math>2</math> .

في اغلب الحالات يستخدم الرمز <math>N_G (v)</math> أو للرمز <math>N(v)</math> لمجموعة الجوار للرأس <math>v</math>في الرسم <math>G</math>. هذه المجموعه لاتشمل الرأس نفسه <math>v</math> فبتالي يمكن تسميتها أيضا بمجموعة '''الجوار المفتوحة (open neighbourhood)''' للرأس <math>v</math>. يوجد مجموعه جوار أخرى تسمى با'''لجوار المغلقه''' ('''closed neighbourhood''') والتي تحتوي على الرأس<math>v</math>ويرمز لهذه المجموعه بالرمز <math>N_G [v]</math> . فيما يلي عند ذكر مصطلح جوار بدون تحديد فنعني بذلك المفتوحه.

من الممكن استخدام مفهوم الجوارات لتمثيل الرسومات في خوارزميه حاسوبيه من خلال قائمة الجوار و[[مصفوفة المجاورة|مصفوفة الجوار]] الممثله لهذه الرسومات. يستخدم مصطلح الجوارات ايضاً في معامل التجميع ([[:en:Clustering coefficient|clustering coefficien]] ) لرسم ما والذي يهتم بقياس متوسط [[:en:Dense graph|كثافة]] التجاور لهذا الرسم. بالإضافة إلى ذلك من الممكن تعريف تصنيفات مهمه للرسومات بناء على خواص التجاور لها أو بالتماثل والتي تربط كل جوار بالآخر.

يٌسمى الرأس الذي ليس له رؤوس مجاوره ب'''[[رأس (نظرية المخططات)|الرأس المنعزل]]''' (isolated vertex). '''[[درجة (نظرية المخططات)|درجة رأس]]''' ما تساوي عدد الرؤوس المجاورة لهذا الرأس. في حالة كان الرأس مجاور لنفسه فإنه يسمى بـ '''عروه''' ([[:en:Loop (graph theory)|loop]]). في حالة وجود عروه لرأس ما فإن هذا الرأس ينتمي لمجموعة التجاور لنفسه.

== خصائص محلية في الرسومات ==
[[ملف:Octahedral_skeleton.svg|تصغير|في [[ثماني سطوح|الرسم ثماني الأوجه]]، الجوار لأي رأس هي عبارة عن [[:en:Cycle graph|دورة]] طولها <math>4</math> .]]في حالة كانت كل رؤوس في الرسم <math>G</math> لديها تجاورات متشاكله للرسم <math>H</math> فإنه يقال فيه هذه الحالة أن الرسم <math>G</math>هو محلياً (locally) الرسم <math>H</math>. وإذا كانت كل الرؤوس في <math>G</math>لها جوارات تنتمي لنفس عائلة الرسومات <math>F</math> فإنه يقال أن <math>G</math>محليا في <math>F</math>.<ref>{{استشهاد بدورية محكمة|مسار=Graphs with given neighborhoods I|عنوان=Problèmes combinatoires et théorie des graphes|الأخير=Hell|الأول=Pavol|سلسلة=Colloques internationaux C.N.R.S.|سنة=1978|المجلد=260|صفحات=219–223}}</ref><ref>{{استشهاد بكتاب|عنوان=Graph Theory, Lagów|ناشر=Springer-Verlag|الأول=J.|مؤلف1=Sedláček|المجلد=1018|صفحات=242–247|سنة=1983|سلسلة=Lecture Notes in Mathematics|الفصل=On local properties of finite graphs|DOI=10.1007/BFb0071634|ISBN=978-3-540-12687-4}}</ref> على سبيل المثال، في الرسم ثماني الأوجه الموضح بالشكل المرفق نجد أن كل رأس له تجاور متشاكل لدوره من أربع رؤوس فبتالي فإن الرسم ثماني الاوجه ([[:en:Octahedron|octahedron graph]] ) هو محليا دوره بطول <math>4</math> أي <math>C_4</math>.

* أي [[رسم بياني كامل|رسم مكتمل]] <math>K_n</math> يعتبر <math>K_{n-1}</math> محليا. الرسوم الوحيده التي تعتبر مكتمله محليا هي الاتحادات المنفصله لرسومات مكتمله.
* رسم توران ([[:en:Turán graph|Turán graph]] ) <math>T(rs,r)</math> هو محليا <math>T((r-1)s,r-1)</math> . بشكل عام فإن أي رسم توران يعتبرتوران محليا.
* نقول أن الرسم خالي من المثلثات ([[:en:Triangle-free graph|triangle-free]] ) إذا وفقط إذا كان [[:en:Independent set (graph theory)|مستقل]] محلياً.
* أي رسم به [[مسألة تلوين المخطط|العدد اللوني يساوي]] <math>k</math> (''k''-[[:en:Chromatic number|chromatic]]) فإن العدد اللوني المحلي يساوي <math>k</math> . أي رسم بعدد تلوين <math>k</math> محليا لديه عدد تلوين <math>O(\sqrt{kn})</math>.<ref>{{استشهاد بكتاب|عنوان=Improving the performance guarantee for approximate graph coloring|مؤلف1=Wigderson|الأول=Avi|المجلد=30|العدد=4|صفحات=729–735|سنة=1983|DOI=10.1145/2157.2158|مؤلف-وصلة=آفي ويغرسون}}</ref>
* إذا كانت <math>F</math> عائلة من الرسومات مغلقه بالنسبة لعملية الرسوم الجزئية المولدة، فإن كل رسم في <math>F</math> أيضا ينتمي لـ <math>F</math> محليا.
* أي رسم يمثل دوره محليه إذا كان مجموعه الجوار له أيضا دوره.
* الرسوم الخطية محليا هي رسومات التي بها مجموعة الجوار هي [[:en:Induced matching|متطابقة مولدة]].

== جوار مجموعة ==
لأي مجموعة من الرؤوس <math>A</math> ، فإن تجاور المجموعة <math>A</math> هي عبارة عن اتحاد تجاورات رؤوسها.

== المزيد ==

== مراجع ==
{{مراجع}}
{{شريط بوابات|رياضيات}}

[[تصنيف:رياضيات]]
[[تصنيف:نظرية البيان]]
لتوضيحات أخرى لمفهوم الجوارات في الرياضيات، يرجى الرجوع لـ جوار (رياضيات) .
 لمفهوم الجوارات الغير متعلق بمجال الرياضيات يرجى زيارة Neighbourhood (disambiguation).

في نظرية الرسومات، يقال عن رأس انه رأس مجاور (adjacent vertex) للرأس  في الرسم إذا كان مرتبط بالرأس  بواسطة ضلع. الجوار (neighbourhood) للرأس  في الرسم هي رسم جزئي مولد بواسطة كل الرؤوس المجاورة لـ  . بمعنى آخر، جوار الرأس  هو الرسم المكون من الرؤوس المجاورة لهذا الرأس  وجميع الأضلاع التي تربط الرؤوس المجاورة بـ . على سبيل المثال، بالصورة المرفقة هنا، الجوار للرأس يتكون من الرؤوس  و و  والضلع الذي يربط الرأسين  و .

في اغلب الحالات يستخدم الرمز  أو للرمز  لمجموعة الجوار للرأس في الرسم . هذه المجموعه لاتشمل الرأس نفسه  فبتالي يمكن تسميتها أيضا بمجموعة الجوار المفتوحة (open neighbourhood) للرأس . يوجد مجموعه جوار أخرى تسمى بالجوار المغلقه (closed neighbourhood) والتي تحتوي على الرأسويرمز لهذه المجموعه بالرمز  . فيما يلي عند ذكر مصطلح جوار بدون تحديد فنعني بذلك المفتوحه.

من الممكن استخدام مفهوم الجوارات لتمثيل الرسومات في خوارزميه حاسوبيه من خلال قائمة الجوار ومصفوفة الجوار الممثله لهذه الرسومات. يستخدم مصطلح الجوارات ايضاً في معامل التجميع (clustering coefficien ) لرسم ما والذي يهتم بقياس متوسط كثافة التجاور لهذا الرسم. بالإضافة إلى ذلك من الممكن تعريف تصنيفات مهمه للرسومات بناء على خواص التجاور لها أو بالتماثل والتي تربط كل جوار بالآخر.

يٌسمى الرأس الذي ليس له رؤوس مجاوره بالرأس المنعزل (isolated vertex). درجة رأس ما تساوي عدد الرؤوس المجاورة لهذا الرأس. في حالة كان الرأس مجاور لنفسه فإنه يسمى بـ عروه (loop). في حالة وجود عروه لرأس ما فإن هذا الرأس ينتمي لمجموعة التجاور لنفسه.

 خصائص محلية في الرسومات 
تصغير|في الرسم ثماني الأوجه، الجوار لأي رأس هي عبارة عن دورة طولها  .في حالة كانت كل رؤوس في الرسم  لديها تجاورات متشاكله للرسم  فإنه يقال فيه هذه الحالة أن الرسم هو محلياً (locally) الرسم . وإذا كانت كل الرؤوس في لها جوارات تنتمي لنفس عائلة الرسومات  فإنه يقال أن محليا في . على سبيل المثال، في الرسم ثماني الأوجه الموضح بالشكل المرفق نجد أن كل رأس له تجاور متشاكل لدوره من أربع رؤوس فبتالي فإن الرسم ثماني الاوجه (octahedron graph ) هو محليا دوره بطول  أي .

 أي رسم مكتمل  يعتبر  محليا. الرسوم الوحيده التي تعتبر مكتمله محليا هي الاتحادات المنفصله لرسومات مكتمله.
 رسم توران (Turán graph )  هو محليا  . بشكل عام فإن أي رسم توران يعتبرتوران محليا.
 نقول أن الرسم خالي من المثلثات (triangle-free ) إذا وفقط إذا كان مستقل محلياً.
 أي رسم به العدد اللوني يساوي  (k-chromatic) فإن العدد اللوني المحلي يساوي  . أي رسم بعدد تلوين  محليا لديه عدد تلوين .
 إذا كانت  عائلة من الرسومات مغلقه بالنسبة لعملية الرسوم الجزئية المولدة، فإن كل رسم في  أيضا ينتمي لـ  محليا.
 أي رسم يمثل دوره محليه إذا كان مجموعه الجوار له أيضا دوره.
 الرسوم الخطية محليا هي رسومات التي بها مجموعة الجوار هي متطابقة مولدة.

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

 المزيد 

 مراجع 

تصنيف:رياضيات
تصنيف:نظرية البيان