رسم بياني متعدد الأجزاء

في نظرية المخططات ، وهي فرع من الرياضيات، يُعرف المخطط ذو k جزء بأنه مخطط تُقسّم رؤوسه (أو يُمكن تقسيمها) إلى k مجموعة مستقلة مختلفة . وبعبارة أخرى، هو مخطط يُمكن تلوينه بـ k لون، بحيث لا يكون لأي طرفين من أطراف أي ضلع اللون نفسه. عندما k = 2، تُسمى هذه المخططات بالمخططات ثنائية الأجزاء ، وعندما k = 3، تُسمى بالمخططات ثلاثية الأجزاء .

يمكن التعرف على الرسوم البيانية ثنائية الأجزاء في وقت متعدد الحدود ، ولكن لأي قيمة k > 2، فإن اختبار ما إذا كان الرسم البياني k -partite يمثل مسألة NP-كاملة ، عند إعطاء رسم بياني غير ملون . ^{[ 1 ]} مع ذلك، في بعض تطبيقات نظرية الرسوم البيانية، قد يُعطى رسم بياني k -partite كمدخل لعملية حسابية مع تحديد تلوينه مسبقًا؛ يحدث هذا عندما تمثل مجموعات الرؤوس في الرسم البياني أنواعًا مختلفة من الكائنات. على سبيل المثال، تم نمذجة التصنيفات الشعبية رياضيًا بواسطة رسوم بيانية ثلاثية الأجزاء، حيث تمثل مجموعات الرؤوس الثلاث في الرسم البياني مستخدمي النظام، والموارد التي يقوم المستخدمون بتصنيفها، والوسوم التي طبقها المستخدمون على الموارد. ^{[ 2 ]}

مثال على الرسوم البيانية الكاملة ذات الأجزاء k

K _2,2,2 رسم بياني لثماني الأوجه

K _3,3,3 رسم بياني لثماني السطوح المعمم المعقد

K _2,2,2,2 رسم بياني لخلية مكونة من 16 خلية

الرسم البياني الكامل ذو k جزء هو رسم بياني ذو k جزء يوجد فيه ضلع بين كل زوج من الرؤوس من مجموعات مستقلة مختلفة. تُوصف هذه الرسوم البيانية برمز يبدأ بالحرف K متبوعًا بتسلسل أحجام كل مجموعة في التقسيم. على سبيل المثال، K _2,2,2 هو الرسم البياني الثلاثي الكامل لثماني السطوح منتظم ، والذي يمكن تقسيمه إلى ثلاث مجموعات مستقلة، تتكون كل منها من رأسين متقابلين. الرسم البياني المتعدد الأجزاء الكامل هو رسم بياني كامل ذو k جزء لبعض قيم k . ^{[ 3 ]} تُعد رسوم توران البيانية حالة خاصة من الرسوم البيانية المتعددة الأجزاء الكاملة، حيث تختلف المجموعات المستقلة في الحجم برأس واحد على الأكثر. تُعد الرسوم البيانية الكاملة ذات k جزء، والرسوم البيانية المتعددة الأجزاء الكاملة، ورسومها البيانية المكملة ( رسوم التجميع )، حالات خاصة من الرسوم البيانية التكميلية، ويمكن التعرف عليها في وقت متعدد الحدود حتى عندما لا يتم توفير التقسيم كجزء من المدخلات.