DOC PREVIEW
UMD CMSC 250 - Graphs and Trees

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC 250 Discrete Structures Graphs and Trees Graphs Vertices Edges 24 July 2007 endpoints Graphs and Trees 2 Types of Graphs Directed order counts when discussing edges Undirected bidirectional Weighted each edge has a value associated with it Unweighted 24 July 2007 Graphs and Trees 3 Examples http richard jones name google hacks google cartography google cartography html 24 July 2007 Graphs and Trees 4 Special Graphs Simple does not have any loops or parallel edges Complete graphs there is an edge between every possible tuple of vertices Bipartite graph V can be partitioned into V1 and V2 such that x y E x V1 y V2 x V2 y V1 Sub graphs G1 is a subset of G2 iff Every vertex in G1 is in G2 Every edge in G1 is in G2 Connected graph can get from any vertex to another via edges in the graph 24 July 2007 Graphs and Trees 5 Degree of Vertex Defined as the number of edges attached to the vertex 24 July 2007 Graphs and Trees 6 Handshake Theorem If G is any graph then the sum of the degrees of all the vertices of G equals twice the number of edges of G Specifically if the vertices of G are v1 v2 vn where n is a nonnegative integer then The total degree of G d v1 d v2 d vn 2 the number of edges of G 24 July 2007 Graphs and Trees 7 Prove Sum of all degrees is even Prove that the sum of the degrees of all vertices in a graph is even 24 July 2007 Graphs and Trees 8 Prove Even vertices w odd degree In any graph there are an even number of vertices with odd degree 24 July 2007 Graphs and Trees 9 Seven Bridges of K nigsberg Is it possible for a person to take a walk around town starting and ending at the same location and crossing each of the seven bridges exactly once 24 July 2007 Graphs and Trees o N 10 Definitions Walk from two vertices alternating sequence of adjacent vertices and edges Trivial walk from v to v consists of single vertex Path does not contain a repeated edge Simple path does not contain a repeated vertex Closed walk starts and ends at same vertex Circuit a closed walk without repeated edge Simple circuit no repeated vertex except first and last Connectedness if a walk from one to the other 24 July 2007 Graphs and Trees 11 Euler Circuits A circuit that contains every vertex and every edge of G A sequence of adjacent vertices and edges That starts and ends at the same vertex uses every vertex of G at least once and uses every edge of G exactly once 24 July 2007 Graphs and Trees 12 If a graph has an Euler circuit every vertex has even degree Contrapositive if some vertex has odd degree then the graph does not have an Euler circuit 24 July 2007 Graphs and Trees 13 If every vertex of nonempty graph has even degree and if graph is connected then the graph has an Euler circuit 24 July 2007 Graphs and Trees 14 Euler Circuit Proofs If every vertex of nonempty graph has even degree and if graph is connected then the graph has an Euler circuit A graph G has an Euler circuit if and only if G is connected and every vertex of G has even degree 24 July 2007 Graphs and Trees 15 Hamiltonian Path A path in an undirected graph which visits each vertex exactly once 24 July 2007 Graphs and Trees 16 Hamiltonian Circuit A simple circuit that includes every vertex of G A sequence of adjacent vertices and distinct edges in which every vertex of G appears exactly once except for the first and last which are the same 24 July 2007 Graphs and Trees 17 Hamiltonian Circuit Proved simple criterion for determining whether a graph has an Euler circuit No analogous criterion for determining whether a graph has a Hamiltonian circuit Nor is there an efficient algorithm for finding such an algorithm 24 July 2007 Graphs and Trees 18 Traveling Salesman Problem http en wikipedia org wiki Traveling Sal esman Problem 24 July 2007 Graphs and Trees 19 TSP One way to solve the general problem is to Write down all Hamiltonian circuits Compute total distance for each Pick one for which total is minimal What if graph has 30 vertices 29 8 84 x 1030 different Hamiltonian circuits If each circuit could be found and total distance computed in a nanosecond then would take 2 8 x 1014 years No known algorithm that is more efficient Some that find pretty good solutions 24 July 2007 Graphs and Trees 20 Matrix Representations of Graphs 24 July 2007 Graphs and Trees 21 Matrices and Connected Components 24 July 2007 Graphs and Trees 22 Counting Walks of Length n Matrix 24 July 2007 multiplication Graphs and Trees 23 How do these graphs relate 24 July 2007 Graphs and Trees 24 Are these two graphs similar 24 July 2007 Graphs and Trees 25 Graph Isomorphism 24 July 2007 Let G and G be graphs with vertex sets V G and V G and edge sets E G and E G respectively G is isomorphic to G if and only if there exists a one to one correspondences g V G V G and E G E G that preserves edgepoint functions of G and G Graphs and Trees 26 Graph Isomorphism To show isomorphic must show mapping If G and G have n vertices and m edges The number of one to one correspondences From vertices to vertices is n From edges to edges is m So total number of pairs is n m If m n 20 There would be 20 20 5 9 x 1020 pairs to check Assuming 1 nanosecond per check 1 9 x 1020 years To show not isomorphic show an invariant doesn t hold 24 July 2007 Graphs and Trees 27 Graph Isomorphic Invariants Has n vertices Has m edges Has a vertex of degree k Has m vertices of degree k Has a circuit of length k Has a simple circuit of length k Has m simple circuits of length k Is connected Has an Euler circuit Has a Hamiltonian circuit 24 July 2007 Graphs and Trees 28 Graph Isomorphism Examples 24 July 2007 Graphs and Trees 29 Trees A graph is circuit free if and only if it has no nontrivial circuits A graph is called a tree if it is Circuit free and Connected A trivial tree is a graph that consists of a single vertex An empty tree has no vertices or edges A graph is a forest if and only if it is circuit free Terminal vertex a leaf degree 1 Internal vertex a branch vertex has degree 1 24 July 2007 Graphs and Trees 30 Tree Proofs For any positive integer n any tree with n vertices has n 1 edges If G is any connected graph C is any nontrivial circuit in G and any one of the edges of C is removed then …


View Full Document

UMD CMSC 250 - Graphs and Trees

Download Graphs and Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Graphs and Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Graphs and Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?