graph (Graph)

The Class of graphs, where a graph is understood to be a set of GraphNodes connected by GraphArcs. Note that this Class includes only connected graphs, i.e. graphs in which there is a GraphPath between any two GraphNodes. Note too that every Graph is assumed to contain at least two GraphArcs and three GraphNodes.

Ontology

SUMO / GRAPH-THEORY

Superclass(es)

entity

abstract

graph

Subclass(es)

directed graph tree multi graph pseudo graph

Coordinate term(s)

attribute graph element proposition quantity relation set or class

Constrains relations

cut set fn minimal cut set fn graph part sub graph

Related WordNet synsets

See more related synsets on a separate page.

Axioms (5)

If graph is an instance of graph and node1 is an instance of graph node and node2 is an instance of graph node and node1 is a part of graph and node2 is a part of graph and node1 is not equal to node2, then there exist arc,path so that

arc links node1 and node2
- path is a subgraph of graph
- path is an instance of graph path
- - "the beginning of path" is equal to node1 and "the end of path" is equal to node2
  - "the beginning of path" is equal to node2 and "the end of path" is equal to node1

(=>
      (and
            (instance ?GRAPH Graph)
            (instance ?NODE1 GraphNode)
            (instance ?NODE2 GraphNode)
            (graphPart ?NODE1 ?GRAPH)
            (graphPart ?NODE2 ?GRAPH)
            (not
                  (equal ?NODE1 ?NODE2)))
      (exists
            (?ARC ?PATH)
            (or
                  (links ?NODE1 ?NODE2 ?ARC)
                  (and
                        (subGraph ?PATH ?GRAPH)
                        (instance ?PATH GraphPath)
                        (or
                              (and
                                    (equal
                                          (BeginNodeFn ?PATH)
                                          ?NODE1)
                                    (equal
                                          (EndNodeFn ?PATH)
                                          ?NODE2))
                              (and
                                    (equal
                                          (BeginNodeFn ?PATH)
                                          ?NODE2)
                                    (equal
                                          (EndNodeFn ?PATH)
                                          ?NODE1)))))))

If graph is an instance of graph, then there exist node1,node2,node3,arc1,arc2 so that node1 is a part of graph and node2 is a part of graph and node3 is a part of graph and arc1 is a part of graph and arc2 is a part of graph and node2 links arc1 and node1 and node3 links arc2 and node2 and node1 is not equal to node2 and node2 is not equal to node3 and node1 is not equal to node3 and arc1 is not equal to arc2.

(=>
      (instance ?GRAPH Graph)
      (exists
            (?NODE1 ?NODE2 ?NODE3 ?ARC1 ?ARC2)
            (and
                  (graphPart ?NODE1 ?GRAPH)
                  (graphPart ?NODE2 ?GRAPH)
                  (graphPart ?NODE3 ?GRAPH)
                  (graphPart ?ARC1 ?GRAPH)
                  (graphPart ?ARC2 ?GRAPH)
                  (links ?ARC1 ?NODE1 ?NODE2)
                  (links ?ARC2 ?NODE2 ?NODE3)
                  (not
                        (equal ?NODE1 ?NODE2))
                  (not
                        (equal ?NODE2 ?NODE3))
                  (not
                        (equal ?NODE1 ?NODE3))
                  (not
                        (equal ?ARC1 ?ARC2)))))

graph element is disjoint from graph.

(disjoint GraphElement Graph)

If part is an instance of graph element, then there exists graph graph so that part is a part of graph.

(=>
      (instance ?PART GraphElement)
      (exists
            (?GRAPH)
            (and
                  (instance ?GRAPH Graph)
                  (graphPart ?PART ?GRAPH))))

If graph is an instance of graph, then "the set of minimal paths that partition graph into two separate graphs" is a subclass of "the set of paths that partition graph into two separate graphs".

(=>
      (instance ?GRAPH Graph)
      (subclass
            (MinimalCutSetFn ?GRAPH)
            (CutSetFn ?GRAPH)))