Ring-sum

Материал из WEGA
Перейти к навигации Перейти к поиску

Ring-sum --- кольцевая сумма.

The ring-sum of two graphs [math]\displaystyle{ G_{1} = (V_{1},E_{1}) }[/math] and [math]\displaystyle{ G_{2} = (V_{2},E_{2}) }[/math], written as [math]\displaystyle{ G_{1} \oplus G_{2} }[/math], is the graph

[math]\displaystyle{ ((V_{1} \cup V_{2}), ((E_{1} \cup E_{2}) \setminus (E_{1} \cap E_{2})). }[/math]

In other words, the edge-set of [math]\displaystyle{ G_{1} \oplus G_{2} }[/math] consists of those edges which are either in [math]\displaystyle{ G_{1} }[/math] or in [math]\displaystyle{ G_{2} }[/math], but not in both. It is easy to see that the operation of ring-sum is both commutative and associative.