logging in or signing up m239w07lecture14 Haggrid Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 154 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: October 19, 2007 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Slide1: Introduction to Combinatorics Lecture 14 http://www.iqc.ca/~mmosca/web/teaching/math239 Michele MoscaSome reverse-engineering Problem 3.1.4: Some reverse-engineering Problem 3.1.4Some reverse-engineering modified Problem 3.1.4: Some reverse-engineering modified Problem 3.1.4 Let Theorem 3.1.1: Theorem 3.1.1Solutions to homogeneous equations: Solutions to homogeneous equationsNon-homogeneous equations: Non-homogeneous equations Suppose satisfies the recurrence relation . Non-homogeneous equations, e.g.: Non-homogeneous equations, e.g. Consider satisfying the recurrence relation Let’s first try to find some sequence that satisfies this recurrence relation.Non-homogeneous equations, e.g.: Non-homogeneous equations, e.g. So satisfies the non-homogeneous recurrence, but NOT the initial conditions. Suppose the initial conditions areHomogenous version of this equation: Homogenous version of this equationLinear Algebra Flashback: Linear Algebra Flashback Theorem 3.2.1: Theorem 3.2.1 is a solution to the non-homogeneous equation for all , but doesn’t necessarily satisfy the same initial conditions.Theorem 3.2.1: Theorem 3.2.1 Then for any sequence , the sequence also satisfies the non-homogeneous equation for (but not necessarily for ) Problem 3.2.2: Problem 3.2.2Problem 3.2.2: Problem 3.2.2Problem 3.2.2: Problem 3.2.2Problem 3.2.2: Problem 3.2.2Graph Theory: Graph Theory A graph G=(V,E) consists of a set of objects V, called the “vertices” and a set E of “edges” which are unordered pairs of distinct vertices. We can denote the vertex set of a graph G by V(G), and the edge set E(G).Graph Theory: Graph Theory We can represent a graph G=(V,E) with a drawing:Graph Theory: Graph Theory we say “3 is joined to 4” we say “3 and 4 are adjacent” we say “e4 joins 3 and 4” we say “3 is incident with e4” we say “4 is incident with e4” we say “3 and 4 are neighbours”Graph Theory: Graph Theory We can draw a graph G in any way that illustrates the adjacency information“Planar” graphs: “Planar” graphs We call a graph planar if it can be drawn in the 2-dimensional plane without any edges crossing over. e.g. this graph G is planar.“Planar” graphs: “Planar” graphs We call a graph planar if it can be represented in the 2-dimensional plane without any edges crossing over. e.g. this graph G is planar. … because G CAN be drawn with no crossovers!e.g. a word graph: e.g. a word graph Let Join word1 and word2 if and only if the two words differ in exactly 1 letterConverting a political map to a graph: Converting a political map to a graph e.g. we can represent the adjacencies between Switzerland, Germany, Austria and Italy by a graphConverting a political map to a graph: Converting a political map to a graph e.g. we can represent the adjacencies between Switzerland, Germany, Austria and Italy by a graph Switzerland Austria Germany ItalyGraphs of subsets: Graphs of subsets For any non-negative integers k and n, define the graph Sn,k so that V(Sn,k) is the set of k-subsets of {1,2,3,…,n} and two k-subsets are adjacent if and only if they have exactly k-1 elements in common.“Complete” graphs: “Complete” graphs A complete graph is one in which all pairs of vertices are adjacent. e.g. S4,3 is a complete graphIsomorphic graphs: Isomorphic graphs We can think of a graph as consisting of two parts: 1) an adjacency structure and 2) a labellingIsomorphic graphs: Isomorphic graphs If two graphs are the same apart from the labelling, we say they are isomorphicIsomorphic graphs: Isomorphic graphs G and H are isomorphic (i.e. the drawings might look different, but they are still isomorphic) Isomorphic graphs: Isomorphic graphs “Complete” graphs: “Complete” graphs “Degree” of a vertex: “Degree” of a vertex The degree of a vertex v, denoted deg(v), is the number of edges incident with v. e.g. You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
m239w07lecture14 Haggrid Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 154 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: October 19, 2007 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Slide1: Introduction to Combinatorics Lecture 14 http://www.iqc.ca/~mmosca/web/teaching/math239 Michele MoscaSome reverse-engineering Problem 3.1.4: Some reverse-engineering Problem 3.1.4Some reverse-engineering modified Problem 3.1.4: Some reverse-engineering modified Problem 3.1.4 Let Theorem 3.1.1: Theorem 3.1.1Solutions to homogeneous equations: Solutions to homogeneous equationsNon-homogeneous equations: Non-homogeneous equations Suppose satisfies the recurrence relation . Non-homogeneous equations, e.g.: Non-homogeneous equations, e.g. Consider satisfying the recurrence relation Let’s first try to find some sequence that satisfies this recurrence relation.Non-homogeneous equations, e.g.: Non-homogeneous equations, e.g. So satisfies the non-homogeneous recurrence, but NOT the initial conditions. Suppose the initial conditions areHomogenous version of this equation: Homogenous version of this equationLinear Algebra Flashback: Linear Algebra Flashback Theorem 3.2.1: Theorem 3.2.1 is a solution to the non-homogeneous equation for all , but doesn’t necessarily satisfy the same initial conditions.Theorem 3.2.1: Theorem 3.2.1 Then for any sequence , the sequence also satisfies the non-homogeneous equation for (but not necessarily for ) Problem 3.2.2: Problem 3.2.2Problem 3.2.2: Problem 3.2.2Problem 3.2.2: Problem 3.2.2Problem 3.2.2: Problem 3.2.2Graph Theory: Graph Theory A graph G=(V,E) consists of a set of objects V, called the “vertices” and a set E of “edges” which are unordered pairs of distinct vertices. We can denote the vertex set of a graph G by V(G), and the edge set E(G).Graph Theory: Graph Theory We can represent a graph G=(V,E) with a drawing:Graph Theory: Graph Theory we say “3 is joined to 4” we say “3 and 4 are adjacent” we say “e4 joins 3 and 4” we say “3 is incident with e4” we say “4 is incident with e4” we say “3 and 4 are neighbours”Graph Theory: Graph Theory We can draw a graph G in any way that illustrates the adjacency information“Planar” graphs: “Planar” graphs We call a graph planar if it can be drawn in the 2-dimensional plane without any edges crossing over. e.g. this graph G is planar.“Planar” graphs: “Planar” graphs We call a graph planar if it can be represented in the 2-dimensional plane without any edges crossing over. e.g. this graph G is planar. … because G CAN be drawn with no crossovers!e.g. a word graph: e.g. a word graph Let Join word1 and word2 if and only if the two words differ in exactly 1 letterConverting a political map to a graph: Converting a political map to a graph e.g. we can represent the adjacencies between Switzerland, Germany, Austria and Italy by a graphConverting a political map to a graph: Converting a political map to a graph e.g. we can represent the adjacencies between Switzerland, Germany, Austria and Italy by a graph Switzerland Austria Germany ItalyGraphs of subsets: Graphs of subsets For any non-negative integers k and n, define the graph Sn,k so that V(Sn,k) is the set of k-subsets of {1,2,3,…,n} and two k-subsets are adjacent if and only if they have exactly k-1 elements in common.“Complete” graphs: “Complete” graphs A complete graph is one in which all pairs of vertices are adjacent. e.g. S4,3 is a complete graphIsomorphic graphs: Isomorphic graphs We can think of a graph as consisting of two parts: 1) an adjacency structure and 2) a labellingIsomorphic graphs: Isomorphic graphs If two graphs are the same apart from the labelling, we say they are isomorphicIsomorphic graphs: Isomorphic graphs G and H are isomorphic (i.e. the drawings might look different, but they are still isomorphic) Isomorphic graphs: Isomorphic graphs “Complete” graphs: “Complete” graphs “Degree” of a vertex: “Degree” of a vertex The degree of a vertex v, denoted deg(v), is the number of edges incident with v. e.g.