Terminology of Graphs and Networks
Graph - A visual representation of a set X of objects and relationships. Each member of X is represented as a vert ex or node. Relationships are represented by edges or arcs.
Vertex or Node - A point representing a member of the set.
Edge or Arc - A link between vertices. An edge must have a vertex at each end.
Loop - An edge with the same vertex at each end.
Degree (order) of a vertex - The number of edges meeting at the vertex.
Simple graph - Contains no loops and has no more than one edge between any pair of vertices.
Walk - Sequence of edges. The end of each edge (except the last) is the start of the next.
Trail - A walk with no repeated edges.
Path - A trail in which no vertex is repeated.
Cycle - A closed path. The end of the last edge joins the start of the first.
Hamiltonian Cycle - A cycle that visits every vertex and returns to the start vertex
Hamiltonian Path - A path that visits every vertex.
Connected - There is a path between every pair of vertices in a connected graph.
Tree - Simple connected graph with no cycles.
Digraph (directed graph) - Graph with at least one edge having a direction.
Complete graph - A simple graph with each pair of vertices connected by an edge.
Eulerian Graph &-; A graph in which every path can be traversed exactly once without lifting pen from paper. An Eulerian graph is connected and the degree of every vertex is even.
Incidence Matrix - Matrix representation of a graph. Elements of the matrix show the number of edges connecting the vertices represented by the row and column of the matrix.
Isomorphic - Graphs are isomorphic if one can be deformed to make the other. The vertices can be moved and the edges straightened or bent to do this.
Planar graph - A graph that can be drawn such that no edges cross.
Bipartite graph - A graph joining two sets of objects. Every edge starts in one set and ends in the other.