Summary notes

32 Pages
Unlock Document

University of Toronto St. George
N/ A

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 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 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
More Less

Related notes for MAT344H1

Log In


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


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.