شجرة الكي

في نظرية المخططات ، تُعرف الشجرة من الرتبة k بأنها مخطط غير موجه يتكون من مخطط كامل مكون من ( k  +  1) رأسًا ، ثم إضافة رؤوس إليه بشكل متكرر بحيث يكون لكل رأس مضاف v عدد k من الجيران U ، بحيث تشكل الرؤوس k + 1 الناتجة عن v و U معًا زمرة . ^{[ 1 ] [ 2 ]}  

الأشجار من الرتبة k هي بالضبط الرسوم البيانية القصوى التي يبلغ عرض شجرتها k ( "قصوى" تعني أنه لا يمكن إضافة المزيد من الحواف دون زيادة عرض الشجرة). ^{[ 2 ]} وهي أيضًا بالضبط الرسوم البيانية الوترية التي يكون حجم جميع زمرها القصوى k  +  1، ويكون حجم جميع فواصل زمرها الدنيا k . ^{[ 1 ]}

الأشجار من الرتبة 1 هي نفسها الأشجار . أما الأشجار من الرتبة 2 فهي رسوم بيانية متسلسلة-متوازية قصوى ، ^{[ 3 ]} وتشمل أيضًا الرسوم البيانية الخارجية المستوية القصوى . تُعرف الأشجار المستوية من الرتبة 3 أيضًا باسم الشبكات الأبولونية . ^{[ 4 ]}

الرسوم البيانية التي يبلغ عرضها الشجري k على الأكثر هي بالضبط الرسوم البيانية الفرعية لأشجار k ، ولهذا السبب تسمى أشجار k الجزئية . ^{[ 2 ]}

تُسمى الرسوم البيانية المُشكَّلة من حواف ورؤوس متعددات السطوح المكدسة ذات البعد k ، وهي متعددات سطوح تُشكَّل بالبدء من مُجَسَّم بسيط ثم لصق مُجَسَّمات بسيطة بشكل متكرر على أوجه متعدد السطوح، أشجارًا من الرتبة k عندما يكون k ≥ 3. ^{[ 5 ]} تُحاكي عملية اللصق هذه بناء أشجار الرتبة k بإضافة رؤوس إلى زمرة. ^{[ 6 ]} تُسمى شجرة الرتبة k رسمًا بيانيًا لمتعدد سطوح مكدس إذا وفقط إذا لم يكن لأي زمر مكونة من ثلاثة ( k + 1) رأسًا k رأسًا مشتركة. ^{[ 7 ]}