کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1709928 | 1519487 | 2007 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Entropy and a certain cost-minimal coloring of graph vertices
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
مکانیک محاسباتی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Entropy and a certain cost-minimal coloring of graph vertices Entropy and a certain cost-minimal coloring of graph vertices](/preview/png/1709928.png)
چکیده انگلیسی
Let GG be a graph with nn vertices and mm edges and let c:V(G)→{1,2,…,n}c:V(G)→{1,2,…,n} be a vertex coloring. We first view ii as the cost associated with color ii and consider the minimum total cost t(G)=minc∑x∈V(G)c(x)t(G)=minc∑x∈V(G)c(x). An inequality relation between t(G)t(G) and the minimum entropy H(G)H(G) of the color distribution induced by any coloring is obtained as (n/2H(G¯)+1)/2⩽t(G)/n. (G¯ is the complement of GG.) Using t(G)/n⩽m/n+1t(G)/n⩽m/n+1, we have log(n2/(n2−2m))⩽H(G)log(n2/(n2−2m))⩽H(G), and the standard argument of entropy maximization leads to a lower bound on t(G)/nt(G)/n in terms of n,mn,m only. Finally, it is remarked that the results can be extended to a case of more general costs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics Letters - Volume 20, Issue 12, December 2007, Pages 1194–1197
Journal: Applied Mathematics Letters - Volume 20, Issue 12, December 2007, Pages 1194–1197
نویسندگان
Yasuichi Horibe, Ryoji Mitani,