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

اذهب إلى التنقل اذهب إلى البحث
تم إضافة 16 بايت ، ‏ قبل 6 سنوات
لا يوجد ملخص تحرير
ط (إضافة بوابة رياضيات (شريط البوابات))
وسمان: تحرير من المحمول تعديل ويب محمول
tutte polynomial أيضا يمكن أن يحسب باستخدام حذف - تقلص تكرار لكن التعقيد الحسابي هو: على العديد من القيم من حجج، بالتحديد هو رقم ف كامل و من الصعب الاقتراب مع ضمان نسبة التقريب . )1,1 (، التي يمكن أن تكون في تقييم استخدام بريشوف، هي واحدة من الاستثناءات القليلة.
 
== الخواروميات: ==
===بناء===
 
المتوازية والموزعة. وبدلا من ذلك، وقد ابتكر الباحثون عدة خوارزميات أكثر تخصصا للعثور على الأشجار الممتدة في هذه النماذج من الحساب.
 
===النمذجهالنمذجة===
 
في مجالات معينة من نظرية الرسم البياني غالبا ما يكون من المفيد ايجاد اقل شجرة ممتدة من شكل ذو اوزان مختلفه . كما تم دراسة مشاكل نمذجه أخرى على الأشجار الممتدة، بما في ذلك مشاكل ايجاد الحد الأقصى من الشجرة الممتدة، والحد الأدنى الشجرة التي تمتد على القمم ك ، والشجرة الممتدة مع أقل عدد من حواف لكل قمه ، والشجرة الممتدة مع أكبر عدد من الأوراق، والشجرة الممتدة مع أقل عدد من الأوراق (ترتبط ارتباطا وثيقا مشكلة مسار هاميلتون)، مشكله اقل قطر للشجرة الممتدة ، والحد الأدنى من اتساع الشجرة الممتدة. [19] [20]
===في الرسوم البيانية لانهائية ===
 
كل رسم بياني متصل محدود له الشجرة الممتدة. ومع ذلك، من أجل الرسوم البيانية متصلة لا حصر لها، ووجود الأشجار التي تغطي ما يعادل مسلمة الاختيار. تم توصيل الرسم البياني لانهائي إذا كان كل زوج من رؤوسه يشكل زوج من نقاط النهاية لمسار محدود. كما هو الحال مع الرسوم البيانية محدودة، شجرة هي رسم بياني متصل مع عدم وجود دورات محدودة، ويمكن تعريف شجرة تمتد إما مجموعة احلقي القصوى من الحواف أو مثل شجرة يحتوي على كل قمة الرأس. [24]
 
الأشجار في الرسم البياني قد أمرت جزئيا بالنسبة رسم بياني ثانوي بهم، وأي سلسلة لا نهائية في هذا النظام الجزئي لديه الحد الأعلى (اتحاد الأشجار في السلسلة). يتطلب يما زورن، واحدة من العديد من البيانات أي ما يعادل مسلمة الاختيار، وهذا أمر جزئي في التي يحدها العلوي كل السلاسل يكون عنصرا القصوى. في النظام الجزئي على الأشجار الرسم البياني، يجب أن يكون هذا العنصر القصوى شجرة تمتد. لذلك، إذا يفترض يما زورن، وكل رسم بياني متصل لانهائي لديه الشجرة الممتدة. [24]
 
في الاتجاه الآخر، نظرا لأسرة مكونة من مجموعات، فمن الممكن لبناء الرسم البياني لانهائي بحيث كل شجرة تمتد من الرسم البياني يتوافق مع وظيفة الاختيار من عائلة مجموعات. لذلك، إذا كل رسم بياني متصل لانهائي لديه شجرة الممتدة، ثم مسلمة الاختيار صحيح. [25]
 
==مراجع==
{{مراجع}}
{{شريط بوابات|رياضيات}}
 

قائمة التصفح