1
$\begingroup$

A digraph is defined as $G=(V,E,\phi)$ with

  • a set of nodes $V$
  • a set of edges $E$
  • a mapping $\phi : E \rightarrow V \times V$

A weighting $\mathcal{W}$ for a directed graph $G=(V,E,\phi)$ is a mapping $E \rightarrow R$ from $E$ to a ring $R$. This ring is considered to be the noncommutative polynomial ring $R=\mathbb{C}\left<\Sigma\right>$ over an alphabet $\Sigma$.

Let $\Sigma$ be an alphabet. The addition and multiplication on the set $\mathbb{C}\langle \Sigma \rangle := \left\{ \sum_{w \in \Sigma^*} a_w w ~|~\begin{array}{c} a_w \in \mathbb{C} \\ a_w = 0/; \mbox{for almost all } w \in \Sigma^* \end{array} \right\}$ are defined by $(\sum_{w \in \Sigma^*} a_w w) + (\sum_{w \in \Sigma^*} b_w w) := \sum_{w \in \Sigma^*} (a_w + b_w) w.$

$(\sum_{w \in \Sigma^*} a_w w) \cdot (\sum_{w \in \Sigma^*} b_w w) := \sum_{w \in \Sigma^*} (\sum_{uv = w} a_ub_v) w.$

The set $\mathbb{C}\left<\Sigma\right>$ describes in combination with the given definitions for addition and multiplication a ring with 1.


Hi!

I do understand what a directed graph is, and I generally understand what a weighted direct graph is as well. But I have only used integers for the weightings before.

Could you please explain to me what this ring is (could you please provide a simple example) and how I might understand the last sentence?

Thank you in advance!

1 Answers 1

2

A simple example: take $\Sigma$ to be $\lbrace x,y\rbrace$. Then ${\bf C}\langle\Sigma\rangle$ is all the polynomials in $x$ and $y$ with complex coefficients, but with one twist: while you add these things as usual, when you come to multiply them, $xy$ is not the same as $yx$. So that means ${\bf C}\langle\Sigma\rangle$ contains things like $\pi ix^2y^3x^4y^5+\sqrt2yxyxyxy$, and you can't simplify, say, $xyx$ to $x^2y$.

Do you know what a ring is? If so, can you see that with this definition ${\bf C}\langle\Sigma\rangle$ is a ring?

  • 0
    Myerson thank you very much!2011-06-27