الرسم البياني الكتلي

في نظرية الرسم البياني ، وهي فرع من الرياضيات التوافقية، فإن الرسم البياني الكتلي أو شجرة الزمرة ^{[ 1 ]} هو نوع من الرسم البياني غير الموجه حيث يكون كل مكون ثنائي الاتصال (كتلة) زمرة .

تُسمى الرسوم البيانية الكتلية أحيانًا بشكل خاطئ بأشجار هوسيمي (نسبة إلى كودي هوسيمي )، ^{[ 2 ]} ولكن هذا الاسم يشير بشكل أدق إلى الرسوم البيانية الصبارية ، وهي الرسوم البيانية التي يكون فيها كل مكون ثنائي الاتصال غير تافه عبارة عن دورة. ^{[ 3 ]}

يمكن وصف الرسوم البيانية الكتلية بأنها رسوم بيانية تقاطعية لكتل ​​من الرسوم البيانية غير الموجهة العشوائية. ^{[ 4 ]}

تُعرف الرسوم البيانية الكتلية بأنها تلك الرسوم البيانية التي يكون فيها، لكل أربعة رؤوس u و v و x و y ، أكبر قيمتين من بين المسافات الثلاث d ( u , v ) + d ( x , y ) ، و d ( u , x ) + d ( v , y ) ، و d ( u , y ) + d ( v , x ) متساوية دائمًا. ^{[ 2 ] [ 5 ]}

كما تتميز هذه الرسوم البيانية بخاصية الرسوم البيانية المحظورة ، وهي الرسوم البيانية التي لا تحتوي على رسم بياني ماسي أو دورة من أربعة رؤوس أو أكثر كرسم بياني فرعي مستحث ؛ أي أنها رسوم بيانية وترية خالية من الرسم البياني الماسي. ^{[ 5 ]} وهي أيضًا رسوم بيانية بطلمية ( رسوم بيانية وترية وراثية المسافة ) حيث يرتبط كل عقدتين على مسافة اثنين من بعضهما البعض بمسار أقصر فريد ، ^{[ 2 ]} والرسوم البيانية الوترية التي تشترك فيها كل مجموعتين عظميين في رأس واحد على الأكثر. ^{[ 2 ]}

يُسمى الرسم البياني G رسمًا بيانيًا كتليًا إذا وفقط إذا كان تقاطع أي مجموعتين فرعيتين متصلتين من رؤوس G فارغًا أو متصلًا. لذلك، تُشكل المجموعات الفرعية المتصلة من الرؤوس في الرسم البياني الكتلي المتصل هندسة محدبة ، وهي خاصية لا تنطبق على أي رسم بياني ليس رسمًا بيانيًا كتليًا. ^{[ 6 ]} وبسبب هذه الخاصية، في الرسم البياني الكتلي المتصل، تحتوي كل مجموعة من الرؤوس على مجموعة فرعية متصلة صغرى فريدة، وهي إغلاقها في الهندسة المحدبة. الرسوم البيانية الكتلية المتصلة هي تحديدًا الرسوم البيانية التي يوجد فيها مسار مستحث فريد يربط كل زوج من الرؤوس. ^{[ 1 ]}

تُصنف الرسوم البيانية الكتلية إلى وتري ، ووراثي المسافة ، وجيوديسي . الرسوم البيانية وراثية المسافة هي تلك التي يكون فيها طول كل مسارين مُستحثين بين رأسين متماثلين متساوياً، وهو ما يُضعف وصف الرسوم البيانية الكتلية بأنها تحتوي على مسار مُستحث واحد على الأكثر بين كل رأسين. ولأن كلاً من الرسوم البيانية الوترية والرسوم البيانية وراثية المسافة تُعتبر فئات فرعية من الرسوم البيانية الكاملة ، فإن الرسوم البيانية الكتلية تُصنف ضمن فئة الرسوم البيانية الكاملة.

كل رسم بياني شجري أو عنقودي أو على شكل طاحونة هوائية هو رسم بياني كتلي.

كل رسم بياني كتلي له خاصية الصندوقية على الأكثر اثنين. ^{[ 7 ]}

تُعد الرسوم البيانية الكتلية أمثلة على الرسوم البيانية شبه الوسيطة : فلكل ثلاثة رؤوس، إما أن يوجد رأس وحيد ينتمي إلى أقصر المسارات بين الرؤوس الثلاثة، أو يوجد مثلث وحيد تقع أضلاعه على هذه المسارات الثلاثة الأقصر. ^{[ 7 ]}

تُعدّ الرسوم البيانية الخطية للأشجار هي نفسها الرسوم البيانية الكتلية التي يكون فيها كل رأس مقطوع متصلاً بكتلتين على الأكثر، أو بعبارة أخرى، الرسوم البيانية الكتلية الخالية من المخالب . وقد استُخدمت الرسوم البيانية الخطية للأشجار لإيجاد رسوم بيانية ذات عدد مُحدد من الحواف والرؤوس، حيث يكون أكبر رسم بياني فرعي مُستحثّ، والذي يُمثّل شجرة، أصغر ما يُمكن. ^{[ 8 ]}

تُعدّ الرسوم البيانية الكتلية التي لا يتجاوز حجم كل كتلة فيها ثلاثة نوعًا خاصًا من رسوم الصبار ، وهي رسوم الصبار المثلثية. يمكن إيجاد أكبر رسم صبار مثلثي في ​​أي رسم بياني في وقت متعدد الحدود باستخدام خوارزمية لمسألة تكافؤ الماترويد . ولأن رسوم الصبار المثلثية هي رسوم بيانية مستوية ، يمكن استخدام أكبر رسم صبار مثلثي كتقريب لأكبر رسم بياني فرعي مستوٍ، وهي مسألة فرعية مهمة في عملية التسطيح . تتميز هذه الطريقة، كخوارزمية تقريب ، بنسبة تقريب 4/9، وهي النسبة الأفضل المعروفة لمسألة إيجاد أكبر رسم بياني فرعي مستوٍ. ^{[ 9 ]}

إذا كان G أي رسم بياني غير موجه، فإن الرسم البياني الكتلي لـ G ، والذي يُرمز له بـ B ( G )، هو _رسم بياني لتقاطع كتل G : يحتوي B ( G ) على رأس لكل مكون ثنائي الاتصال في G ، ويكون رأسان من B ( G ) متجاورين إذا التقت الكتلتان المتناظرتان عند رأس مفصلي. إذا كان K1 يرمز إلى الرسم البياني ذي الرأس الواحد، فإن B ( K1 ) يُعرَّف بأنه الرسم البياني الفارغ . B ( G ) هو بالضرورة رسم بياني كتلي: إذ يحتوي على مكون ثنائي الاتصال واحد لكل رأس مفصلي في G ، ويجب _أن يكون كل مكون ثنائي الاتصال مُشكَّل بهذه الطريقة زمرة. على العكس من ذلك، فإن كل رسم بياني كتلي هو الرسم البياني B ( G ) لبعض الرسوم البيانية G. ^{[ 4 ]} إذا كان G شجرة، فإن B ( G ) يتطابق مع الرسم البياني الخطي لـ G.

يحتوي الرسم البياني B ( B ( G )) على رأس واحد لكل رأس مفصلي في G ؛ يكون رأسان متجاورين في B ( B ( G )) إذا كانا ينتميان إلى نفس الكتلة في G. ^{[ 4 ]}