Scribd
Upload
158 views19 pages

Graph Theory Lecture Notes: Narayanan N

The document discusses graph theory concepts including: [1] It introduces graphs using the example of the Bridges of Königsberg problem, where vertices represent land areas and edges represent bridges. [2] It formally defines a graph as an ordered pair of vertices and edges, with an incidence function associating edges to vertex pairs. [3] It provides examples of graphs and discusses basic graph parameters like order and size, representing edges concisely as vertex pairs like "uv".

Uploaded by

maruthamangalam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
158 views19 pages

Graph Theory Lecture Notes: Narayanan N

The document discusses graph theory concepts including: [1] It introduces graphs using the example of the Bridges of Königsberg problem, where vertices represent land areas and edges represent bridges. [2] It formally defines a graph as an ordered pair of vertices and edges, with an incidence function associating edges to vertex pairs. [3] It provides examples of graphs and discusses basic graph parameters like order and size, representing edges concisely as vertex pairs like "uv".

Uploaded by

maruthamangalam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 19

Graph Theory Lecture notes

Narayanan N

Indian Institute of Technology Madras


Bridges of Königsberg

The city of Königsberg had two river islands in the river Pregel and there were
seven bridges connecting the banks and islands as follows.

Is it possible to start from any place, go through each bridge exactly once and
return to the same place?
Leonard Euler: Only relevant piece of information is the existence and number of
bridges connecting two places.
Leonard Euler: Only relevant piece of information is the existence and number of
bridges connecting two places.

Such a walk possible iff we can draw the diagram without lifting pencil.

A diagram such as above is called a graph . The dots are called vertices and the
lines are called the edges of the graph.
Graph
A graph G is an ordered pair (V, E) consisting of a set V = V ( G ) of vertices and a
set E = E( G ), disjoint from V, of edges, together with an incidence function ψG
that associates with each edge of G an unordered pair of (not necessarily distinct)
vertices of G. If e is an edge and u and v are vertices such that ψG (e) = {u, v}, then
e is said to join u and v, and the vertices u and v are called the endpoints of e.

Example
Let V = {1, 2, 3, 4, 5}, E = {{1, 3}, {1, 5}, {2, 4}, {3, 5}, {1, 4}}.

We denote the numbers of vertices and edges in G by | G | and ||( G )||; these two
basic parameters are called the order and size of G, respectively. ‘
For the sake of brevity, we often represent the edge {u, v} by writing uv.

Example
Let G = (V, E) be given by: V = {u, v, w, x, y}, E = { a, b, c, d, e, f , g, h}. Where the
incidence function is given by ψG ( a) = uv, ψG ( a) = uv, ψG (b) = uv, ψG (c) =
uu, ψG (d) = ux, ψG (e) = vx, ψG ( f ) = wy, ψG ( g) = uw, ψG (h) = uy
Graphical representation

We usually think of a graph by identifying the vertices with distinct points on a


surface (like the plane) and edges are represented by simple curves that connect
the points corresponding to the endpoints of the edges.
Two edges are called parallel edges if they both have the same endpoints. If
endpoints of an edge are identical, it is called a loop.

Simple graphs
A graph without having parallel edges or loops is called a simple graph.

multigraphs
A graph is called a multigraph if it allows parallel edges and loops.

Simple graphs
A graph without having loops, but allows parallel edges is called a loopless
multigraph.
• adjacency
• neighbours
• incident
• finite graph
• infinite graph

You might also like