Study Guides (258,891)
CA (125,041)
UTSG (8,541)
MAT (562)
MAT344H1 (1)
N/ A (1)

Summary notes

32 Pages
215 Views

Department
Mathematics
Course Code
MAT344H1
Professor
N/ A

This preview shows pages 1-3. Sign up to view the full 32 pages of the document.
MAT344H1.doc
Page 1 of 32
Graphs and Subgraphs
Definition: Graph
A graph G is a triple
(
)
(
)
(
)
G
GEGV
ψ
,, where
1)
(
)
GV is a finite set. The elements of
(
)
GV are called the vertices of G.
2)
(
)
GE is a finite set. The elements of
(
)
GE are called the edges.
3) G
ψ
is a function which associates to every edge of an unordered pair of not necessarily distinct vertices. G
ψ
is called the incidence function.
Example
Let
(
)
{
}
4321 ,,, vvvvGV=.
Let
(
)
{
}
87654321 ,,,,,,, eeeeeeeeGE=.
Let
(
)
111 vve
G=
ψ
,
(
)
232 vve
G=
ψ
,
(
)
223 vve
G=
ψ
,
(
)
314 vve
G=
ψ
,
(
)
325 vve
G=
ψ
,
(
)
146 vve
G=
ψ
,
(
)
427 vve
G=
ψ
,
(
)
438 vve
G=
ψ
.
The graph looks like:
Could have drawn it like this:
Definition: Planar
If a graph G can be drawn such that edges only intersect at their ends, then G is called planar.
Example
Consider
3,3
k. Prove that its not planar.
v1
v4
v2 v3
e1 e2
e3 e4 e5
e6 e7
e8
v5
v6
3,3
k
e9
v1
v4
v2
v3
v1
v4
v2 e1
e2
e3
e4
e5
e6
e7
e8
www.notesolution.com
MAT344H1.doc
Page 2 of 32
Cycle-Chord technique. Observe that
3,3
k contains a cycle which covers every vertex:
1258396624411
vevevevevevev .
There is nowhere to place
9
e!
Vocabulary
1) If
(
)
uve =
ψ
, then u and v are the ends of e.
2) e is said to join u and v.
3) u and v are said to be incident to the edge.
4) u and v are said to be adjacent.
5) If
v
u
=
, then e is said to be a loop.
6) If
v
u
, then e is said to be a link.
Definition: Simple
A graph is said to be simple if it has no loops and no two edges join the same pair of vertices.
VERTEX DEGREES
Definition: Vertex Degrees
The degree of a vertex v of a graph G, denoted
(
)
vdG, is defined to be the number of edges that end at the
vertex (loops count twice).
Example
Fact
(
)
( )
=
GVv
Gvd
ε
2, where
ε
is the number of edges.
Proof:
To begin, cut each edge into two pieces. Count the resulting half-edges in two different ways.
3
3
3 5
v1
v4
v2
v3
e1
e2
e3
e4
e5
e6
e7
e8
v5
v6
www.notesolution.com
MAT344H1.doc
Page 3 of 32
Count 1: Label every half edge by the vertex it ends at. The number of edges labeled with some vertex v is
clearly
(
)
vdG. So the number of half-edges is
(
)
( )
GVv
Gvd.
Count 2: There are clearly twice as many half-edges as edges.
Fact
In a graph, the number of vertices with odd degree is even.
Proof:
Let
(
)
(
)
GVGVeven be the set of vertices of G with even degrees. Similarly define
(
)
(
)
GVGVodd .
(
)
( )
(
)
( )
(
)
( )
+==
oddeven
2
GVv
G
GVv
G
GVv
Gvdvdvd
ε
, so
(
)
( )
oddGVv
Gvd must be even, so the number of vertices
with odd degree must be even.
Problem
1) In a group of 8 persons, is it possible that everyone knows exactly 3 others? Yes.
2) In a group of 7 persons, is it possible that everyone knows exactly 3 others? No.
APPLICATION: THE MOUNTAIN CLIMBERS PUZZLE
Consider 2 mountaineers approaching a mountain range from opposite sides. Is it possible for the climbers to
always be at the same height and reach the summit?
Theorem
Two mountaineers can indeed clime in the required fashion to the summit of any mountain range.
Proof:
Construct a graph (the ascent graph) with vertices corresponding to configurations of the climbers where:
1) The two climbers are at the same height.
2) There is one climber on each side of the summit.
3) At least one of the climbers is at a local maxima or minima.
Join the vertices by an edge when the climbers can move between the corresponding configurations by strictly
ascending or strictly descending together.
We must show that no matter for what mountain range, the corresponding ascent graph G has a path from the
initial configuration
(
)
ZA, to the summit
(
)
MM ,.
Well assume no such path exists and produce a contradiction. The proof follows from two observations on G.
Observation 1: G has exactly 2 vertices of degree 1 (namely, the initial configuration and the summit), and the
rest are either degree 2 or 4 (2 when one is on a local max/min, 4 when both are on local max/min at the same
height).
Observation 2: Let
( )
(
)
GVV
ZA
, denote the set of vertices that can be reached by a path from
(
)
ZA,. Note
that the summit
(
)
( )
ZA
VMM ,
,. It is easy to see that there are no edges in G with one end in
( )
ZA
V, and one
end in
(
)
( )
ZA
VGV,
\.
www.notesolution.com

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

Leah — University of Toronto

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto
Saarim — University of Michigan

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan
Jenna — University of Wisconsin

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin
Anne — University of California

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
Description
MAT344H1.doc Graphs and Subgraphs Definition: Graph A graph G is a tripleV(G ), (G , G )where 1) V G ) is a finite set. The elements o(GV)are called the vertices of G. 2) E G ) is a finite set. The elements o(GE)are called the edges. 3) is a function which associates to every edge of an unordered pair of not necessarily distinct vertices. G G is called the incidence function. Example The graph looks like: Let V(G )= {v1,v2,v3,v4 }. Let E G )= {e ,e ,e ,e ,e ,e ,e ,e } . e3 1 2 3 4 5 6 7 8 Let G(e1)= v1 1, G(e2)= v3 2, v2 e2 e1 G(e3 )= v2 2, G(e4 )= v1 3, e5 (e )= v v , (e )= v v , G 5 2 3 G 6 4 1 e G(e7 )= v2 4, G(e8) = v3 4. 4 e v e 7 1 8 e v 6 4 Could have drawn it like this: v 4 v2 v1 v3 Definition: Planar If a graph G can be drawn such that edges only intersect at their ends, then G is called planar. Example Consider k . Prove that its not planar. 3,3 v1 v2 v3 e3 e4 e6 e7 e5 e1 e2 e8 e9 k 3,3 v6 v5 v4 Page 1 of 32 www.notesolution.com MAT344H1.doc Cycle-Chord technique. Observe that k3,3contains a cycle which covers every vertex: v1 1 4 4 2 6 6 9 3 8 5 2 1. v1 v5 e2 e5 e1 e8 v4 e3 v3 e4 e7 v e v 2 6 6 There is nowhere to placee9! Vocabulary 1) If (e)= uv , then u and v are the ends of e. 2) e is said to join u and v. 3) u and v are said to be incident to the edge. 4) u and v are said to be adjacent. 5) If u = v , then e is said to be a loop. 6) If u v, then e is said to be a link. Definition: Simple A graph is said to be simple if it has no loops and no two edges join the same pair of vertices. V ERTEX D EGREES Definition: Vertex Degrees The degree of a vertex v of a graph G, denotedG v), is defined to be the number of edges that end at the vertex (loops count twice). Example 3 3 5 3 Fact dG v) = 2 , where is the number of edges. vV(G ) Proof: To begin, cut each edge into two pieces. Count the resulting half-edges in two different ways. Page 2 of 32 www.notesolution.com MAT344H1.doc Count 1: Label every half edge by the vertex it ends at. The number of edges labeled with some vertex v is clearly dG(v). So the number of half-edges s dG v). v(G ) Count 2: There are clearly twice as many half-edges as edges. Fact In a graph, the number of vertices with odd degree is even. Proof: Let V G )even V(G )be the set of vertices of G with even degrees. Similarly Ge)odd V G ). 2 = d G(v)= dG(v)+ dG v ), so dG v) must be even, so the number of vertices vVG ) vVG ven v(G dd v(G dd with odd degree must be even. Problem 1) In a group of 8 persons, is it possible that everyone knows exactly 3 others? Yes. 2) In a group of 7 persons, is it possible that everyone knows exactly 3 others? No. A PPLICATION : T HE M OUNTAIN C LIMBERS P UZZLE Consider 2 mountaineers approaching a mountain range from opposite sides. Is it possible for the climbers to always be at the same height and reach the summit? Theorem Two mountaineers can indeed clime in the required fashion to the summit of any mountain range. Proof: Construct a graph (the ascent graph) with vertices corresponding to configurations of the climbers where: 1) The two climbers are at the same height. 2) There is one climber on each side of the summit. 3) At least one of the climbers is at a local maxima or minima. Join the vertices by an edge when the climbers can move between the corresponding configurations by strictly ascending or strictly descending together. We must show that no matter for what mountain range, the corresponding ascent graph G has a path from the initial configuratiA, Z) to the summitM,M ). Well assume no such path exists and produce a contradiction. The proof follows from two observations on G. Observation 1: G has exactly 2 vertices of degree 1 (namely, the initial configuration and the summit), and the rest are either degree 2 or 4 (2 when one is on a local maxmin, 4 when both are on local maxmin at the same height). Observation 2: Let A,Z )V (G )denote the set of vertices that can be reached by a paA, Z). Note that the summitM,M )V A,Z ) It is easy to see that there are no edges in G with o(A,Zn)nd one end in V(G)V . A,Z ) Page 3 of 32 www.notesolution.com
More Less
Unlock Document


Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit