On 11/14/2011 8:32 AM, Phil Murray wrote:
> Are hypergraphs sufficiently well understood and accepted
> as a modeling tool for similar [n-ary] requirements? (01)
Every hypergraph can be converted to and from a bipartite graph.
Some definitions: (02)
1. A graph is defined as a set of nodes N and a set of arcs A.
Every arc in A is a pair of two nodes (x,y) from N (with
the possibility that nodes x and y may be the same -- a loop).
In diagrams, the arc is usually drawn as a line (straight
or curved) that connects x and y. (03)
2. A hypergraph is a also a set of nodes N and a set of arcs A.
But the arcs of a hypergraph are n-tuples of nodes in N.
If n=2 for all arcs, then the hypergraph is identical to
an ordinary graph. (04)
Note that every graph is a hypergraph, but not every hypergraph
is a graph. But it is possible to map any hypergraph to or
from a bipartite graph: (05)
3. A bipartite graph is defined by three sets: a set N1 of
nodes, a set N2 of nodes, and a set A of arcs that connect
one node in set N1 to one node in N2. (06)
Given this definition of bipartite graph and the above definition
of hypergraph, following is a mapping from a hypergraph (N,A) to
a bipartite graph (N1,N2,A'). (07)
- Let N1 of the bipartite graph be the set N of arcs in the
hypergraph. (08)
- Let N2 of the bipartite graph be the set A of the hypergraph. (09)
- For each hypergraph arc a in N2 that has an n-tuple of nodes
in N1 (x1,...,xn), let the set of arcs A' be the set of all
pairs of the form (a,x1),...,(a,xn). (010)
This construction maps any hypergraph graph to a bipartite
graph. The mapping is invertible, and it can map any bipartite
graph to a hypergraph. (011)
When I defined conceptual graphs, i called them bipartite graphs.
But this mapping shows that I could just as well call them hypergraphs.
All the definitions, theorems, and algorithms for one can be mapped
to equivalent definitions, theorems, and algorithms for the other. (012)
There are two reasons why I prefer to call CGs bipartite graphs: (013)
1. Any word that contains the prefix 'hyper-' is scary and
causes people to think it must be a difficult subject. (014)
2. The common conventions for drawing hypergraphs are difficult
to draw and read. But a bipartite graph can be drawn with nodes
of two different shapes (boxes and circles for CGs). Then the
hyperarcs of a hypergraph become ordinary connections between
circles and boxes. (015)
John (016)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J (017)
|