Graph Theory has been included here because many 3D standards (such as VRML/X3D) and programming libraries (Java3D) use the concept of a scenegraph. This is related to graph theory. It is also useful for general programming issues including flow diagrams.
Concepts of Graph Theory
A graph G=(N,U) consists of:
- A finite set N={n1,n2,...} of nodes.
- A subset U of the Cartesian product N x N, the elements of which are called arcs.
The diagram above shows the nodes represented by circles, and arcs (ni,nj) are shown by an arrow drawn from the point representing ni to the point representing nj.
The subset of arcs is shown in the following table.
| to node | |||||||
| n1 | n2 | n3 | n4 | n5 | n6 | ||
| from node | n1 | true | true | ||||
| n2 | true | ||||||
| n3 | true | true | |||||
| n4 | true | true | |||||
| n5 | true | true | |||||
| n6 | true | ||||||
Initial and terminal end-points of an arc.
For an arc (ni,nj), the node ni is the initial end-point and the node nj is the terminal end-point.
Adjacent nodes
Two nodes are adjacent if they are joined by an arc.
adjacent arcs.
Two arcs are adjacent if they have at least one common end-point.
Successors of a node.
A node ni is called a successor of a node x if (ni,nj)
U; the set of all successors
of x, is denoted by 
+(ni).
In the example, the successors of n1 are (n2,n4), the other successors are:
| ni | +(ni) |
| n1 | (n2,n4) |
| n2 | (n1) |
| n3 | (n1,n6) |
| n4 | (n3,n5) |
| n5 | (n2,n4) |
| n6 | (n3) |
Predecessors of a node.
A node nj is called a predecessor of ni if (nj,ni)
U, and the set of all predecessors
of n is denoted by -(ni).
For example the predecessors of n1 are (n2,n3), the other predecessors are:
| ni | -(ni) |
| n1 | (n2,n3) |
| n2 | (n1,n1) |
| n3 | (n4,n6) |
| n4 | (n1,n5) |
| n5 | (n4) |
| n6 | (n3) |
Arcs incident to and from a node.
If an arc u has node ni, as its initial end-point, we say that the arc is incident from ni, whereas if an arc u has node ni as its terminal end-point we say that arc u is incident to ni. The number of arcs incident from a node ni is called the out-degree of ni and it is denoted by p+(ni); while the number of arcs incident to ni is calles in-degree of x and is denoted by p-(ni).
From the example:
| ni | p+(ni) | p-(ni) |
| n1 | 2 | 2 |
| n2 | 1 | 2 |
| n3 | 2 | 2 |
| n4 | 2 | 2 |
| n5 | 2 | 1 |
| n6 | 1 | 1 |
Partial graphs.
If we remove from a graph G (N,U) a subset of its arcs, we are left with a graph of the form:
H = (N,V), where V 
U
which is called a partial graph of G.
Subgraphs.
If we remove from a graph G = (X,U) a subsei nodes, together with all the arcs incident to or from nodes, we are left with a graph of the form:
where
M N and Uy=U 
(MxM)
which is called a subgraph of G. We may describe H is precisely, as the subgraph of G generated by Y.
Condensations.
Let P= (nI,n2,...,nJ) be a partition of the node-set of a graph G~(X,U). Then the condensation of G induced by P is the graph G~ = (P,U~) where:
Up={(Nr,Ns) P x P|Xr ~ Ns SA
(]X,CXr,XiCX, (x,x)eU)}
In pictorial terms, G~ is obtained from U by coalescing the nodes of each member of P, and then removing any loops.
