- A,B,C,D and E are vertices
- AB, BC, CD etc are edges
- the whole diagram is called a graph.
- The degree of a vertex is the number of edges with that vertex as an end-point; B is degree 2, written as deg(B)
- Graphs with no loops or multiple edges, such as the graph in 1, are called simple graphs.
-
Directed graph with walks between edges
- A walk is a ‘way of getting from one vertex to another’, and consists of a sequence of edges, one following after another. For example, in above figure P —> Q—>R is a walk of length 2, and P —> S —> Q —> T —> S —> R is a walk of length 5. A walk in which no vertex appears more than once is called a path; for example, P—> T—> S —> R is a path. A walk of the form Q—> S—> T—> Q is called a cycle.
- walks that include every edge or every vertex exactly once, ending at the initial vertex; such graphs are called Eulerian and Hamiltonian graphs.
- Two graphs Gl and G2 are isomorphic if there is a one-one correspondence between the vertices of Gx and those of G2 such that the number of edges joining any two vertices of Gx is equal to the number of edges joining the corresponding vertices of G2.
- We say that two vertices v and w of a graph G are adjacent if there is an edge vw joining them, and the vertices v and w are then incident with such an edge.
- A graph whose edge-set is empty is a null graph.
-
Matrix representation of graphs for computer storage. If G is a graph with vertices labelled {1, 2, …,n} , its adjacency matrix A is the n x n matrix whose ij-th entry is the number of edges joining vertex i and vertex j . If, in addition, the edges are labelled {1, 2,… , m}, its incidence matrix M is the n x m matrix whose ij-th entry is 1 if vertex i is incident to edge;, and 0 otherwise.
- A simple graph in which each pair of distinct vertices are adjacent is a complete graph.
