Applied Linear Algebra

Calculus and Computational Methods I

Calculus and Computational Methods II

Calculus and Geometry

Discrete Mathematics I

Discrete Mathematics II

Dynamic Systems Differential Equations

Graph Theory

Linear Algebra

Modern Mathematics I

Modern Mathematics II

Numerical Analysis I

Probability and Statistics I

Probability and Statistics II

MTH | 430 | Dynamic Systems Differential Equations | study guides | 

MTH607 (Graph Theory) — Course Notes Lecture 2 — January 25, 2016 Deﬁnition 2.1. A subgraph , H , of a graph G , written H ⊆ G , is a graph such that V ( H ) ⊆ V ( G ) and E ( H ) ⊆ E ( G ) (clearly, the endpoints of the edges in H must be in V ( H ) ). Example 2.2. In the following picture, H 1 and H 2 are subgraphs of G . a b c d e f b c d e a b c d e f G H 1 H 2 Deﬁnition 2.3. A graph G is called a path if its vertices can be ordered so that edges only go between consecutive vertices in the ordering. A graph G is called a cycle if its vertices can be placed on a circle so that edges only go between vertices adjacent on the circle. Example 2.4. Below, the ﬁrst row of graphs shows cycles and the second row shows paths. Notice that some researchers index paths by the number of edges in the path, not the number of vertices. In this course, however, we index them by the number of vertices. For cycles, the number of edges and the number of vertices are the same. C 3 C 4 C 5 C 6 P 6 P 4 P 5 P 3 Consider the following two graphs: a b c d 1 2 3 4 G H 1 2 The vertices are labelled diﬀerently and they “look” diﬀerent, but in some sense they are the same. They are both the “same” as P 3 . To make this formal we introduce isomorphisms of graphs. Deﬁnition 2.5. An isomorphism from a graph G to a graph H is a bijection f : V ( G ) → V ( H ) such that { u, v }∈ E ( G ) if and only if { f ( u ) ,f ( v ) }∈ E ( H ) . If there exists an isomor- phism from G to H , then we say that G and H are isomorphic and we write G ∼ = H . Looking at G and H above, we can deﬁne the bijection f : V ( G ) → V ( H ) by f ( a )=1 f ( b )=3 f ( c )=4 f ( d )=2 and see that the edges and non-edges of G are preserved by the mapping. For example { a, b } 7→ { f ( a ) ,f ( b ) } = { 1 , 3 } . In order for a bijection f to be an isomorphism from G to H , vertex f ( v ) must behave in H as v does in G (for example, they must have the same degree). Deﬁnition 2.6. An invariant is a graph property which must be the same in graphs that are isomorphic. Examples of invariants: number of vertices, number of edges, degree sequence (list of degrees of the vertices), number of cycles of given length, subgraphs, bipartite-ness. Example 2.7. Which pairs, if any, of the following 4 graphs are isomorphic? An equivalence relation is a relation which is reﬂexive, symmetric, and transitive. Theorem 2.8. Being isomorphic is an equivalence relation on any set of graphs. Proof. Reﬂexive property ( G ∼ = G ). Every graph is isomorphic to itself since the identity function ( f ( v )= v for all v ∈ V ( G )) is an isomorphism. Symmetric property ( G ∼ = H ⇒ H ∼ = G ). Let f : V ( G ) → V ( H ) be an isomorphism from G to H . Then the inverse function f - 1 : V ( H ) → V ( G ) is an isomorphism from H to G . Transitive property ( F ∼ = G and G ∼ = H ⇒ F ∼ = H ). Let f : V ( F ) → V ( G ) be an isomorphism from F to G and g : V ( G ) → V ( H ) be an isomorphism from G to H . Then the composition ( f ◦ g )( v )= f ( g ( v )) of f and g is an isomorphism from F to H .  Any equivalence relation on a set partitions the set into equivalence classes : two elements are in the same equivalence class if and only if they satisfy the equivalence relation. So graph isomorphism can partition any set of graphs into isomorphism classes . Notation. For an integer n , we use [ n ] to represent { 1 , 2 ,...,n } . Fact 2.9. The number of (labelled) graphs with vertex set [ n ] is 2 ( n 2 )

MTH | 607 | Graph Theory | lecture notes | MTH607 (Graph Theory) — Course

Probability and Statistics Dr. Changping Wang Chapter 8 Large-Sample Estimation 8.3 Types of Estimators 1) Point estimation Based on sample data, a single number is calculated to estimate the population parameter. e.g., sample mean for ; sample variance for . 2) Interval estimation Based on sample data, two numbers are calculated to form an interval in which the population parameter is expected to lie. Chapter 8 Page 1 Probability and Statistics Dr. Changping Wang 8.4 Point Estimation An estimator of a parameter is said to be unbiased if the mean of its distribution is equal to the true value of the parameter. Otherwise, the estimator is said to be biased . The distance between an estimate and the estimate parameter is called the error of estimation . Note 1: To estimate the population mean, we can use the sample mean as an estimator. Then would be the error of estimator. Note 2: To estimate the population proportion, we can use the sample proportion as an estimator. Then would be the error of estimator. Chapter 8 Page 2 Probability and Statistics Dr. Changping Wang The 95% margin of error is defined to be 1.96 times the standard deviation (or standard error (SE)). Note 3: To estimate the population mean, we can use the sample mean as an estimator. Then the 95% margin of error would be when the sample size n is 30 or larger. Note 4: To estimate the population proportion, we can use the sample proportion as an estimator. Then the 95% margin of error would be when both Chapter 8 Page 3 Probability and Statistics Dr. Changping Wang Example 1 . Calculate the 95% margin of error in estimating the population mean when the sample gives Example 2 . Calculate the 95% margin of error in estimating the population proportion when the sample gives Chapter 8 Page 4 Probability and Statistics Dr. Changping Wang 8.5 Interval Estimation The confidence coefficient (level of confidence) is the probability that a confidence interval will contain the true estimated parameter. Usually written by . Some common confidence coefficients used are : 0.90, 0.95, 0.98, 0.99. denotes the z-score with an area in the upper (right) tail of a standard normal distribution. Chapter 8 Page 5 Probability and Statistics Dr. Changping Wang (a) Large-Sample Confidence Interval for the Mean Steps for constructing a confidence interval : 1. Find the sample mean 2. Specify , if known; or replace it by the sample standard deviation s if unknown. 3. Find the z-score that corresponds to the given level of confidence . 4. Find the margin of error 5. Find the lower and upper confidence limits and form the confidence interval ( , ). Chapter 8 Page 6

MTH | 304 | Probability and Statistics I | lecture notes | Probability and Statistics Dr.

MTH 607 – Graph Theory Assignment 1b (Solutions) Due Monday, January 26, 2015 (3pm) For full marks, your answers should be clear, precise and carefully argued. Just having “the right idea” will only give you a passing mark. (1) Question: Suppose that a graph of order n is isomorphic to its complement. Find a formula of the number of edges and show that n =4 k or n =4 k + 1 for some integer k . (The order of a graph is the number of vertices.) Solution: Since the number of edges is an invariant property, we have | E ( G ) | = | E ( ¯ G ) | = ( n 2 ) 2 = n ( n - 1) 4 . Obviously the number of edges is an integer, so the number of vertices must be of the form n =4 k or n =4 k + 1 for some integer k . (2) Question: Determine whether the graph below is isomorphic to the Petersen graph. r r r r r r r r r r     ❅ ❅ ❍ ❍ ❍ ❍ ✟ ✟ ✟ ✟   ❅ ❅ ❅ ❅✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ✏ ✏ ✏ ✏ ✏✏P P P P PP Solution: The graph is isomorphic to the Petersen graph. The following mapping is an example of homomorphism. s s s s s s s s s s     ❅ ❅ ❍ ❍ ❍ ❍ ✟ ✟ ✟ ✟   ❅ ❅ ❅ ❅✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ✏ ✏ ✏ ✏ ✏ ✏P P P P P P 13 24 35 12 34 15 23 14 25 45 (3) Question: Prove that the complement of a disconnected graph must be connected. Solution: Let G be a disconnected graph. In order to prove the statement we have to show that there is a walk in ¯ G between any pair of vertices. Let x, y ∈ V ( ¯ G )= V ( G ) ,x 6 = y . 1 2 Case 1. x and y are in two diﬀerent components of G . So { x, y } / ∈ E ( G ), but it means that there is an edge { x, y } in ¯ G . Case 2. x and y are in the same component of G . Since G is disconnected there is a vertex z in another component of G (in particular, { z,x } / ∈ E ( G ), { z,y } / ∈ E ( G )). So { z,x }∈ ¯ G and { z,y }∈ ¯ G , and there is a path ( x,z,y ) from x to y . (4) Question: G =( V,E ) is a connected graph. P 1 and P 2 are both paths of maximum length in G . Prove that P 1 and P 2 have at least one common vertex. Is this result sharp? That is, maybe these paths have at least two common vertices? Solution: Let P 1 =( a 0 ,a 1 ,...,a n ) and P 2 =( b 0 ,b 1 ,...,b n ) be two longest paths in G . For a contradiction, suppose that { a 0 ,a 1 ,...,a n } and { b 0 ,b 1 ,...,b n } are disjoint. Since G is connected, there is a path connecting some vertex of A to a vertex of B ; let P =( v 0 ,v 1 ,...,v k ) be a shortest such path. Therefore v 0 = a i for some i , v k = b j for some j , and { v 1 ,v 2 ,...,v k - 1 } is disjoint from both { a 0 ,a 1 ,...,a n } and { b 0 ,b 1 ,...,b n } . By possibly reversing the direction of A , we may assume that i ≥ n/ 2. Similarly we may assume that j ≥ n/ 2. Now consider the path Q =( a 0 ,a 1 ,...,a i = v 0 ,v 1 ,...,v k - 1 ,v k = b j ,b j - 1 ,...,b 0 ). The length of Q is ( i + j )+ k ≥ n + k ≥ n + 1, whereas A has length n . This contradicts the fact that A is a longest path. This contradiction shows that A and B share a common vertex. This result is sharp. You can take, for example, a star with 4 edges. Each path of maximum length has length 2, and no two paths share more than one vertex. (5) Question: Let G =( V,E ) be a graph with V = { 1 , 2 ,..., 100 } where vertices i and j are adjacent if and only if | i - j |∈{ 4 , 10 , 12 } . • Is there a path from 1 to 7 in G ? • Is there a path from 1 to 100 in G ? Solution: There is a path (1 , 11 , 7) from 1 to 7 in G . Let A = { 1 , 3 , 5 ,..., 99 } and B = { 2 , 4 , 6 ,..., 100 } . Note that 1 ∈ A , 100 ∈ B , and there is no edge connecting A to B . Therefore there is no path from 1 to 100 in G . (6) Question: Let G =( V,E ) be a graph with exactly two vertices of odd degree, say u and v . Prove that there is a path from u to v in G . (Hint: try to use Corollary 1.16 from the notes.) Solution: For a contradiction, suppose that there is no path from u to v in G . Then u and v are in diﬀerent components; Let H be the component of G that contains u . Now, u is the only vertex in H with odd degree. However, this contradicts Corollary 1.16 which says that H has an even number of vertices of odd degree. Therefore there is a path from u to v .

MTH | 607 | Graph Theory | homework | MTH 607 – Graph Theory Assignm

Quiz 2 Solution Suppose a reading comprehension test is given to random samples of three Grade 7 students from each of five different schools. The samples are chosen so that each school provides a student categorized as low IQ, average IQ, and high IQ. Perform an analysis using the data below, treating the IQs as blocks. Is there sufficient evidence to reject

MTH404_20170207_Q2Soln_Prof.pdf-Quiz 2 Solution Suppose a reading

All courses in MTH

Popular Documents