-{ Brokendust }-

- 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

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!

- About Brokendust - I am a computer science major with a minor in mathematics. My interests include programming, 3d Design and application development. I document everything I do and write articles explaining things both as a way to remember what I have learned before and as way to show others how to accomplish things. I do not post tutorials that do not live up to my expectations. Each article is toughly revised to be quality work. I document advanced computer science topics that are not explained clearly with clear illustrations and step by step algorithm design.

- Current Projects -

3D MGR

ABLL