كل شجرة ثنائية القسم. الرسوم البيانية للدورة التي تحتوي على عدد زوجي من الرؤوس تكون ثنائية الجزء. كل رسم بياني مستوٍ تتساوى وجوهه جميعًا هو من جزئين.
هل كل الرسوم البيانية ثنائية الأجزاء عبارة عن أشجار؟
كل شجرة ثنائية القسم. الرسوم البيانية للدورة التي تحتوي على عدد زوجي من الرؤوس تكون ثنائية الجزء. كل رسم بياني مستوٍ تتساوى وجوهه جميعًا هو من جزئين.
لماذا كل شجرة عبارة عن رسم بياني ثنائي الأجزاء؟
شجرة: الشجرة عبارة عن رسم بياني بسيط بحواف N - 1 حيث N هو عدد الرؤوس بحيث يكون هناك مسار واحد بالضبط بين أي رأسين. ثنائي الجزء: الرسم البياني ثنائي القسم إذا كان بإمكاننا تقسيم الرؤوس إلى مجموعتين منفصلتين V1 ، V2 بحيث لا توجد حافة تربط الرؤوس من نفس المجموعة
كيف تثبت أن كل شجرة عبارة عن رسم بياني ثنائي الأجزاء؟
دع تكون مجموعة الرؤوس المميزة بعلامة'' وتكون مجموعة الرؤوس المميزة بعلامة ''. من الواضح أن أي رأسين متمايزين من ليست متجاورة بحافة ، وبالمثل ، لأن الأشجار ليس لها دوائر ؛ علاوة على ذلك ، قسِّم بوضوح مجموعة قمة الرسم البياني إلى مجموعتين فرعيتين منفصلتين. وبالتالي ، فإن أي شجرة ثنائية الأطراف.
هل كل رسم بياني كامل ثنائي الأجزاء؟
كل رسم بياني كامل ثنائي الأجزاء. K ، رسم بياني لمور وقفص (ن ، 4). الرسوم البيانية الكاملة ثنائية الأجزاء K ، و K ، +1لديها أقصى عدد ممكن من الحواف بين جميع الرسوم البيانية الخالية من المثلثات بنفس عدد الرؤوس ؛ هذه هي نظرية المانتل.
