مخطط شانون المتعدد

في فرع الرياضيات لنظرية الرسم البياني ، تعتبر الرسوم البيانية المتعددة لشانون ، التي سميت على اسم كلود شانون بواسطة فيزينغ (1965) ، ^{[ 1 ]} نوعًا خاصًا من الرسوم البيانية المثلثية ، والتي تستخدم في مجال تلوين الحواف على وجه الخصوص.

الرسم البياني المتعدد لشانون هو رسم بياني متعدد يحتوي على 3 رؤوس ويتحقق فيه أحد الشرطين التاليين:

• أ) جميع الرؤوس الثلاثة متصلة بنفس عدد الحواف.
• ب) كما في أ) ويتم إضافة حافة إضافية.

وبشكل أدق، يُطلق على الرسم البياني المتعدد لشانون اسم Sh( n ) ، إذا كانت الرؤوس الثلاثة متصلة بواسطة${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }$،${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }$و${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$على التوالي. يمتلك هذا الرسم البياني المتعدد درجة قصوى n . تعددية هذا الرسم البياني (الحد الأقصى لعدد الحواف في مجموعة من الحواف التي لها جميعًا نفس نقاط النهاية) هي${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$[ ^{2 ] [ 3 ]​}

• مخططات شانون المتعددة
• 
  Sh(2)
• 
  Sh(3)
• 
  Sh(4)
• 
  Sh(5)
• 
  Sh(6)
• 
  Sh(7)

وفقًا لنظرية شانون (1949) ، فإن كل رسم بياني متعدد ذو درجة قصوى${\displaystyle \Delta }$يتميز بتلوين الحواف الذي يستخدم في الغالب${\displaystyle {\frac {3}{2}}\Delta }$الألوان. ^{[ 4 ]} عندما${\displaystyle \Delta }$زوجي، مثال على الرسم البياني المتعدد لشانون مع التعددية${\displaystyle \Delta /2}$يُظهر هذا أن هذا الحد دقيق: درجة الرأس هي بالضبط${\displaystyle \Delta }$لكن كل واحد من${\displaystyle {\frac {3}{2}}\Delta }$الحواف متجاورة مع بعضها البعض، لذا فهي تتطلب${\displaystyle {\frac {3}{2}}\Delta }$الألوان في أي تلوين مناسب للحواف. ^{[ 3 ]}

تنص إحدى صيغ نظرية فيزينغ على أن كل رسم بياني متعدد ذي درجة قصوى${\displaystyle \Delta }$والتعددية${\displaystyle \mu }$يمكن تلوينها باستخدام الحد الأقصى${\displaystyle \Delta +\mu }$الألوان. ^{[ 5 ]} مرة أخرى، هذا الحد ضيق بالنسبة للرسوم البيانية المتعددة لشانون. ^{[ 3 ]}

• لوتز فولكمان: Graphen an allen Ecken und Kanten . ملاحظات المحاضرة 2006، ص.  244 (الألمانية)