إنتروبيا الرسم البياني

في نظرية المعلومات ، يُعدّ إنتروبيا الرسم البياني مقياسًا لمعدل المعلومات الذي يمكن تحقيقه من خلال نقل الرموز عبر قناة قد يحدث فيها تداخل بين بعض أزواج القيم. ^{[ 1 ]} وقد أثبت هذا المقياس، الذي قدمه كورنر لأول مرة في سبعينيات القرن العشرين، ^{[ 2 ] [ 3 ]} فائدته في مجالات أخرى، بما في ذلك التوافقية. ^{[ 4 ]}

يترك${\displaystyle G=(V,E)}$ليكن رسمًا بيانيًا غير موجه . إنتروبيا الرسم البياني لـ${\displaystyle G}$، المشار إليه${\displaystyle H(G)}$يُعرَّف بأنه

${\displaystyle H(G)=\min _{X,Y}I(X;Y)}$

أين${\displaystyle X}$يتم اختيارها بشكل عشوائي من${\displaystyle V}$،${\displaystyle Y}$تتراوح على مجموعات مستقلة من G، التوزيع المشترك لـ${\displaystyle X}$و${\displaystyle Y}$بحيث${\displaystyle X\in Y}$باحتمال واحد، و${\displaystyle I(X;Y)}$المعلومات المتبادلة لـ${\displaystyle X}$و${\displaystyle Y}$[ ^{5 ]​}

أي إذا سمحنا${\displaystyle {\mathcal {I}}}$تشير إلى مجموعات الرؤوس المستقلة في${\displaystyle G}$نرغب في إيجاد التوزيع المشترك${\displaystyle X,Y}$على${\displaystyle V\times {\mathcal {I}}}$بأقل قدر من المعلومات المتبادلة بحيث يكون (أ) التوزيع الهامشي للحد الأول منتظمًا، و(ب) في عينات من التوزيع، يحتوي الحد الثاني على الحد الأول بشكل شبه مؤكد. المعلومات المتبادلة لـ${\displaystyle X}$و${\displaystyle Y}$ويُطلق عليها حينها اسم إنتروبيا${\displaystyle G}$.

• الرتابة. إذا${\displaystyle G_{1}}$هو رسم بياني فرعي من${\displaystyle G_{2}}$على نفس مجموعة الرؤوس، ثم${\displaystyle H(G_{1})\leq H(G_{2})}$.
• خاصية الجمع الجزئي. بالنظر إلى رسمين بيانيين${\displaystyle G_{1}=(V,E_{1})}$و${\displaystyle G_{2}=(V,E_{2})}$على نفس مجموعة الرؤوس، اتحاد الرسم البياني${\displaystyle G_{1}\cup G_{2}=(V,E_{1}\cup E_{2})}$يرضي${\displaystyle H(G_{1}\cup G_{2})\leq H(G_{1})+H(G_{2})}$.
• المتوسط ​​الحسابي لاتحادات منفصلة. ليكن${\displaystyle G_{1},G_{2},\cdots ,G_{k}}$لتكن سلسلة من الرسوم البيانية على مجموعات منفصلة من الرؤوس، مع${\displaystyle n_{1},n_{2},\cdots ,n_{k}}$الرؤوس، على التوالي. ثم${\displaystyle H(G_{1}\cup G_{2}\cup \cdots G_{k})={\tfrac {1}{\sum _{i=1}^{k}n_{i}}}\sum _{i=1}^{k}{n_{i}H(G_{i})}}$.

بالإضافة إلى ذلك، توجد صيغ بسيطة لفئات معينة من عائلات الرسوم البيانية.

• تتمتع الرسوم البيانية الكاملة المتوازنة ذات الأجزاء k بالإنتروبيا${\displaystyle \log _{2}k}$. بخاصة،
  • تتمتع الرسوم البيانية عديمة الحواف بالإنتروبيا${\displaystyle 0}$.
  • أكمل الرسوم البيانية حول${\displaystyle n}$الرؤوس لها إنتروبيا${\displaystyle \log _{2}n}$.
  • تتمتع الرسوم البيانية الثنائية المتوازنة تمامًا بالإنتروبيا${\displaystyle 1}$.
• أكمل الرسوم البيانية الثنائية الأجزاء مع${\displaystyle n}$الرؤوس في قسم واحد و${\displaystyle m}$أما في الجانب الآخر، فيوجد إنتروبيا${\displaystyle H\left({\frac {n}{m+n}}\right)}$، أين${\displaystyle H}$هي دالة الإنتروبيا الثنائية .

هنا، نستخدم خصائص إنتروبيا الرسم البياني لتقديم برهان بسيط على أن الرسم البياني الكامل${\displaystyle G}$على${\displaystyle n}$لا يمكن التعبير عن الرؤوس كاتحاد لأقل من${\displaystyle \log _{2}n}$الرسوم البيانية ثنائية الأجزاء.

برهان: بحسب خاصية الرتابة، لا يمكن لأي رسم بياني ثنائي الأجزاء أن يمتلك إنتروبيا رسم بياني أكبر من إنتروبيا الرسم البياني الثنائي الكامل، والتي تكون محدودة بـ${\displaystyle 1}$وبالتالي، من خلال خاصية الجمع الجزئي، فإن اتحاد${\displaystyle k}$لا يمكن أن يكون للرسوم البيانية ثنائية الأجزاء إنتروبيا أكبر من${\displaystyle k}$والآن لنبدأ${\displaystyle G=(V,E)}$كن رسمًا بيانيًا كاملاً على${\displaystyle n}$الرؤوس. وفقًا للخصائص المذكورة أعلاه،${\displaystyle H(G)=\log _{2}n}$لذلك، فإن اتحاد أقل من${\displaystyle \log _{2}n}$لا يمكن أن يكون للرسوم البيانية ثنائية الأجزاء نفس الإنتروبيا مثل${\displaystyle G}$، لذا${\displaystyle G}$لا يمكن التعبير عنها على أنها اتحاد من هذا القبيل.${\displaystyle \blacksquare }$

• ماتياس ديمر؛ فرانك إيمرت-ستريب؛ زينغكيانغ تشين؛ شوليانغ لي؛ يونغتانغ شي (25 يوليو 2016). الأسس الرياضية وتطبيقات إنتروبيا الرسم البياني . وايلي. ISBN 978-3-527-69325-2.