شجرة (نظرية المخططات)

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
شجرة مبيانية لها 6 رؤوس و 5 حدود

الشجرة هو مصطلح يستعمل في الرياضيات وعلم الحاسوب. في نظرية المخططات الرياضياتية، الشجرة هي مبيان غير موجه والتي يرتبط أي من زوج رأسين بمسار واحد بسيطة. وبالتالي، لا يوجد أي رابط دائري. والغابة (في الرياضيات) هي اتحاد منفصل من الأشجار.

أما في علم الحاسوب، فالشجرة هي أنواع من ترابط البيانات مشابهة للمبيانات الغير موجهة لكنها مجذرة، وبالتالي، لها مخططات موجهة وتسلسل نتتابع لفروعها.

التسمية[عدل]

الشجرة هي الترجمة لمصطلح (بالإنكليزية: Tree) والتي استبطها أرثور كايلي عام 1857[1]، عند وضعه نظرية الأشكال التحليلية ليصف الترابطات التي تبدأ برأس واحد ثم تتشعب إلى روؤس أخرى عن طريق ما يشبه فروع الشجر. ومن المفردات المتعلقة بالشجرة الرياضية:

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

أنواع الشجر[عدل]

مبيانة النجمة
  • النجمة: هي شجرة ذات رأس داخلي يتفرع منها فروع تتصل برؤوس خارجية عن طريق رابط بسيط.
  • مسار: وهي شجرة من ورقتين.

مراجع[عدل]

  1. ^ Cayley (1857) "On the theory of the analytical forms called trees," Philosophical Magazine, 4th series, 13 : 172-176.
Nuvola apps edu mathematics-ar.svg هذه بذرة مقالة عن الرياضيات تحتاج للنمو والتحسين، فساهم في إثرائها بالمشاركة في تحريرها.