ग्राफ एन्ट्रापी

सूचना सिद्धांत में, ग्राफ एन्ट्रॉपी एक चैनल पर प्रतीकों को संचारित करके प्राप्त की जाने वाली सूचना दर का एक माप है जिसमें मूल्यों के कुछ जोड़े भ्रमित हो सकते हैं। यह उपाय, सबसे पहले 1970 के दशक में कोर्नर द्वारा पेश किया गया था, तब से यह कॉम्बिनेटरिक्स सहित अन्य सेटिंग्स में भी उपयोगी साबित हुआ है।

परिभाषा

होने देना $G=(V,E)$ एक अप्रत्यक्ष ग्राफ बनें। का ग्राफ एन्ट्रापी $G$, निरूपित $H(G)$ परिभाषित किया जाता है

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

कहाँ $X$ असतत समान वितरण को चुना गया है $V$, $Y$ जी के स्वतंत्र सेट (ग्राफ़ सिद्धांत) से अधिक, का संयुक्त वितरण $X$ और $Y$ इस प्रकार कि $X\in Y$ संभाव्यता एक के साथ, और $I(X;Y)$ की पारस्परिक जानकारी है $X$ और $Y$. अर्थात्, यदि हम जाने दें ${\mathcal {I}}$ स्वतंत्र शीर्ष सेट को निरूपित करें $G$, हम संयुक्त वितरण खोजना चाहते हैं $X,Y$ पर $V\times {\mathcal {I}}$ न्यूनतम पारस्परिक जानकारी के साथ, जैसे कि (i) पहले पद का सीमांत वितरण एक समान हो और (ii) वितरण के नमूनों में, दूसरे पद में पहला पद लगभग निश्चित रूप से शामिल हो। की आपसी जानकारी $X$ और $Y$ तब की एन्ट्रापी कहलाती है $G$.

गुण

• एकरसता. अगर $G_{1}$ का एक उपसमूह है $G_{2}$ फिर, उसी शीर्ष सेट पर $H(G_{1})\leq H(G_{2})$.
• उपादेयता। दो ग्राफ़ दिए गए हैं $G_{1}=(V,E_{1})$ और $G_{2}=(V,E_{2})$ शीर्षों के एक ही सेट पर, ग्राफ़ ऑपरेशंस#बाइनरी ऑपरेशंस $G_{1}\cup G_{2}=(V,E_{1}\cup E_{2})$ संतुष्ट $H(G_{1}\cup G_{2})\leq H(G_{1})+H(G_{2})$.
• असंयुक्त संघों का अंकगणितीय माध्य। होने देना $G_{1},G_{2},\cdots ,G_{k}$ शीर्षों के असंयुक्त सेटों पर ग्राफ़ का एक क्रम बनें $n_{1},n_{2},\cdots ,n_{k}$ क्रमशः शीर्ष। तब $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})}$.

इसके अतिरिक्त, ग्राफ़ के कुछ पारिवारिक वर्गों के लिए सरल सूत्र मौजूद हैं।

• पूर्ण संतुलित बहुपक्षीय ग्राफ ़|के-पार्टाइट ग्राफ़ में एन्ट्रॉपी होती है $\log _{2}k$. विशेष रूप से,
  • एज-लेस ग्राफ़ में एन्ट्रापी होती है $0$.
  • पूरा ग्राफ़ चालू करें $n$ शीर्षों में एन्ट्रापी होती है $\log _{2}n$.
  • पूर्ण संतुलित द्विदलीय ग्राफ़ में एन्ट्रापी होती है $1$.
• के साथ द्विदलीय रेखांकन पूरा करें $n$ एक विभाजन में शीर्ष और $m$ दूसरे में एन्ट्रापी है $H\left({\frac {n}{m+n}}\right)$, कहाँ $H$ बाइनरी एन्ट्रॉपी फ़ंक्शन है।

उदाहरण

यहां, हम एक पूर्ण ग्राफ़ का सरल प्रमाण प्रदान करने के लिए ग्राफ़ एन्ट्रॉपी के गुणों का उपयोग करते हैं $G$ पर $n$ शीर्षों को इससे कम के मिलन के रूप में व्यक्त नहीं किया जा सकता $\log _{2}n$ द्विदलीय रेखांकन.

एकरसता का प्रमाण, किसी भी द्विदलीय ग्राफ में पूर्ण द्विदलीय ग्राफ की तुलना में ग्राफ एन्ट्रापी अधिक नहीं हो सकती है, जो कि इससे घिरा है $1$. इस प्रकार, उप-योगात्मकता द्वारा, का मिलन $k$ द्विदलीय ग्राफ़ की एन्ट्रापी इससे अधिक नहीं हो सकती $k$. अब चलो $G=(V,E)$ पर एक पूरा ग्राफ बनें $n$ शिखर. ऊपर सूचीबद्ध गुणों के अनुसार, $H(G)=\log _{2}n$. इसलिए, से कम का मिलन $\log _{2}n$ द्विदलीय ग्राफ़ में समान एन्ट्रापी नहीं हो सकती $G$, इसलिए $G$ ऐसे मिलन के रूप में व्यक्त नहीं किया जा सकता. $\blacksquare$

सामान्य सन्दर्भ

• Matthias Dehmer; Frank Emmert-Streib; Zengqiang Chen; Xueliang Li; Yongtang Shi (25 July 2016). ग्राफ एन्ट्रापी की गणितीय नींव और अनुप्रयोग. Wiley. ISBN 978-3-527-69325-2.

टिप्पणियाँ

[Category:Graph theo