الأشجار والبيانات المستوية

هذه الورشة إضافية وليست في الكتب السورية. «الشجرة» بيان متصل لا توجد فيه دورة. من خواصها: بين أيّ رأسين مسار واحد فقط؛ والشجرة التي فيها n رأسًا فيها n − ١ ضلعًا بالضبط؛ وإذا كان فيها أكثر من رأس واحد ففيها «ورقة» أي رأس درجته ١. تصف الأشجار شجرة العائلة وفهرس الكتاب ودورات خروج المغلوب.

«الشجرة الشاملة» لبيان متصل هي جزء منه يحوي كل الرؤوس وهو شجرة. للحصول عليها من بيان فيه V رأسًا وE ضلعًا نحذف E − (V − ١) ضلعًا، بحذف ضلع من كل دورة.

يكون البيان «مستويًا» إذا أمكن رسمه دون أن يتقاطع ضلعان. في البيان المستوي المتصل تصحّ صيغة أويلر: V − E + F = ٢، حيث F عدد الأوجه ومعها الوجه الخارجي. هذا موضوع للمتوسعين.