 Home  Forums  Projects  Articles  Snippets 
 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: AD, DA, BC, CB, DC, CD, DE, ED. 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 connected.
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 

