Introduction to Graphs

Graph

A graph G=(V,E) consists of V, a nonempty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.

Types of Graphs

1. Directed Graphs

A directed graph (or digraph) (V,E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u,v) is said to start at u and end at v.

2. Undirected Graph

   All edges are bidirectional. If vertex A is connected to vertex B, then B is also connected to A.

3. Weighted Graph

   Each edge has an associated weight, which could represent a cost, distance, or any other metric.

4. Unweighted Graph

   All edges are treated equally without any weights or costs.

Graph Terminologies

Degree of a Vertex

Neighbourhood

Isolated Vertex

Pendant Vertex

In-degree Vertex

Out-degree Vertex

Example - 1

In G, deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d) = 1, deg(e) = 3, and deg(g) = 0. The neighborhoods of these vertices are N(a)={b,f}, N(b)={a,c,e,f}, N(c)={b,d,e,f}, N(d)={c}, N(e)={b,c,f}, N(f)={a,b,c,e}, and N(g)=∅. In H, deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, and deg(d) = 5. The neighborhoods of these vertices are N(a)={b,d,e}, N(b)={a,b,c,d,e}, N(c)={b}, N(d)={a,b,e}, and N(e)={a,b,d}

Example-2

$$ $$ The in-degrees in graph ( G ) are as follows: $$ \deg^-(a) = 2, \quad \deg^-(b) = 2, \quad \deg^-(c) = 3, \quad \deg^-(d) = 2, \quad \deg^-(e) = 3, \quad \deg^-(f) = 0 $$ The out-degrees are as follows: $$\deg^+(a) = 4, \quad \deg^+(b) = 1, \quad \deg^+(c) = 2, \quad \deg^+(d) = 2, \quad \deg^+(e) = 3, \quad \deg^+(f) = 0$$

Handshaking Theorem

References:

[1] DISCRETE MATHEMATICS AND ITS APPLICATIONS, SEVENTH EDITION