[Home] [Essays] [Book_Reviews] [Tools] [Links] [News] [Blog] [About]

Page 6

Appendix 1: Graph Theory Cheat Sheet19

Appendix 2: References. 20

Appendix 3: Relevant web sites. 21

Appendix 1: Graph Theory Cheat Sheet

A Graph has Vertices and Edges.

Edges Join vertices. (synonyms; Vertex:Node).

The count of the number of edges which have the vertex as an end point is the Degree of that vertex.

Concepts:

-          Multiple Edges between the same two vertices

-          Loop, an edge from a vertex to the same vertex

-          Two vertices are Adjacent when joined by an edge; two edges are Adjacent when they have a shared vertex

-          A Weight is a value assigned to an edge, a graph with weighted edges is a Weighted Graph
 

-          Vertices are Incident to the edge joining them

-          Simple Graph has no loops or multiple edges

-          Digraph is a graph where the edges have a direction (Directed Graph)
 

-          An edge in a Digraph is called an Arc

-          In a digraph, the degree of a vertex is the out-degree for arcs out of the vertex and the in-degree for arcs into the vertex

-          A Vertex with In-degree of 0 is a Source and a Vertex with Out-degree of 0 is a Sink

-          Subgraph is defined in terms of a Graph minus edges; G – {e,f,g} (where e,f,g are edges)

-          an End Vertex has degree of 1; an Isolated Vertex has degree of  0

-          A Walk is a sequence of edges, from the Initial Vertex to the Final Vertex.  The length of a walk is the number of edges.

-          A Path is a walk in which no vertex appears more than once.

-          A Trail is a walk where no edge appears more than once

-          A walk is Closed when the Initial Vertex is the same as the Final Vertex

-          A Cycle is a walk where the start vertex is the end vertice.

-          A Connected Graph is in one piece

-          A Disconnected Graph is one with more than one piece

-          A Tree is a graph with 1 path between each pair of vertices.

-          A Forest is a disconnected graph where each graph is a tree

-          Planar Graph is a graph that can be redrawn without edges crossing

Graphs can be represented non visually as lists & matrices.

Graph Types: Null, Complete, Cycle, Path, Wheel, Regular, Biparite, Cubes, Simple, Eulerian, Hamiltonian, Isomorphic

Recommended References

• Introduction to Graph Theory, Robin J. Wilson, 1996, Longman
• Graph Theory Techniques in Model Based Testing, Harry Robinson, http://www.geocities.com/harry_robinson_testing/graph_theory.htm