PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (21)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Medium Entry average rating: No information on entry rating
[parent] graph-theoretic representation of relation composition (Example)

There is another form of representation for 2-adic relations that is useful to keep in mind, especially for its ability to render the logic of many complex formulas almost instantly understandable to the mind's eye. This is the representation in terms of bipartite graphs, or bigraphs for short.

Here is what $ G$ and $ H$ look like in the bigraph picture:

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . . . . . ./|\. . . . . . . . . . |
| . . . . . . . / | \ . . . . . . .G. . |
| . . . . . . ./. | .\. . . . . . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 9. G = 4:3 + 4:4 + 4:5

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . . . . .\. | ./. . . . . . . . . |
| . . . . . . . \ | / . . . . . . .H. . |
| . . . . . . . .\|/. . . . . . . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 10. H = 3:4 + 4:4 + 5:4

These graphs may be read to say:

$ G$ puts $ 4$ in relation to $ 3, 4, 5$.
$ H$ puts $ 3, 4, 5$ in relation to $ 4$.

To form the composite relation $ G \circ H$, one simply follows the bigraph for $ G$ by the bigraph for $ H$, here arranging the bigraphs in order down the page, and then treats any non-empty set of paths of length two between two nodes as being equivalent to a single directed edge between those nodes in the composite bigraph for $ G \circ H$.

Here's how it looks in pictures:

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . . . . . ./|\. . . . . . . . . . |
| . . . . . . . / | \ . . . . . . .G. . |
| . . . . . . ./. | .\. . . . . . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . . . . .\. | ./. . . . . . . . . |
| . . . . . . . \ | / . . . . . . .H. . |
| . . . . . . . .\|/. . . . . . . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 11. G Followed By H

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . . . . . . | . . . . . . . . . . |
| . . . . . . . . | . . . . . . .G o H. |
| . . . . . . . . | . . . . . . . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 12. G Composed With H

Once again we find that $ G \circ H$ = $ 4:4$.

To see the utility of the bigraph picture of 2-adic relations, let us devise a slightly more complex example of a composition problem, and use it to illustrate the logic of the matrix multiplication formula.

Keeping to the same space $ X = \{ 1, 2, 3, 4, 5, 6, 7 \}$, define the 2-adic relations $ M, N \subseteq X \times X$ as follows:

\begin{displaymath}\begin{array}{lcccccc} M & = & 2\mathrm{:}1 + 2\mathrm{:}2 + ... ...}5 + 5\mathrm{:}5 + 6\mathrm{:}7 + 7\mathrm{:}7 \ \end{array}\end{displaymath}

Here are the bigraph pictures:

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . ./|\. . ./|\. . ./|\. . . . . . |
| . . . / | \ . / | \ . / | \ . . .M. . |
| . . ./. | .\./. | .\./. | .\. . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 13. Dyadic Relation M

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . | ./. . | ./.\. | . .\. | . . . . |
| . . | / . . | / . \ | . . \ | . .N. . |
| . . |/. . . |/. . .\| . . .\| . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 14. Dyadic Relation N

To form the composite relation $ M \circ N$, one simply follows the bigraph for $ M$ by the bigraph for $ N$, here arranging the bigraphs in order down the page, and then counts any non-empty set of paths of length two between two nodes as being equivalent to a single directed edge between those two nodes in the composite bigraph for $ M \circ N$.

Here's how it looks in pictures:

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . ./|\. . ./|\. . ./|\. . . . . . |
| . . . / | \ . / | \ . / | \ . . .M. . |
| . . ./. | .\./. | .\./. | .\. . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . | ./. . | ./ \. | . .\. | . . . . |
| . . | / . . | / . \ | . . \ | . .N. . |
| . . |/. . . |/. . .\| . . .\| . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 15. M Followed By N

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . ./.\. . ./.\. . ./.\. . . . . . |
| . . . / . \ . / . \ . / . \ . .M o N. |
| . . ./. . .\./. . .\./. . .\. . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 16. M Composed With N

Let us hark back to that mysterious matrix multiplication formula, and see how it appears in the light of the bigraph representation.

The coefficient of the composition $ M \circ N$ between $ i$ and $ j$ in $ X$ is given as follows:

$ (M \circ N)_{ij} = \sum_{k} M_{ik} N_{kj}.$

Graphically interpreted, this is a sum over paths. Starting at the node $ i$, $ M_{ik}$ being 1 indicates that there is an edge in the bigraph of $ M$ from node $ i$ to node $ k$, and $ N_{kj}$ being 1 indicates that there is an edge in the bigraph of $ N$ from node $ k$ to node $ j$. So the $ \sum_{k}$ ranges over all possible intermediaries $ k$, ascending from 0 to 1 just as soon as there happens to be some path of length two between nodes $ i$ and $ j$.

It is instructive at this point to compute the other possible composition that can be formed from $ M$ and $ N$, namely, the composition $ N \circ M$, that takes $ M$ and $ N$ in the opposite order. Here is the graphic computation:

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . | ./. . | ./.\. | . .\. | . . . . |
| . . | / . . | / . \ | . . \ | . .N. . |
| . . |/. . . |/. . .\| . . .\| . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . ./|\. . ./|\. . ./|\. . . . . . |
| . . . / | \ . / | \ . / | \ . . .M. . |
| . . ./. | .\./. | .\./. | .\. . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 17. N Followed By M

o---------------------------------------o
| . . . . . . . . . . . . . . . . . . . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . . . . . . . . . . . . . . . . . . |
| . . . . . . . . . . . . . . . .N o M. |
| . . . . . . . . . . . . . . . . . . . |
| . . o . o . o . o . o . o . o . .X. . |
| . . 1 . 2 . 3 . 4 . 5 . 6 . 7 . . . . |
| . . . . . . . . . . . . . . . . . . . |
o---------------------------------------o
Figure 18. N Composed With M

In sum, $ N \circ M = 0$. This example affords sufficient evidence that relational composition, just like its kindred, matrix multiplication, is a non-commutative algebraic operation.



"graph-theoretic representation of relation composition" is owned by Jon Awbrey.
(view preamble | get metadata)

View style:

See Also: algebraic representation of relation composition, geometric representation of relation composition, matrix representation of relation composition

Keywords:  bigraph, bipartite graph, binary relation, dyadic relation, graph, relation, relation composition

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: operation, algebraic, non-commutative, relational composition, sufficient, opposite, point, ranges, coefficient, matrix multiplication, composition, utility, composite, edge, nodes, length, paths, order, graphs, terms, formulas, logic, relations, representation
There is 1 reference to this entry.

This is version 6 of graph-theoretic representation of relation composition, born on 2008-02-22, modified 2008-02-24.
Object id is 10314, canonical name is GraphTheoreticRepresentationOfRelationComposition.
Accessed 345 times total.

Classification:
AMS MSC: 03B10 (Mathematical logic and foundations :: General logic :: Classical first-order logic)
 03E20 (Mathematical logic and foundations :: Set theory :: Other classical set theory )
 05B20 (Combinatorics :: Designs and configurations :: Matrices )
 05B30 (Combinatorics :: Designs and configurations :: Other designs, configurations)
 05C65 (Combinatorics :: Graph theory :: Hypergraphs)
 08A02 (General algebraic systems :: Algebraic structures :: Relational systems, laws of composition)
 68P15 (Computer science :: Theory of data :: Database theory)
 68R01 (Computer science :: Discrete mathematics in relation to computer science :: General)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)