Denote c as the set of all unlabeled finite simple graphs Sh

Denote c as the set of all unlabeled finite simple graphs. Show G is a commutative semiring with identity (a) is commutative (b) is commutative (c) is associative (d) is associative (e) 0 is the additive identity (f) 1 is the multiplicative identity

Solution

A commutative semiring R is defined as an algebraic system (R, +, ·) such that (R, +) and (R, ·) are commutative semigroups, connected by a(b + c) = ab+ac for all a, b, c R, and there exist 0, 1 R such that r+0 = r, r0 = 0r = 0 and r1 = 1r = r for each r R. In this paper all semirings considered will be assumed to be commutative semirings with non-zero identity.

A commutative semiring is a set K with two binary operators “+” and “·” having three axioms, for all a, b, c K.

S1: “+” is commutative (a + b) = (b + a) and associative (a + b) + c = a + (b + c), and additive identity called “0” such that k + 0 = k for all k K. I.e., (K, +) is a commutative monoid.

S2: “·” is also associative, commutative, and multiplicative identity called “1” s.t. k · 1 = k for all k K ((K, ·) is also a comm. monoid).

S3: distributive law holds: (a · b) + (a · c) = a(b + c) for all a, b, c K.

This, and factorization w.r.t. a graph G is all that is necessary for the above message passing algorithms to work. There are many commutative semirings.