ontolog-forum
[Top] [All Lists]

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

 To: ontolog-forum@xxxxxxxxxxxxxxxx "John F. Sowa" Mon, 14 Nov 2011 18:09:14 -0500 <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) ```
 Current Thread Re: [ontolog-forum] Self Interest Ontology, (continued) Re: [ontolog-forum] Self Interest Ontology, Richard Vines Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, Cory Casanave Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, Rich Cooper Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, Cory Casanave Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, AzamatAbdoullaev Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, doug foxvog Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, AzamatAbdoullaev Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, doug foxvog Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, AzamatAbdoullaev [ontolog-forum] N-ary relationships and hypergraphs, Phil Murray Re: [ontolog-forum] N-ary relationships and hypergraphs, John F. Sowa <= Re: [ontolog-forum] N-ary relationships and hypergraphs, Phil Murray Re: [ontolog-forum] N-ary relationships and hypergraphs, John F. Sowa Re: [ontolog-forum] N-ary relationships and hypergraphs, AzamatAbdoullaev Re: [ontolog-forum] N-ary relationships and hypergraphs, doug foxvog Re: [ontolog-forum] N-ary relationships and hypergraphs, AzamatAbdoullaev Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, Cory Casanave Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, AzamatAbdoullaev Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, Ed Barkmeyer Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, Simon Spero Re: [ontolog-forum] N-RELATIONs: Formal Ontology, Semantic Web and Smart Applications, AzamatAbdoullaev