جميع المقالات (الصفحة 429)

قراءات عربية في العلوم والتقنية والطبيعة والثقافة، تبدأ بسؤال وتترك لك مساحة للاستكشاف.

8455 مقالًا

علوم وفضاء

مبرهنة توت: عدد زوجي ورسم متصل لا يكفيان للمطابقة الكاملة

المطابقة الكاملة تختار حواف لا تتشارك في رأس، بحيث يدخل كل رأس في حافة واحدة منها. لذلك يلزم عدد زوجي من الرؤوس. [2] لكن العدد الزوجي والاتصال لا يكفيان: سنبني رسمًا من عشرة رؤوس، ثم نحذف رأسًا واحدًا لنكشف ثلاثة مكونات ذات أعداد فردية من الرؤوس.

7 دقائق قراءةمصدران

علوم وفضاء

مبرهنة ديراك: فشل شرط الدرجة لا ينفي الدورة الهاملتونية

تضمن مبرهنة ديراك دورة هاملتونية في رسم بسيط فيه n≥3 رؤوس، إذا كانت درجة كل رأس لا تقل عن n/2. [1] ماذا إذا لم يتحقق الشرط؟ سنقارن رسمين متصلين من ستة رؤوس وأقل درجة2؛ أحدهما يملك الدورة والآخر لا يملكها. ثم نضيف حواف لنتابع تغير النتيجة والضمان.

6 دقائق قراءةمصدران