Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Graph Theory, Discrete Mathematics
Description: These notes contain the information about the graphs generally taught in the computer science, usually in discrete structures and data structure courses.
Description: These notes contain the information about the graphs generally taught in the computer science, usually in discrete structures and data structure courses.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
12/4/2016
Graph Theory and
Applications
Branch of mathematics concerned
with networks of points connected by
lines
In 1735 the Swiss mathematician
Leonhard Euler presented a
solution to this problem, concluding
that such a walk was impossible
...
The number of ksubsets on n
elements is therefore
given by the binomial
coefficient
...
8
12/4/2016
9
12/4/2016
10
12/4/2016
11
12/4/2016
12
12/4/2016
13
12/4/2016
14
12/4/2016
15
12/4/2016
16
12/4/2016
17
12/4/2016
18
12/4/2016
19
12/4/2016
20
12/4/2016
21
12/4/2016
22
12/4/2016
23
12/4/2016
24
12/4/2016
25
12/4/2016
26
12/4/2016
27
12/4/2016
28
12/4/2016
29
12/4/2016
Suppose, u and w are the only
neighbors of v
...
A minor is a graph that can be
constructed by the original
graph by deleting vertices,
deleting edges or merging
vertices as shown
...
30
12/4/2016
31
12/4/2016
32
12/4/2016
Isomorphism
• The word isomorphism comes from the Greek roots isos for “equal”
and morphe for “form
...
33
12/4/2016
34
12/4/2016
35
12/4/2016
36
12/4/2016
Graph Colouring
37
12/4/2016
Graph Colouring
Graph Colouring Problem:
Given a graph, colour all the vertices so that
two adjacent vertices get different colours
...
3-colourable
Optimal Colouring
Definition
...
”
if (unique) path from root is
even length:
odd length:
Can prove more formally using induction (classwork)
...
how many gates needed?
time
122
145
Flights
67
257
306
99
41
12/4/2016
Conflict Graph
Needs gate at same time
145
• Each vertex represents a flight
306
• Each edge represents a conflict
99
Graph Colouring
257
122
145
306
67
9
There is a k-colouring in this graph iff the flights can be scheduled using k
gates
...
<= If there is a graph colouring, then the vertices using each colour
have no conflict, and so we can schedule the flights having the same
colour in one gate
...
how short an exam period?
This is a graph colouring problem
...
The graph has a k-colouring if and only if
the exams can be scheduled in k days
...
minimum number of
44
12/4/2016
Register Allocation
• Given a program, we want to execute it as quick as possible
...
• But registers are very expensive, and there are only a few in a computer
...
This is a graph colouring problem
...
• Two variables have a conflict if they cannot be put into the same register
...
c and d cannot use the same register otherwise the value of c is overwritten
...
45
12/4/2016
Map Colouring
Colour the map using minimum number of colours so that
two countries sharing a border are assigned different colours
...
All of (e, b), (b, a), (a, b), (b, a), (a, b), and (b, e) are edges, so
e, b, a, b, a, b, e is a path of length six
...
50
12/4/2016
51
12/4/2016
52
12/4/2016
53
12/4/2016
Weighted Graphs
Graphs that have a number assigned to
each edge are called weighted graphs
...
Euler’s Theorem
56
12/4/2016
Example: Euler Paths
Example: Euler Circuits
Euler’s Theorem
57
12/4/2016
Euler’s Theorem
Graph
Number of odd
Number of even
vertices (vertices
vertices (vertices
connected to an odd connected to an even
number of edges)
number of edges)
What does the path
contain?
(Euler path = P;
Euler circuit = C;
Neither = N)
1
0
10
C
2
0
6
C
3
2
6
P
4
2
4
P
5
4
1
N
6
8
0
• From the table, we can
observe that:
• A graph with all vertices
being even contains an
Euler circuit
...
• A graph with more than 2
odd vertices does not
contain any Euler path or
circuit
...
The resulting mathematical structure is called a graph
...
It does not
matter whether the links are straight or curved, or whether one node is to the
left of another
...
The degree of a node is the number of edges touching it; in the
Königsberg bridge graph, three nodes have degree 3 and one has degree 5
...
Such a walk is called an Eulerian circuit or an
Euler tour
...
"
12/4/2016
119
Seven Bridges of Königsberg
"The problem can be modified to ask for a path that
traverses all bridges but does not have the same starting
and ending point
...
Such a path exists if and only if the graph has exactly two
nodes of odd degree, those nodes being the starting and
ending points
...
)"
12/4/2016
120
60
12/4/2016
61
12/4/2016
62
12/4/2016
A problem p in NP is NPcomplete if every other
problem in NP can be
transformed (or
reduced) into p in
polynomial time
...
• Each node is given a temporary label denoting the length of the
shortest path from the start node so far
...
• Once it is certain that no other shorter paths can be found, the
temporary label becomes a permanent label
...
• At this point the shortest path is found by retracing the path
backwards
...
• Step 2: Consider the node with the most recently boxed label
...
Then,
in turn, consider each node directly joined to X but not yet
permanently boxed
...
• Step 3: Choose the least of all temporary labels on the network
...
• Step 4: Repeat Steps 2 and 3 until the destination node has a
permanent label
...
65
12/4/2016
Dijkstra’s Algorithm
• Dijkstra’s algorithm is used in problems relating to finding the
shortest path
...
• This label is replaced if another shorter route is found
...
• Eventually all the nodes have permanent labels
...
66
12/4/2016
Dijkstra’s Algorithm
Aim: To find the shortest path connecting two nodes
• Step 1: Label the start node with zero and box this label
...
Suppose this node to be X and let D be its permanent label
...
For each such node, Y say, temporarily label
it with the lesser of D + (the weight of arc XY) and its existing
label (if any)
...
Make this label permanent by boxing it
...
• Step 5: Go backwards through the network, retracing the path
of shortest length from the destination node to the start node
...
7
Planar Graphs
The House-and-Utilities Problem
Is it possible to join the three houses to the
three utilities in such a way that none of the
connections cross?
72
12/4/2016
Planar Graphs
• Phrased another way, this question is equivalent to:
Given the complete bipartite graph K3,3, can K3,3 be
drawn in the plane so that no two of its edges cross?
K3,3
Planar Graphs
• A graph is called planar if it can be drawn
in the plane without any edges crossing
...
• Such a drawing is called a planar
representation of the graph
...
74
12/4/2016
Example
A graph may be planar even if it represents a
3-dimensional object
...
• However, not all graphs are planar
...
• We would have to show that there is no way
to draw the graph without any edges
crossing
...
R4
R3
R2
R1
Faces or Regions
When a planar graph is drawn with no crossing edges,
it divides the plane into a set of regions, called faces
...
76
12/4/2016
Regions
• In any planar representation of K3,3, vertex
v1 must be connected to both v4 and v5, and
v2 also must be connected to both v4 and v5
...
v1
v5
R2
v4
R1
v2
77
12/4/2016
Regions
• Next, we note that v3 must be in either R1 or R2
...
Then the edges {v3, v4} and {v4, v5}
separate R2 into two subregions, R21 and R22
...
Then the
edges {v3, v4} and {v4, v5} separate R1 into
two subregions, R11 and R12
...
K3,3
Regions
• Euler devised a formula for expressing the
relationship between the number of vertices,
edges, and regions of a planar graph
...
80
12/4/2016
Euler’s Formula
• Let G be a connected planar simple graph
with e edges and v vertices
...
Then r = e - v + 2
...
Every simple planar graph has a vertex of degree at most 5
...
)
• Corollary 1: If G is a connected planar
simple graph with e edges and v vertices
where v 3, then e 3v - 6
...
)
• K5 has 5 vertices and 10 edges
...
• So, if K5 is planar, it must be true that e 3v – 6
...
• So e must be 9
...
• So, K5 is nonplanar
...
)
• Corollary 2: If G is a connected planar
simple graph, then G must have a vertex of
degree not exceeding 5
...
)
• Corollary 3: If a connected planar simple
graph has e edges and v vertices with v 3
and no circuits of length 3, then e 2v - 4
...
)
• K3,3 has 6 vertices and 9 edges
...
• If K3,3 were planar, then e 2v – 4 would have to be true
...
• But e = 9
...
K3,3
Regions
The first invariant of a planar graph will be the
number of regions that the graph defines in the
plane
...
EG: the car graph has 4 regions:
4
L25
3
1
2
168
84
12/4/2016
Regions
Q: How many regions does the 3-cube have?
L25
169
Regions
A: 6 regions
6
3
4
1
2
5
L25
170
85
12/4/2016
Regions
THM: The number of regions defined by a connected
planar graph is invariant of how it is drawn in the
plane and satisfies the formula involving edges and
vertices:
r = |E | - |V | + 2
EG: Verify formula for car and 3-cube:
4=
L25
3
6-4+2
3
1
6=
12-8+2
2
4
1
2
5
171
Euler Characteristic
The formula is proved by showing that the quantity (chi) = r - |E | +
|V | must equal 2 for planar graphs
...
The idea is that any connected planar graph can be
built up from a vertex through a sequence of vertex and edge
additions
...
L25
174
87
12/4/2016
Euler
Check that moves don’t change :
Characteristic
1) Adding a degree 1 vertex:
r is unchanged
...
|V | increases by
1
...
|E | increases by 1
...
+= (1-1+0)
EG:
L25
175
Animated Invariance of
Euler Characteristic
|V |
r
=
r - |E | + |V |
1
L25
|E |
0
1
2
176
88
12/4/2016
Animated Invariance of
Euler Characteristic
|V |
|E |
r
=
r - |E | + |V |
2
1
1
2
L25
177
Animated Invariance of
Euler Characteristic
|V |
r
=
r - |E | + |V |
3
L25
|E |
2
1
2
178
89
12/4/2016
Animated Invariance of
Euler Characteristic
|V |
|E |
r
=
r - |E | + |V |
4
3
1
2
L25
179
Animated Invariance of
Euler Characteristic
|V |
r
=
r - |E | + |V |
4
L25
|E |
4
2
2
180
90
12/4/2016
Animated Invariance of
Euler Characteristic
|V |
|E |
r
=
r - |E | + |V |
5
5
2
2
L25
181
Animated Invariance of
Euler Characteristic
|V |
r
=
r - |E | + |V |
6
L25
|E |
6
2
2
182
91
12/4/2016
Animated Invariance of
Euler Characteristic
|V |
|E |
r
=
r - |E | + |V |
7
7
2
2
L25
183
Animated Invariance of
Euler Characteristic
|V |
r
=
r - |E | + |V |
8
L25
|E |
8
2
2
184
92
12/4/2016
Animated Invariance of
Euler Characteristic
|V |
|E |
r
=
r - |E | + |V |
8
9
3
2
L25
185
Animated Invariance of
Euler Characteristic
|V |
r
=
r - |E | + |V |
8
L25
|E |
10
4
2
186
93
12/4/2016
Animated Invariance of
Euler Characteristic
|V |
|E |
r
=
r - |E | + |V |
8
11
5
2
L25
187
Animated Invariance of
Euler Characteristic
|V |
r
=
r - |E | + |V |
8
L25
|E |
12
6
2
188
94
Title: Graph Theory, Discrete Mathematics
Description: These notes contain the information about the graphs generally taught in the computer science, usually in discrete structures and data structure courses.
Description: These notes contain the information about the graphs generally taught in the computer science, usually in discrete structures and data structure courses.