Graph Theory
From DocR21
Graph theory is an area of mathematics that has been incorporated into ACIS to provide additional functionality in Boolean operations and sweeping. The graph theory subsystem residing in ACIS is generalized and may be applied in other areas of geometric modeling.
A graph is a mathematical abstraction of relationships. Many real-world situations can conveniently be described through a diagram or graph consisting of a set of points (nodes or vertices) together with lines (edges) joining various pairs of these points. This graphical representation helps us understand connectivity relationships and is the basis for graph theory.
In graph diagrams, you may be mainly interested in whether or not two vertices are joined by an edge. The manner in which they are joined - long edge, short edge, straight edge, curved edge - is immaterial, and the relative positions of the vertices and edges have no significance. There is no unique way of drawing a graph.
The graph theory subset of ACIS laws provides a generic way of dealing with finite combinations of objects that have some relation to each other. The graph theory laws deal with the discrete, not continuous, part of mathematics.
Contents |
Definitions
- Main article: Graph Theory Definitions
Definitions of basic terms and concepts of graph theory and their implementation are discussed.
Graph Theory in ACIS
- Main article: Graph Theory in Geometric Modeling
Two examples of the use of graph theory in ACIS are described.
Boolean Operations on Graphs
- Main article: Boolean Operations on Graphs
ACIS provides for four types of Boolean operations on graphs: unite, intersect, subtract and lose boundary, and subtract and keep boundary.
Cut Edges and Cut Vertices
- Main article: Cut Edges and Cut Vertices
Certain edges and vertices can be categorized as cut edges and vertices.
Ordering Graphs
- Main article: Ordering Graphs
Ordering a graph is a fundamental graph operation. The generic_graph class provides several methods to order graphs.
Other Ways to Create Graphs
- Main article: Other Ways to Create Graphs
Several additional means to create graphs are described.
See Also
For an interesting historical perspective on graph theory, refer to Seven Bridges of Königsberg.
