- Graph Theory - Graphs are the mathematical representation of relationships between objects. Graphs contain a
given number of vertices. These vertices are connected together by edges.
A simple graph
Above is an example of a simple graph. The graph contains vertices "A, B, C, D and E". Every adjacency is listed in
what either an adjacency list or adjacency array.
• Adjacency List - The adjacencies of the vertices can be described in an adjacency list as:
A|D, D|A, B|C, C|B, D|C, C|D, D|E, E|D. To represent the graph in an adjacency array a matrix
( Number of Vertices by Number of Vertices ) must be created. For the graph above would result in the following:
This matrix is a representation of the graph above.
• Adjacency Matrix -The matrix represents how many vertices there are, how many connections and if they are
directed or undirected. Starting with the left side (rows) find the selected vertex. Follow the row of the selected
vertex and if an 'X' appears in the same row this is a edge connection. If the vertex in that column does not have a link
to the original selected vertex the selected vertices edge to the second vertex is directed. For example: Take the
edge on row 'A' and column 'D'. If there was no 'X' on row 'D' column 'A' the edge would be directed from vertex 'A'
to vertex 'D'.
• Directed Edge - A line connecting two vertices that only allows travel in one direction. Directed edges are usually
represented by an arrow. (->)
• Undirected Edge - A line connecting two vertices that allows travel in both directions. Undirected edges are usually
represented by a single line. (-)
• Weighted Edge - An edge becomes weighted if there is a cost of traveling along that edge.
• Directed Graph - If a graph of vertices contains a directed edge the graph is then directed.
The graph shown has 3 directed edges. The only paths from
vertex 'A', 'C' and 'E' are to vertex 'D'.
• Undirected Graph - If a graph of vertices contains no directed edges the graph is undirected.
• Weighted Graph - If a graph of vertices contains a weighted edge the graph is weighted.
The graph shown has numbers on the edges designating the value
of the edge beside it.
• Unweighted Graph - If a graph of vertices contains no weighted edges the graph is unweighted.
• Connected - If every vertex of the graph is connected to at least one other through any edge the graph is
The graph shown is connected because there are not isolated vertices
however is not fully connected because each vertex does not have
a connection to every other vertex.
• Fully Connected - If every vertex in the graph is connected to every other vertex the graph is fully connected.
Graph shows 4 vertices. Each vertex has a connection to all other vertices.
• Isolated Vertex - If a vertex has no edge connection to any other vertex then the vertex is isolated. This also
becomes a sub graph of the parent graph.
The graph shows 4 vertices. Vertices 'A' and 'E' are isolated
• Sub Graph - A graph that has isolated graphs within a parent graph. This means the number of vertices in
the graph cannot be reached from a given vertex 'X'. A single isolated vertex also counts a sub graph.
The graph shows 2 sub graphs. The first sub graph contains vertices 'A' and 'C'
The second sub graph contains vertices 'D' and 'E'
• Shortest Path - The shortest path is the analyzation of each route from one vertex to another returning with
the shortest path between them. This is the permutation of the number of vertices which becomes N!
- Current Projects -