Transcript Slides (PPTX)

Week 11 - Wednesday



What did we talk about last time?
Graphs
Paths and circuits







As I was going to St. Ives
I crossed the path of seven wives
Every wife had seven sacks
Every sack had seven cats
Every cat had seven kittens
Kittens, cats, sacks, wives
How many were going to St. Ives?

A walk from v to w is a finite alternating sequence of
adjacent vertices and edges of G, starting at vertex v and
ending at vertex w
 A walk must begin and end at a vertex





A path from v to w is a walk that does not contain a
repeated edge
A simple path from v to w is a path that does not contain
a repeated vertex
A closed walk is a walk that starts and ends at the same
vertex
A circuit is a closed walk that does not contain a repeated
edge
A simple circuit is a circuit that does not have a repeated
vertex other than the first and last
We can always pin down a walk unambiguously if we
list each vertex and each edge traversed
 How would we notate a walk that starts at v1 and ends
at v2 and visits every edge exactly once in the
following graph?

e2
e1
v1

e4
v2
e3
v3
However, if a graph has no parallel edges, then a
sequence of vertices uniquely determines the walk
Vertices v and w of G are connected iff there is a walk
from v to w
 Graph G is connected iff all pairs of vertices v and w
are connected to each other
 A graph H is a connected component of a graph G iff

 H is a subgraph of G
 H is connected
 No connected subgraph of G has H as a subgraph and
contains vertices or edges that are not in H


A connected component is essentially a connected
subgraph that cannot be any larger
Every (non-empty) graph can be partitioned into one
or more connected components
What if you want to find an Euler circuit or path of your
own?
 If a graph is connected, non-empty, and every node in the
graph has even degree, the graph has an Euler circuit

 If exactly two nodes have odd degree, the graph has an Euler
path

Algorithm to find one:
Pick an arbitrary starting vertex (but you must start on an odd
degree node if there is one)
Move to an adjacent vertex and remove the edge you cross
from the graph
1.
2.
▪
3.
Whenever you choose such a vertex, pick an edge that will not
disconnect the graph
If there are still uncrossed edges, go back to Step 2



An Euler circuit has to visit every edge of a graph exactly once
A Hamiltonian circuit must visit every vertex of a graph exactly once
(except for the first and the last)
If a graph G has a Hamiltonian circuit, then G has a subgraph H with the
following properties:







H contains every vertex of G
H is connected
H has the same number of edges as vertices
Every vertex of H has degree 2
In some cases, you can use these properties to show that a graph does
not have a Hamiltonian circuit
In general, showing that a graph has or does not have a Hamiltonian
circuit is NP-complete (widely believed to take exponential time)
Does the following graph have a Hamiltonian circuit?
a
c
b
e
d


As you presumably know, a matrix is a
rectangular array of elements
An m x n matrix has m rows and n columns
𝑎11
𝑎21
⋮
𝐴= 𝑎
𝑖1
⋮
𝑎𝑚1
𝑎12 ⋯
𝑎22 ⋯
⋮
𝑎𝑖2 ⋯
⋮
𝑎𝑚2 ⋯
𝑎1𝑗
𝑎2𝑗
⋮
𝑎𝑖𝑗
⋮
𝑎𝑚𝑗
⋯
⋯
𝑎1𝑛
𝑎2𝑛
⋮
⋯ 𝑎𝑖𝑛
⋯
⋮
⋯ 𝑎𝑚𝑛
There are many, many different ways to
represent a graph
 If you get tired of drawing pictures or listing
ordered pairs, a matrix is not a bad way
 To represent a graph as an adjacency matrix,
make an n x n matrix, where n is the number of
vertices
 Let the nonnegative integer at aij give the
number of edges from vertex i to vertex j
 A simple graph will always have either 1 or 0 for
every location


What is the adjacency matrix for the following graph?
v1
v2
v3

What about for this one?
v3
v1
v2

Draw a graph corresponding to this matrix
0
1
A 
0

2
1
1
0
1
1
0
1
0
0

2

1

0




What's the adjacency matrix of this graph?
v1
v2
v4
v3
Note that the matrix is symmetric
In a symmetric matrix, aij = aji for all 1 ≤ i ≤ n and
1≤j≤n
All undirected graphs have a symmetric matrix
representation
To multiply matrices A and B, it must be the case
that A is an m x k matrix and that B is a k x n
matrix
 Then, the ith row, jth column of the result is the
dot product of the ith row of A with the jth
column of B
 In other words, we could compute element cij in
the result matrix C as follows:

k
a
x 1
ix
 bxj

Multiply matrices A and B
 2 0 3
A 


1
1
0


3
4


B 2
2
 2  1 

Matrix multiplication is associative
 That is, A(BC) = (AB)C

Matrix multiplication is not commutative
 AB is not always equal to BA (for one thing, BA might not
even be legal if AB is)

There is an n x n identity matrix I such that, for any m
x n matrix A, AI = A
 I is all zeroes, except for the diagonal (where row =
column) which is all ones

We can raise square matrices to powers using the
following recursive definition
 A0 = I, where I is the n x n identity matrix
 Ak = AAk-1, for all integers k ≥ 1
1 2
A 

2 0





Is A symmetric?
Compute A0
Compute A1
Compute A2
Compute A3




We can find the number of walks of length k that
connect two vertices in a graph by raising the
adjacency matrix of the graph to the kth power
Raising a matrix to the zeroth power means you
can only get from a vertex to itself (identity
matrix)
Raising a matrix to the first power means that
the number of paths of length one from one
vertex to another is exactly the number of edges
between them
The result holds for all k, but we aren't going to
prove it
A property is called an isomorphism invariant if its truth or
falsehood does not change when considering a different (but
isomorphic) graph
 10 common isomorphism invariants:

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Has n vertices
Has m edges
Has a vertex of degree k
Has m vertices of degree k
Has a circuit of length k
Has a simple circuit of length k
Has m simple circuits of length k
Is connected
Has an Euler circuit
Has a Hamiltonian circuit


If any of the invariants have different values
for two different graphs, those graphs are not
isomorphic
Use the 10 invariants given to show that the
following pair of graphs is not isomorphic


Spanning trees
Graphing functions



Keep reading Chapter 10
Start Chapter 11
Finish Assignment 8
 Due Friday

Internship opportunity:
 CLAIR Global in Lititz, PA
 Enterprise Resource Planning software developer
 Looking for candidates with MS Visual Studio and
MS SQL Server Management Studio