Graph Theory (Part 1)

Table of Contents

1. Definitions
   1. Examples
2. Definitions for Nondirected Graphs
   1. Example
3. Definitions for Directed Graphs
   1. Example
4. General Definitions for Any Graph
5. Additional Terminology
6. Weighted Graphs

• A graph G is a pair of sets (V,E), where V is a set of vertices and E is a set of edges, and a relation R which defines a mapping between V and E.
• If G is a nondirected graph then the elements of E are unordered pairs of vertices.
  • We say that an edge {u,v} joins the vertices u and v.
  • Order does not matter, so edge {u,v} is the same as {v,u}.
• If G is a directed graph or digraph then the elements of E are ordered pairs of vertices, i.e. E is a subset of V X V.
  • Therefore, the edge {u,v} is not the same as {v,u} unless u=v.
  • An edge is said to be from u to v.
• An edge that joins a vertex to itself is called a self-loop or loop

                     ---
                    |   |
                    V   |
       o----------->o---
       v1           v2
  

• A graph with no loops is called simple.

Nondirected Graph                         Directed Graph
-----------------                         -----------------
V = {v1, v2, v3, v4}                      V = {v1, v2, v3, v4}
E = {{v1,v2},{v1,v3},{v2,v3},{v3,v4}}     E = {{v1,v3},{v3,v4},{v4,v3},{v4,v2}}

 v1  o---------o  v2                      v1 o           o v2
      \       /                              |           ^ 
       \     /                               |           |
        \   /                                |           |
         \ /                                 |           |
          o  v3                              V           | v4
          |                               v3 o<----------o<--
          |                                  |               |
          o  v4                               ---------------

• For a nondirected graph G=(V,E)
  • if e=uv in E (i.e. if uv is an edge of a graph G) then u and v are each incident on both u and v.
  • two vertices u and v are adjacent in a graph G if uv in E.
  • if uv and uw are distinct edges of a graph G (i.e. v ~= w), then uv and uw are adjacent edges.
  • the degree of a vertex v is the number of edges incident on it. It is written degreeG(v) or deg(v). If a vertex has a self-loop then we count it twice.
  • a vertex of degree 0 is called an isolated vertex.
  • the minimum degree of any vertex in G is written d(G) and the maximum degree of any vertex is written ^(G).

• v1v3 and v3v4 are adjacent edges
• v1 is adjacent to v3 and v1 is not adjacent to v2
• v2 and v4 each are incident to v2v4
• vertex degrees
  • deg(v1) = 1
  • deg(v2) = deg(v4) = 2
  • deg(v3) = 3
  • deg(v5) = 0
• minimum degree = 0 and maximum degree = 3
• v5 is an isolated vertex

     v1 o    o v2
        |   /|
        |  / |   o v5
        | /  |
        |/   |
     v3 o----o v4

• For a directed graph G=(V,E)
  • an edge xy is said to be incident from x and incident to y and incident on both x and y.
  • if there is an edge in E from x to y, then x is said to be adjacent to y and x and y are adjacent or neighbours.
  • in the directed edge (u,v), the vertex u is called the initial vertex.
  • in the directed edge (u,v), the vertex v is called the terminal or end vertex.
  • the in-degree of a vertex v, denoted by deg-(v), is the number of edges with v as their terminal vertex.
  • the out-degree of a vertex v, denoted by deg+(v), is the number of edges with v as their initial vertex.

• edge (a,d) is incident from a and incident to d
• a is adjacent to d
• Vertex degrees:

     Vertex  In-degree  Out-degree
     ------  ---------  ----------
       a        0          2
       b        2          0
       c        0          1
       d        1          0

     a o---------->o d
       |
       |
       |
       |
       V
     b o<----------o c

• V(G) and E(G) will represent its vertices and edges respectively.
• We will always assume that graphs have a finite number of vertices and edges, i.e. V(G) is a finite set which implies that E(G) is also finite and so we say that G is finite.
• |V(G)| is the number of vertices in G and is called the order of G.
• |E(G)| is the number of edges in G and is called the size of G.