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

تم إزالة 1٬160 بايت ، ‏ قبل سنتين
مسح
ط (بوت: أضاف قالب:ضبط استنادي)
(مسح)
وسوم: تحرير من المحمول تعديل ويب محمول تحرير مرئي إزالة نصوص لا أحرف عربية مضافة
{{مصدر|تاريخ=ديسمبر 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}}
{{ضبط استنادي}}
{{شريط بوابات|رياضيات}}
[[تصنيف:أصناف المخططات]]
[[تصنيف:بديهية الاختيار]]
مستخدم مجهول