Discussion

◼ What is a Graph?

◼ Applications of Graphs

◼ Categorization

◼ Terminology
What is a Graph?
A graph G=(V,E) consists of a finite
nonempty set V, the elements of which are
the vertices of G, and a finite set E of
unordered pairs of distinct elements of V
called edges.
G = ( V, E ) 1 3
Where, V - set of vertices
Vertex
E - set of edges Edge 2 (Node)
4
V = {1, 2, 3, 4, 5}
5
E = { (1,2), (1,3), (1,4), (2,3), (3,5), (4,5) }
Graph applications
◼ Graphs can be used for:
❑ Finding a route to drive from one city to another
❑ Finding connecting flights from one city to another
❑ Determining least-cost highway connections
❑ Designing optimal connections on a computer chip
❑ Implementing automata
❑ Implementing compilers
❑ Doing garbage collection
❑ Representing family histories
❑ Doing similarity testing (e.g. for a dating service)
❑ Pert charts
❑ Playing games
Graph applications
Computer
◼ Computer Networks

Resistor/Inductor/…
◼ Electrical Circuits

◼ Road Map
City
Graph Models
◼ Acquaintanceship Graphs – showing whether two people know each
other, that is, whether they are acquainted.
◼ Influence Graphs – showing whether a person can influence another
(e.g., a → b) by using a directed graph.
◼ The Bollywood Graph – showing whether the actors have worked
together in a movie.
◼ Round-Robin Tournaments – showing if team a beats team b (using
an edge (a, b)) via a directed graph.
◼ Collaboration Graphs – modeling joint authorship of academic papers
(an edge links two people if they have jointly written a paper).
◼ Call Graphs – modeling telephone calls made in a network (can use
either directed multigraphs or undirected ones, depending on the
interest)
◼ The Web Graph – representing hyperlinks between Web pages using a
directed graph. E.g., Web page a links to Web page b via an edge
pointing from a to b.
Structure of the Internet
SOURCE: CISCO SYSTEMS

NAP

Backbone 1 Europe
Japan
Backbone 4, 5, N
NAP Regional A

Backbone 2
NAP
NAP

Backbone 3 Australia

Regional B

MAPS UUNET MAP

Graph Models
◼ Where are we right now?
Graph categorization
◼ Simple Graphs
◼ Multigraphs
◼ Pseudographs
◼ Directed Graphs
◼ Directed Multigraphs
◼ Weighted Graph
Simple Graphs

◼ A simple graph G = (V,E)

consists of:
❑ a set V of vertices or nodes
(V corresponds to the
universe of the relation R),
❑ a set E of edges / arcs / links: unordered pairs of
distinct elements u, v  V, such that uRv.
Multigraphs

◼ Like simple graphs, but there may be more than one

edge connecting two given nodes.
◼ A multigraph G=(V, E, f ) consists of a set V of
vertices, a set E of edges (as primitive objects), and
a function f from E to
{{u,v}| u,vV  uv}. Parallel edges
◼ The edges e1 and e2 are called multiple
or parallel edges if f(e1) = f(e2).
◼ E.g., nodes are cities, edges
are segments of major highways
Pseudographs

◼ Like a multigraph, but edges connecting a

node to itself are allowed.
◼ A pseudograph G=(V, E, f ) where
f:E→{{u,v}|u,vV}. Edge eE is Self loops
a loop if f(e)={u,u}={u}.
◼ E.g., nodes are campsites
in a state park, edges are
hiking trails through the woods.
Directed Graphs

◼ Correspond to arbitrary binary relations R,

which need not be symmetric.
◼ A directed graph (V,E) consists of a set of
vertices V and a binary relation E on V.
◼ E.g.: V = people,
E={(x,y) | x loves y}
Directed Multigraphs

◼ Like directed graphs, but there may be more

than one arc from a node to another.
◼ A directed multigraph G=(V, E, f ) consists of
a set V of vertices, a set E of edges, and a
function f:E→VV.
◼ E.g., V=web pages,
E=hyperlinks. The WWW is
a directed multigraph...
Weighted Graph

◼ A Weighted Graph is a graph where all the

edges are assigned weights

50
1 3
40 30
20
2 40
4
30 5
Graph Terminology

◼ Adjacent, connects, endpoints, degree, initial,

terminal, in-degree, out-degree, complete,
cycles, wheels, n-cubes, bipartite, subgraph,
union.
Adjacency

Let G be an undirected graph with vertices u

and v, and a linking edge e = {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.

Adjacency

◼ Adjacent vertices: If (i,j) is an edge of the

graph, then the nodes i and j are adjacent
◼ An edge (i,j) is Incident to vertices i and j

1 3

Vertices 2 and 5 are not

2 adjacent
4
5
Degree of a Vertex

◼ Let G be an undirected graph with vertex v.

◼ The degree of v, deg(v), is its number of
incident edges. (Except that any self-loops
are counted twice.)
◼ A vertex with degree 0 is isolated.
◼ A vertex of degree 1 is pendant.
A Degree Example

◼ What are the degrees of the vertices in

the graphs G and H as shown below?
In G, deg(a) = 2, deg(b) = deg(c) = deg(f) = 4,
deg(d) = 1, deg(e) = 3 and deg(g) = 0
In H, deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1,
deg(d) = 5
b c d a b c

a f e g e d
Handshaking Theorem

◼ Let G = (V, E) be an undirected (simple,

multi-, or pseudo-) graph with e edges. Then

◼ Corollary: Any undirected graph has an even

number of vertices of odd degree.
Handshaking Theorem Example

◼ How many edges are there in a graph with

ten vertices each of degree six?
The sum of the degrees of the vertices is 6x10 = 60,
it follows that 2e = 60. Therefore, e = 30.
Directed Adjacency

◼ Let G be a directed (possibly multi-) graph,

and let e be an edge of G that is (or maps to)
(u,v). Then we say:
❑ u is adjacent to v, v is adjacent from u
❑ e comes from u, e goes to v.
❑ e connects u to v, e goes from u to v
❑ the initial vertex of e is u
❑ the terminal vertex of e is v
Directed Degree

◼ Let G be a directed graph, v a vertex of G.

❑ The in-degree of v, deg−(v), is the number of
edges going to v.
❑ The out-degree of v, deg+(v), is the number of
edges coming from v.
❑ The degree of v, deg(v)deg−(v)+deg+(v), is the
sum of v’s in-degree and out-degree.
Directed Handshaking Theorem

◼ Let G = (V, E) be a directed (possibly multi-)

graph with vertex set V and edge set E .
Then:

◼ Note that the degree of a node is unchanged

by whether we consider its edges to be
directed or undirected.
Path
◼ Path: A sequence of edges in the graph
◼ There can be more than one path between
two vertices
◼ Vertex A is reachable from B if there is a path
from A to B G
A
Paths from B to D
F
- B, A, D D
- B, C, D B
- C E
Path

◼ Simple Path: A path where all the vertices are

distinct

1 3 1,4,5,3 is a simple
path.
2
4 But 1,4,5,4 is not a
5 simple path.
Length

◼ Length : Sum of the lengths of the edges on

the path.

1 3
Length of the path
2
1,4,5,3 is 3
4
5
Circuit

◼ Circuit: A path whose first and last vertices

are the same

1 3
The path 3,2,1,4,5,3
2 is a circuit.
4
5
Cycle

◼ Cycle: A circuit where all the vertices are

distinct except for the first (and the last)
vertex
1 3
1,4,5,3,1 is a cycle
2
1,4,5,4,1 is not a cycle
4
5