نظرية البيانات
- مبرهنة المصافحة
- Σ deg(v) = 2|E|
- البيانات التامة
- |E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
- البيان المنتظم
- |E| = n·k/2
- الشجرة والغابة
- |E| = n − 1, |E| = n − c
- أوراق الشجرة
- L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
- أويلر
- الدارة: كل الدرجات زوجية؛ المسار: درجتان فرديتان بالضبط
- دارات هاملتون في Kn
- (n − 1)!/2
- تحديث ديكسترا
- d(v) = min(d(v), d(u) + w(u, v))
- المسارات (walks) بطول L
- (Mᴸ)ij
الطريقة
- اكتب درجة كل رأس؛ مجموع الدرجات يساوي ضعف عدد الحواف.
- في أسئلة أويلر، تحقّق من أن البيان متصل وعُدّ الرؤوس ذات الدرجة الفردية.
- للأشجار استخدم n − 1 حافة ومبرهنة المصافحة.
- في ديكسترا احتفظ بجدول للمسافات المؤقتة وثبّت في كل جولة أصغر رأس غير مثبّت.
- لإيجاد شجرة ممتدة دنيا، رتّب الحواف بحسب الوزن وتخطَّ كل حافة تُغلق دورة (كروسكال)، أو أنمِ شجرة واحدة انطلاقًا من رأس البداية (برايم).