consists of a set 
of vertices together with a set 
of
edges, which are pairs of distinct vertices.
|
A graph consists of a set of vertices together with a set of
edges, which are pairs of distinct vertices.
The graph 
is a subgraph of of 
if 
and 
. Is a spanning subgraph of if 
. And it's
an induced subgraph of if 
has as many edges as possible.
A graph with n vertices and e edges are said to have order n and size e.
A spanning path 
of a graph is called a
Hamiltonian path, and a spanning cycle called a Hamiltonian
cycle. A graph is called Hamiltonian if it has a
Hanmiltonian cycle.
The degree of a vertex is the number of neighbours it has.
The girth of a graph is the length of its shortest cycle. The girth is infinite if the graph is acyclic.
The distance 
between two vertices
u and v is the minimum length of a path from
u to v in the graph. It is infinite if there is no
such path.
The diameter of a graph is the maximum of , over all vertices u and v.
The graph is connected if its diameter is finite.
A connected graph with fewest edges is called a free tree.
A graph is said to be k-partite or k-colorable if its vertices can be partitioned into k or fewer parts, with the endpoints of each edge belonging to different parts.
A 2-partite graph is generally called bipartite, or simply a “bigraph”.
Theorem
Proof. Every subgraph of a bigraph is also a bigraph.
However a cycle of odd length is not a bigraph.
They are much like graphs except that they have arcs instead of edges. Also, their vertices are allowed to have self loops.
The digraph are called simple if there is only one arc from any
vertex 
and 
.
Out-degree of a vertex v is denoted as 
,
in-degree is denoted as 
.
A vertex of in-degree 0 is called a source; a vertex of out-degree 0 is called a sink.
Two arcs are consecutive if the tip of the first is the initial vertex of the second.
Every SGB digraph of order n and size m is built upon a sequential array of n vertex nodes. The m arc nodes are linked in an unstructured memory pool.
Every vertex node has two fields, NAME and ARCS. NAME points to the name of the node; ARCS points to a the first entry of a linked list of all the out-degrees of the node.
Every arc node has two fields TIP and NEXT. TIP represents the tip of the arc while NEXT points to the next arc in the linked list of all out-degrees.
The complement of graph , denoted 
is obtained by letting
Given two graphs 
and 
, their union 
is
the graph 
.
Every graph leads to a line graph 
, whose vertices are the edge of
; two edges of are adjacent in if they have a
common vertex.
The juxtaposition or direct sum of two graphs and 
,
denoted 
is simply drawing
along side to . The adjacency
matrix of 
where 
is
matrix with all 0's.
The join, denoted by 
,
which consists of together with all edges 
for 
and 
. The direct join 
is
simply join but all the edges 
are directed from
to .
The adjacency matrices are
where 
is matrix with all 1's.
The cartesian product 
of and is a graph whose vertices are
ordered pairs 
, where and . The
edges are 
when 
in or 
when 
in .
The direct product 
,
also called the “conjunction” of and
, or their “categorical
product”, has 
when
in and in H.
The strong product 
combines the edges
of with those of .
The odd product 
has when
we have either or but
not both.
The lexicographic product 
,
also called the “composition” of and
, has
when in ,
and 
when in .