CSD101- Discrete Structures
(Discrete Mathematics)
Fall 2016
Lecture - 14
Graphs
Graphs
• What are graphs?
• A class of discrete structures useful for representing relations
among objects.
• Vertices (nodes) connected by edges.
• Theory about graphs can be used to solve a lot of important
problems
The First Graph Theory
• The first graph theory paper by Leonhard
• Euler in 1736: Seven bridges of Königsberg,
• A town with 7 bridges and 4 pieces of land…
The Origin of Graph Theory
• Can we travel each bridge exactly once and return to the
starting point?
Definition - Graphs
• A graph G = (V, E) is defined by a set of vertices V , and a
set of edges E consisting of ordered or unordered pairs of
vertices from V.
• Thus a graph G = (V, E)
• V = set of vertices
• E = set of edges = subset of V V
• Each edge has either one or two vertices
associated with it, called its endpoints.
• An edge is said to connect its endpoints.
Simple Graphs
• A graph in which each edge connects two different
vertices and where no two edges connect the same pair
of vertices.
Example
Multigraph
• A multigraph: multiple edges
connecting the same nodes
• E.g., nodes are cities, edges are
segments of major highways.
Pseudographs
• Pseudograph: Like a multigraph, but edges connecting a
node to itself are allowed.
Example
Directed Graphs
• A directed graph (or digraph) (V,E) consists of a set of
vertices V and a set of directed edges E on V. 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.
Example
Directed Multigraphs
• A directed multigraph has directed parallel edges.
Example
Types of Graphs: Summary
• Summary of the book’s definitions.
• Keep in mind this terminology is not fully standardized
across different authors...
Graph Models: Acquaintanceship Graph
• Represent whether two people know each other, that is,
whether they are acquainted.
• Each person in a particular group of people is
represented by a vertex.
• Undirected edge is used to connect two people when
these people know each other.
• No multiple edges are used.
• Usually no loops are used. (If we want to include the
notion of self-knowledge, we would include loops.)
Example
An Influence Graph
• A directed edge (a, b) means a can influence b.
• E.g. (Fred, Brian) means Fred can influence Brian.
Example
• Construct an influence graph for the board members of a
company if the President can influence the Director of
Research and Development, the Director of Marketing
and the Director of Operations; the Director of Research
and Development can influence the Director of
Operations; the Director of Marketing can influence the
Director of Operations; and no one can influence, or be
influenced by, the Chief Financial Officer.
Round Robin Tournaments
• A tournament where each team plays each other team
exactly once.
• Such tournaments can be modeled using directed
graphs where each team is represented by a vertex.
Note that (a, b) is an edge if team ‘a’ beats team ‘b’. This
graph is a simple directed graph, containing no loops or
multiple directed edges.
Example
Team 1 is undefeated in this tournament, and Team 3 is winless.
Intersection Graph
• The intersection graph of a collections of sets is the
graph that has a vertex for each of these sets and has
an edge connecting the vertices representing two sets if
these sets have a non empty intersection.
Graph Terminologies
• Adjacent:
Let G be an undirected graph with edge set E. Let e ∈ E be
(or map to) the pair {u,v}. Then we say:
u, v are adjacent / neighbors / connected.
• Edge e is incident with vertices u and v.
• Edge e connects u and v.
• Vertices u and v are endpoints of edge e.
Degree of a Vertex
• Let G be an undirected graph, v ∈ V a vertex.
• The degree of v, deg(v), is its number of incident edges.
(Except that any self-loops are counted twice.)
deg(a) = 3
deg(b) = 5
deg(c) = 5
deg(d) = 5
deg(e) = 0 (isolated vertex)
Pendant vertex = with deg . 1
Example
• What are the degrees of vertices of following graph?
• How many edges are there in a graph with 10 vertices
each of degree six?
Handshaking Theorem
• Let G be an undirected (simple, multi-, or pseudo-) graph
with vertex set V and edge set E. Then
deg(v) 2 E
vV
• deg(a)=3, deg(b)=5, deg(c)=5, deg(d)=5, deg(e)=0
deg(v) deg(a) deg(b) deg(c) deg(d ) deg(e) 18 2 | E |
v{ a ,b ,c , d ,e}
Handshaking Theorem
• Any undirected graph has an even number of vertices of
odd degree.
• Let and be the set of vertices of even and odd degrees
respectively, in an undirected graph, then
2e deg(v) deg(v) deg(v)
vV vV1 vV2
• || has to be even.
Directed Degree
• When is an edge of the graph G with directed edges, is
said to be adjacent to . The vertex is called the initial
vertex of , and is called the terminal or end vertex of
• The initial vertex and terminal vertex of a loop are the
same.
Directed Degree
• Let G be a directed graph, v a vertex of G.
• The in-degree of v, , is the number of edges with as their
terminal vertex.
• The out-degree of v, , is the number of edges with as
their initial vertex.
• The degree of v, is the sum of v’s in-degree and out-
degree.
• Loop at a vertex contributes 1 to both the in-degree and
the out-degree of this vertex.
Example
• Determine in/out-degree of each node
•
•
Theorem
• Let be a graph with directed edges then
deg
vV
(v ) deg
vV
(v ) E
Chapter Exercise
• Chapter # 10
• Topic # 10.1
• Q – 1,3,4,5,6,7,8,9,13,16,19,21,22
• Topic # 10.2
• Q -1,2,3,4,7,8,9,10,21,22,23,24,27
• Topic # 10.3
• Q – 1,2,3,4,5,6,7,8,10,11,12,13,14,15,16,17,18,19,20,21,
22,23,24,26,27
