Discrete Mathematics
Course No: CSE 2101
Graphs
Utsha Das
Assistant Professor
,10.1 Graphs and Graph Models
, Graphs
Definition: A graph G = (V, E) consists of
a nonempty set V of vertices (or nodes) and
a set E of edges.
Each edge has either one or two vertices associated with it,
called its endpoints.
An edge is said to connect its endpoints.
v1 v5 G=(V, E), where
V={v1,v2,…, v7}
v3 v4 E={{v1,v2}, {v1,v3}, {v2,v3}
v6
{v3,v4}, {v4,v5}, {v4,v6}
{v4,v7}, {v5,v6}, {v6,v7}}
v2 v7
, Some Terminology
A graph with an infinite vertex set is called an infinite graph.
A graph with a finite vertex set is called a finite graph.
In a simple graph each edge connects two different vertices,
and no two edges connect the same pair of vertices.
Multigraphs may have multiple edges connecting the same
two vertices. When m different edges connect the vertices u
and v, we say that {u, v} is an edge of multiplicity m.
v1 v5
v4
v3 v4 v6
v1
v3
v2 v2 v7
Multi graph
Simple graph
Course No: CSE 2101
Graphs
Utsha Das
Assistant Professor
,10.1 Graphs and Graph Models
, Graphs
Definition: A graph G = (V, E) consists of
a nonempty set V of vertices (or nodes) and
a set E of edges.
Each edge has either one or two vertices associated with it,
called its endpoints.
An edge is said to connect its endpoints.
v1 v5 G=(V, E), where
V={v1,v2,…, v7}
v3 v4 E={{v1,v2}, {v1,v3}, {v2,v3}
v6
{v3,v4}, {v4,v5}, {v4,v6}
{v4,v7}, {v5,v6}, {v6,v7}}
v2 v7
, Some Terminology
A graph with an infinite vertex set is called an infinite graph.
A graph with a finite vertex set is called a finite graph.
In a simple graph each edge connects two different vertices,
and no two edges connect the same pair of vertices.
Multigraphs may have multiple edges connecting the same
two vertices. When m different edges connect the vertices u
and v, we say that {u, v} is an edge of multiplicity m.
v1 v5
v4
v3 v4 v6
v1
v3
v2 v2 v7
Multi graph
Simple graph
