[Top] [All Lists]

Re: [ontolog-forum] N-ary relationships and hypergraphs

To: ontolog-forum@xxxxxxxxxxxxxxxx
From: "John F. Sowa" <sowa@xxxxxxxxxxx>
Date: Mon, 14 Nov 2011 18:09:14 -0500
Message-id: <4EC19F9A.3070704@xxxxxxxxxxx>
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)

<Prev in Thread] Current Thread [Next in Thread>