الجوار (نظرية الرسومات)
عودة للموسوعة- لتوضيحات أخرى لمفهوم الجوارات في الرياضيات، يرجى الرجوع لـ جوار (رياضيات) .
- لمفهوم الجوارات الغير متعلق بمجال الرياضيات يرجى زيارة Neighbourhood (disambiguation).
في نظرية الرسومات، ينطق عن رأس انه رأس مجاور ( adjacent vertex) للرأس
في اغلب الحالات يستخدم الرمز أوللرمز لمجموعة الجوار للرأس في الرسم . هذه المجموعه لاتضم الرأس نفسه فبتالي يمكن تسميتها أيضا بمجموعة الجوار المفتوحة (open neighbourhood) للرأس . يوجد مجموعه جوار اخرى تسمى بالجوار المغلقه (closed neighbourhood ) والتي تحتوي على الرأسويرمز لهذه المجموعه بالرمز . فيما يلي عند ذكر مصطلح جوار بدون تحديد فنعني بذلك المفتوحه.
من الممكن استخدام مفهوم الجوارات لتمثيل الرسومات في خوارزميه حاسوبيه من خلال قائمة الجوار ومصفوفة الجوار الممثله لهذه الرسومات. يستخدم مصطلح الجوارات ايضاً في معامل التجميع ( clustering coefficien ) لرسم ما والذي يهتم بقياس متوسط كثافة التجاور لهذا الرسم. بالإضافة إلى ذلك من الممكن تعريف تصنيفات مهمه للرسومات بناء على خواص التجاور لها أوبالتماثل والتي تربط جميع جوار بالآخر.
يٌسمى الرأس الذي ليس له رؤوس مجاوره بالرأس المنعزل (isolated vertex ). درجة رأس ما تساوي عدد الرؤوس المجاورة لهذا الرأس. في حالة كان الرأس مجاور لنفسه فإنه يسمى بـ عروه ( loop). في حالة وجود عروه لرأس ما فإن هذا الرأس ينتمي لمجموعة التجاور لنفسه.
خصائص محلية في الرسومات
في حالة كانت جميع رؤوس في الرسم
- أي رسم مكتمل يعتبر محليا . الرسوم الوحيده التي تعتبر مكتمله محليا هي الاتحادات المنفصله لرسومات مكتمله.
- رسم توران (Turán graph ) هومحليا . بشكل عام فإن اي رسم توران يعتبرتوران محليا .
- نقول حتى الرسم خالي من المثلثات ( triangle-free ) إذا وفقط إذا كان مستقل محلياً.
- أي رسم به العدد اللوني يساوي
- إذا كانت عائلة من الرسومات مغلقه بالنسبة لعملية الرسوم الجزئية المولدة، فإن جميع رسم في أيضا ينتمي لـ محليا.
- أي رسم يمثل دوره محليه إذا كان مجموعه الجوار له ايضا دوره.
- الرسوم الخطية محليا هي رسومات التي بها مجموعة الجوار هي متطابقة مولدة.
جوار مجموعة
لأي مجموعة من الرؤوس ، فإن تجاور المجموعة هي تعبير عن اتحاد تجاورات رؤوسها.
المزيد
مراجع
-
^ Hell, Pavol (1978). [Graphs with given neighborhoods I "Problèmes combinatoires et théorie des graphes"] تحقق من قيمة
|مسار=
(مساعدة). 260: 219–223. - ^ Sedláček, J. (1983). "On local properties of finite graphs". Graph Theory, Lagów. 1018. Springer-Verlag. صفحات 242–247. doi:10.1007/BFb0071634. ISBN .
- ^ Wigderson, Avi (1983). Improving the performance guarantee for approximate graph coloring. 30. صفحات 729–735. doi:10.1145/2157.2158.
التصنيفات: رياضيات, نظرية المخططات, أخطاء CS1: دورية مفقودة, صفحات برابط تشعبي خاطئ, مقالات يتيمة منذ أغسطس 2019, جميع المقالات اليتيمة, جميع المقالات التي بحاجة لصيانة, بوابة رياضيات/مقالات متعلقة, جميع المقالات التي تستخدم شريط بوابات