请输入您要查询的字词:

 

单词 GraphtheoreticRepresentationOfRelationComposition
释义

graph-theoretic representation of relation composition


\\PMlinkescapephrase

complex\\PMlinkescapephraseComplex\\PMlinkescapephrasedyadic\\PMlinkescapephraseDyadic

There is another form of representation for 2-adic relationsMathworldPlanetmath that is useful to keep in mind, especially for its ability to render the logic of many complex formulasMathworldPlanetmathPlanetmath almost instantly understandable to the mind’s eye. This is the representation in terms of bipartite graphsMathworldPlanetmath (http://planetmath.org/BipartiteGraph), 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---------------------------------------oFigure 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---------------------------------------oFigure 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 (http://planetmath.org/CompositionOfRelations) GH, 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 equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to a single directed edge between those nodes in the composite bigraph for GH.

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---------------------------------------oFigure 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---------------------------------------oFigure 12.  G Composed With H

Once again we find that GH = 4:4.

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

Keeping to the same space X={1,2,3,4,5,6,7}, define the 2-adic relations M,NX×X as follows:

M=2:1+2:2+2:3+4:3+4:4+4:5+6:5+6:6+6:7N=1:1+2:1+3:3+4:3+4:5+5:5+6:7+7:7

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---------------------------------------oFigure 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---------------------------------------oFigure 14.  Dyadic Relation N

To form the composite relation MN, 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 MN.

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---------------------------------------oFigure 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---------------------------------------oFigure 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 MN between i and j in X is given as follows:

(MN)ij=kMikNkj.

Graphically interpreted, this is a sum over paths. Starting at the node i, Mik being 1 indicates that there is an edge in the bigraph of M from node i to node k, and Nkj being 1 indicates that there is an edge in the bigraph of N from node k to node j. So the 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 NM, 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---------------------------------------oFigure 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---------------------------------------oFigure 18.  N Composed With M

In sum, NM=0. This example affords sufficient evidence that relational compositionPlanetmathPlanetmath, just like its kindred, matrix multiplication, is a non-commutative algebraic operation.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 1:53:49