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

تم إضافة 53 بايت ، ‏ قبل 4 سنوات
ط
روبوت: +تصنيف:أصناف المخططات +تنسيقات تجميلية
ط (بوت:أضاف قالب:تصنيف كومنز)
ط (روبوت: +تصنيف:أصناف المخططات +تنسيقات تجميلية)
{{يتيمة|تاريخ=يونيو 2015}}
 
[[File:4x4 grid spanning tree.svg|thumbتصغير|A spanning tree (blue heavy edges) of a [[grid graph]]]]
 
في مجال الرياضيات لنظرية المخططات,المخططات، spanning tree(شجرة الامتداد)T لمخطط غير متصل هو مخطط ثانويG يحتوي علي كل القمم الموجوده لتلك المخطط. عموما، يمكن للمخطط ان يحتوي علي أكثر من شجرة امتداد ز ولكن اذا كان المخطط غير متصل فلا يمكن ان يحتوي علي شجره امتداد . اذا كانت جميع الحواف في المخطط الثانوي G هي نفسها حواف المخططه T هذا يعني ان G عباره عن شجره مماثله ل T .
 
== تطبيقات ==
العديد من الخوارزميات الاستطلاعية بما فيهم Dijkstra's algorithm و AوA* search algorithm . تقوم ببناء شجره امتداد داخليه تعد خطوة وسيطه في حل المشكلات. من أجل تقليل تكلفة شبكات الكهرباء,الكهرباء، وصلات الأسلاك، الأنابيب، التعرف على الكلام التلقائي ....الخ . الناس غالبا ما تستخدم خوارزميات التي تبني تدريجيا الشجرة الممتدة (أو الكثير من هذه الأشجار) كخطوة وسيطة في عملية إيجاد الحد الأدنى من الشجرة الممتدة.
الإنترنت والعديد من شبكات الاتصالات السلكية واللاسلكية الأخرى لديها صلات الإرسال التي تربط العقد معا في الهندسه اللا كميه شبكة تضم بعض الحلقات. من أجل "تجنب الحلقات"، والعديد من بروتوكولات التوجيه مصممة لمثل هذه الشبكات—بما في ذلك بروتوكول الشجرة الممتدة، فتح مسار أقصر أولا، بروتوكول التوجيه حاله الارتباط، المعزز التوجيه القائم على شجرة....... الخ - يتطلب كل جهاز التوجيه لتذكر الشجرة الممتدة.
 
===حلقات اساسيه===
 
إضافة حافه واحده الي شجرة امتداد يتسبب في تكوين حلقه ؛ كل حلقه تسمي حلقه أساسية. توجد حلقات أساسية متميزة لكل حافة ؛ هكذا,هكذا، يوجد تطابق بين الحلقات الاساسيه والحواف التي لا تنتمي الي شجرة الامتداد. بالنسبة الي المخططات المتصلة التي بقي قمم V . اي شجرة امتداد سوف تحتوي علي عدد من الحواف يكافئV-1 . و هكذاوهكذا فان المخطط الذي يحتوي علي عدد E من الحواف و احديواحدي شجرة الامتداد لهذا المخطط يحتوي علي E-V+1 من الحلقات الأساسية . لأي شجرة امتداد معطاه فان المجموع ل E-V+1 من الحلقات الأساسيه يكون ما يسمي ب cycle basis (قاعدة الحلقات)
 
===مجموعه القطع الاساسيه===
الفكره المزدوجة لفكره الحلقات الأساسية هي فكرة مجموعة القطع الأساسية فبحذف حافه واحده من شجرة الامتداد يتم تقسيم القمم إلى مجموعتين متصلتين . مجموعة القطع الأساسية تعرف علي انها مجنوعة الحواف التي يلزم حذفها من ال مخطط G لانجاز نفس القسم . وهكذا فان كل جرة امتداد تعرف بمجموعه من القطع الاساسيه V-1 . واحده لكل حافة في شجرة الامتداد .
الثنائية بين الحلقات الأساسيه ومجموهة القطع الأساسية أنشئت من قبل مشيرا الى ان دورة حواف ليس في الشجرة الممتدة يمكن أن تظهر فقط في مجموعات قطع من حواف أخرى في الحلقة.
الحواف في ال cutset يمكنها الظهور فقط في الحلقات التي تحتوي الحواف المقابله لل cutset. ويمكن أيضا أن تتجلى هذه الازدواجية باستخدام نظرية matroid. التي تنص علي ان الشجره هي قاعدد matroid . الحلقة الأساسية هي دائرة فريدة من نوعها ضمن مجموعة شكلت من خلال إضافة عنصر واحد إلى قاعدة. و تعرفوتعرف مجموهة القطع الأساسية بنفس الطريقة من matroid.
 
===الغابات الممتدة===
== عد الأشجار الممتدة ==
 
[[File:Cayley's formula 2-4.svg|thumbتصغير|[[Cayley'sصيغة formulaكايلي]]
 
عدد الاشجار الممتدة من رسم بياني متصل t(G) هو مدروسة ثابتة.
• في حالة G هي “cyclic graph(Cn)”يحتوي علي عدد n من القمم، بالتالي t(G)=n
• في الرسم البياني الكامل مع عدد رؤوس n، Cayley's formula يعطي عدد الأشجار الممتدة nn-2
• في حالة G هي "complete bipartite graph " Kp,qبالتاليKp،qبالتالي
t(G)=pq-1qp-1
• في حالة عدد ابعاد nhypercube graphQn عدد الاشجار الممتدة هو
 
• درجة قمة i، وإذا كانت i=j
• -1 إذا القمم i و jمتجاورينوjمتجاورين
• صفر إذا القمم i و jوj تختلف عن بعضها البعض ولكن غير متجاورة.
المصفوفة الناتجة تكون مفردة، بحيث المحدد لها يساوي صفر. ومع ذلك، حذف الصفوف والأعمدة لقمة مختارة عشوائيا يؤدي إلى مصفوفة الأصغر التي المحدد هو بالضبط (G)t.
===Tutteمتعددة الحدود ===
 
على tutte polynomial على الرسم البياني يمكن تعريفها بأنها مبلغ أكثر من الأشجار الممتدة على الرسم البياني من حيث يحسب من "الداخلية" و "الخارجية" من الشجرة . قيمته في الحجج )1,1( في عدد من الأشجار الممتدة أو، في حالات فصل الرسم البياني، على عدد من أقصى تغطي الغابات"
 
tutte polynomial أيضا يمكن أن يحسب باستخدام حذف - تقلص تكرار لكن التعقيد الحسابي هو: على العديد من القيم من حجج، بالتحديد هو رقم ف كامل و منومن الصعب الاقتراب مع ضمان نسبة التقريب . )1,1 (، التي يمكن أن تكون في تقييم استخدام بريشوف، هي واحدة من الاستثناءات القليلة.
 
== الخواروميات==
==مراجع==
{{مراجع}}
 
{{شريط بوابات|رياضيات}}
 
{{تصنيف كومنز|Spanning trees}}
{{شريط بوابات|رياضيات}}
 
[[تصنيف:أصناف المخططات]]
[[تصنيف:رياضيات]]
664٬821

تعديل