35 Graphs Trees

Graph Theory: Intro and Trees
CS 2800: Discrete Structures, Spring 2015
Sid Chaudhuri
This is ok
(Ok because equality is symmetric and transitive)

implied if you omit them
This is NOT ok
⇒
These ⇒ symbols are
⇒
⇒
⇒
⇒
… which is true, so QED No!
Plea for the Day #1
Please read out your proofs in plain

English and ask yourself if it makes sense
http://www.plainenglish.co.uk/
Plea for the Day #2
Plain English is often better than

“mathy” notation
Instead of “∀d∈Days,Rainy(d)⇒Umbrella(d)”, say

“If it's a rainy day, I will carry an umbrella”
(Which is easier to read and debug?)

(But do be precise and terse)
(This is an acquired skill – look at lots of well-written proofs)
<modest>... such as the homework and prelim solutions</modest>
These aren't the graphs we're interested in
This is
V.J. Wedeen and L.L. Wald, Martinos Center for Biomedical Imaging at MGH
And so is this
A social graph
An older social graph
A fictional social graph
A transport graph
Another transport graph
A circuit graph (flip-flop)
A circuit graph (Intel 4004)
A circuit graph (Intel Haswell)
A probabilistic graphical model
P(C=F) P(C=T)
0.5 0.5
C P(S=F) P(S=T) Cloudy C P(R=F) P(R=T)

F 0.5 0.5 F 0.8 0.2
T 0.9 0.1 T 0.2 0.8
Sprinkler Rain
P(W, R, S, C) =
P(W | R, S) Wet grass R S P(W=F) P(W=T)
× P(R | C) F F 1.0 0.0

T F 0.1 0.9
× P(S | C) F T 0.1 0.9
× P(C) T T 0.01 0.99
This is a graph(ical model) that has learned
to recognize cats
Some abstract graphs
K5
K3,3
=
What is a graph?
A
● An undirected graph G = (V, E)
consists of D
C
– A non-empty set of vertices/nodes V B
– A set of edges E, each edge being a set of one or two vertices (if
one vertex, the edge is a self-loop)
A
● A directed graph G = (V, E)
consists of D
C
– A non-empty set of vertices/nodes V B
– A set of edges E, each edge being an ordered pair of vertices (the

first vertex is the “start” of the edge, the second is the “end” )
● That is, E ⊆ V × V, or E is a relation from V to V
Multigraphs
D
C
● Multiple edges between same pair of vertices

● Need a different representation (not a relation)
Adjacency, Incidence and Degree
● Two vertices are adjacent iff there is an edge between
them
● An edge is incident on both of its vertices
● Undirected graph:
– Degree of a vertex is the number of edges incident on it
● Directed graph:
– Outdegree of a vertex u is the number of edges leaving it,
i.e. the number of edges (u, v)
– Indegree of a vertex u is the number of edges entering it,
i.e. the number of edges (v, u)
Paths
● A path is a sequence of vertices v0, v1, v2 … vn, all different except
possibly the first and the last, such that
– (in an undirected graph) every pair {vi, vi + 1} is an edge
– (in a directed graph) every pair (vi, vi + 1) is an edge
● Alternatively, a path may be defined as a sequence of distinct
edges e0, e1, e2 … en such that
– Every pair ei, ei + 1 shares a vertex
– These vertices are distinct, except possibly the first & the last
– If the graph is directed, then the end vertex of ei is the start vertex
of ei + 1 (the “arrows” point in a consistent direction)
● We will use these interchangeably
● A cycle is a path with the same first and last vertex
Connectedness
● An undirected graph is connected iff for every pair of
vertices, there is a path containing them
● A directed graph is strongly connected iff it satisfies the
above condition for all ordered pairs of vertices (for
every u, v, there are paths from u to v and v to u)
● A directed graph is weakly connected iff replacing all
directed edges with undirected ones makes it connected
A A
C D C D
B B
Connected Not connected
Trees
● A forest is an undirected graph with no cycles
A
F G
C D
A B C D E
B
● A tree is a connected forest (← definition)

G
A
E G
C D
B
A B C D E
Identifying trees
● An undirected graph G on a finite set of vertices is a
tree iff any two of the following conditions hold
– |E| = |V| - 1
– G is connected
– G has no cycles
● Any two of these imply the third

● There are many other elegant characterizations of
trees
Proof Sketches
● If G is connected and lacks cycles, then |E| = |V| - 1
– Show that such a graph always has a vertex of degree 1
– Use induction, repeatedly removing such a vertex
● If G is connected and |E| = |V| - 1, then it lacks cycles
– Show that a connected graph has a spanning tree
– Apply the |E| = |V| - 1 formula to the spanning tree
● If G lacks cycles and |E| = |V| - 1, then it is connected
– If disconnected, must have ≥ 2 connected components, each
of which must be a tree
– Sum vertex and edge counts over connected components,
show that they don't add up
Cayley's Formula
● For any positive integer n, the number of trees on
n labeled vertices is nn – 2
2 vertices: 1 tree 3 vertices: 3 trees
if ul
e au t 4 vertices: 16 trees
n y b
Ma roofs!
p

35 Graphs Trees

Uploaded by

Copyright:

Available Formats

35 Graphs Trees

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

35 Graphs Trees

Uploaded by

Copyright:

Available Formats

Graph Theory: Intro and Trees

CS 2800: Discrete Structures, Spring 2015

(Ok because equality is symmetric and transitive)

Please read out your proofs in plain

Plain English is often better than

Instead of “∀d∈Days,Rainy(d)⇒Umbrella(d)”, say

(Which is easier to read and debug?)

C P(S=F) P(S=T) Cloudy C P(R=F) P(R=T)

× P(R | C) F F 1.0 0.0

– A set of edges E, each edge being an ordered pair of vertices (the

● Multiple edges between same pair of vertices

● A tree is a connected forest (← definition)

● Any two of these imply the third

2 vertices: 1 tree 3 vertices: 3 trees

You might also like