شجرة متفرعة: الفرق بين النسختين

اذهب إلى التنقل اذهب إلى البحث
تم إضافة 1٬135 بايت ، ‏ قبل سنتين
الرجوع عن تعديلين معلقين من 51.253.117.3 و Mr.Ibrahembot إلى نسخة 33932871 من Mr.Ibrahembot.
ط (بوت: أضاف قالب:تصنيف كومنز)
(الرجوع عن تعديلين معلقين من 51.253.117.3 و Mr.Ibrahembot إلى نسخة 33932871 من Mr.Ibrahembot.)
{{مصدر|تاريخ=ديسمبر 2018}}
 
[[File:4x4 grid spanning tree.svg|تصغير|A spanning tree (blue heavy edges) of a [[grid graph]]]]
 
في مجال [[نظرية المخططات]]، '''الشجرة المتفرعة''' {{إنج|spanning tree}} هي مخطط بياني يضم مجموعة من العقد والحواف التي تسمى أغصاناً، تتصل هذه العقد مع بعضها البعض بشكل متفرع من نقطة مركزية تسمى الجذر.
 
== عد الأشجار الممتدة ==
 
[[File:Cayley's formula 2-4.svg|تصغير|[[صيغة كايلي]]
 
عدد الاشجار الممتدة من رسم بياني متصل t(G) هو مدروسة ثابتة.
في الرسوم البيانية المحددة
في بعض الحالات، من السهل حساب t(G) مباشرة :
• في حالة G هي نفسها شجرة ، بالتالي t(G)=1
• في حالة G هي “cyclic graph(Cn)”يحتوي علي عدد n من القمم، بالتالي t(G)=n
• في الرسم البياني الكامل مع عدد رؤوس n، Cayley's formula يعطي عدد الأشجار الممتدة nn-2
• في حالة G هي "complete bipartite graph " Kp،qبالتالي
t(G)=pq-1qp-1
• في حالة عدد ابعاد nhypercube graphQn عدد الاشجار الممتدة هو
 
<math>2^{2-2}=1</math> trees in <math>K_2</math>,
<math>3^{3-2}=3</math> trees in <math>K_3</math>, and <math>4^{4-2}=16</math>
trees in <math>K_4</math>.]]
 
===في الرسوم البيانية الاختيارية ===
==مراجع==
{{مراجع}}
{{تصنيف كومنز|Spanning trees}}
{{ضبط استنادي}}
{{شريط بوابات|رياضيات}}
[[تصنيف:أصناف المخططات]]
[[تصنيف:بديهية الاختيار]]
[[تصنيف:رياضيات]]
[[تصنيف:شجرة الامتداد]]{{تصنيف كومنز}}
74٬798

تعديل

قائمة التصفح