 |
 |
 |
 |
A graph is a finite set of points, called vertices, together with a finite set of lines, called edges, that join some or all of these points. More formally:.
Graphs have pictorial representations in which the vertices are represented by dots and the edges by line segments, as shown by the following diagrams:
|
|
|
|
| A directed graph consists of a finite set V(G) of vertices and a finite set D(G) of directed edges, where each edge is associated with an ordered pair of vertices called its endpoints. This is also known as a digraph. |
For example, consider the following diagram.
Here,
the set of vertices V(G) = {v1,
v2, v3,
v4} and the set of edges
D(G) = { e1,
e2, e3,
e4}
The edge-endpoint function is described by the following table:
| Edges | Endpoints |
|
e1 |
{v1, v2} |
|
e2 |
{v2, v3} |
|
e3 |
{v1, v4} |
|
e4 |
{v4, v1} |
1. Simple Graphs
| A simple graph G is an ordered pair (V, E), where V is a finite nonempty set of nodes (vertices) and E is another finite set of edges of the graph. A simple graph does not contain loops or parallel edges. |
Example: Based on the graph
G shown below,
|
|
V ={v1,
v2, v3,
v4}
E = {{v1, v2}, {v1, v3}, {v1, v4}, {v2, v3}, {v3, v4}) |
Besides the above example, the diagrams shown below are also considered to be simple graphs.
| A simple graph is complete provided that any two vertices
in the graph are adjacent.
A complete graph with n vertices is called
a complete graph on n vertices, and is denoted by Kn.
(K is taken from the German word komplett, meaning "complete.") |
The drawings below represent Kn for each n = 1, 2, 3, 4, 5.
Bipartite graphs : A bipartite graph G is a simple graph whose vertex set can be partitioned into two mutually disjoint nonempty subsets V1 and V2 such that vertices in V1 may be connected to vertices in V2, but no vertices in V1 are connected to other vertices in V1 and no vertices in V2 are connected to other vertices in V2. Consider the following example, the graph G in diagram 1 can be redrawn as shown in diagram 2. In diagram 2, we can see that G is bipartite with mutually disjoint vertex sets V1 = {v1, v3, v4} and V2 = {v2, v5, v6}.
| A complete bipartite graph on (m, n)
vertices, denoted Km, n, is a simple graph with
vertices v1, v2,
...., vm and w1,
w2, ..., wn
that satisfies the following properties:
for all i, j = 1, 2, ..., m and for all k, l = 1, 2, ..., n, 1. There is an edge from each vertex vi to each vertex wk; 2. There is no edge from any vertex vi to any other vertex vj; 3. There is no edge from any vertex wk to any other vertex wl. |
The bipartite graphs K1, 2, K2, 3 and K3, 3 are illustrated below.
4. Subgraphs
| A graph H is a subgraph of G provided that the set of vertices in H is a subset of the set of vertices in G and the set of edges in H is a subset of the set of edges in G. Moreover, every edge in H must have the same endpoints as in G. |
| Example: | List three nonempty subgraphs of the graph G shown below.
|
| Solutions: | 1.  2. 3. Can you think of other subgraphs from G? Try finding them yourself before checking the answer. |
| Let G be a graph and v a vertex of G. The degree of v, denoted deg(v), is the number of edges that are incident with v, with an edge that is a loop counted twice. The total degree of G is the sum of the degrees of all the vertices of G. |
| Example: | Find the degree of each vertex of the graph G shown below
and the total degree of G, then compare
your answer to ours.
. |
Other properties:
For any graph G, the sum of the degrees of all the vertices of G equals twice the number of edges of G. This means that if the vertices of G are v1, v2, ..., vn, where n is a positive integer, then
the total degree of G = deg(v1) + deg(v2) + ... + deg(vn)
= 2 * (the number of edges of G)
| Looking at the previous example, there are three edges in the graph. Hence, the total degree of the graph = 2 * 3 = 6 which is same as the above answer. |  |
Since the total degree of a graph always equals to some multiple of
2, the total degree of the graph is even.
