Discrete Struc CECS 228
Popular in Course
Popular in Computer Science and Engineering
This 10 page Class Notes was uploaded by Zackary Cronin on Monday October 5, 2015. The Class Notes belongs to CECS 228 at California State University - Long Beach taught by Staff in Fall. Since its upload, it has received 25 views. For similar materials see /class/218758/cecs-228-california-state-university-long-beach in Computer Science and Engineering at California State University - Long Beach.
Reviews for Discrete Struc
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/05/15
DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H Rosen Chapter 8 Graphs 81 and 82 Introduction and Terminology A graph denoted by G V E is a discrete structure consisting of vertices v e V that are connected by edges e e E A graph is a directed graph if the edges are directed otherwise it is an undirected graph A directed edge is denoted by an ordered pair of the vertices that it connects a v and an undirected edge by an unordered pair L1 v Two vertices u v in a graph that are connected by an edge e L1 v are said to be adjacent e is called incident with u and v and u and v are called endpoints of e If u v is a directed edge in a directed graph u is said to be adjacent to v and v adjacent from u Also a is called the initial vertex and v the terminal vertex of the edge u v The degree of a vertex is the number of edges that are incident with a vertex In a directed graph the indegree of a vertex v denoted by deg v is the number of edges with v as their terminal vertex and the outdegree denoted by degv is the number of edges with v as their initial vertex A loop contributes l to both the in degree and the out degree A vertex with degree zero is an isolated vertex A vertex with degree 1 is a pendent vertex Multiple parallel edges are two or more edges connecting the same pair of vertices A loop is an edge that goes from a vertex to itself A simple graph is an undirected graph where each edge connects two distinct vertices and there is no loop A multigraph is a graph where some pairs of vertices are connected with multiple edges A pseudograph is an undirected graph that may contain multiple edges and loops See Table l for a summary of characteristics of different types of graphs One obtains a subgraph from a given graph by removing some vertices and all their incident edges The union of two simple graphs G1 V1 E1 and G2 V2 E2 is the simple graph G V E where V 1qu andE E1U E2 The cycle CH n23 consists ofn vertices v1 v2 vn v1 Adding a vertex to a cycle C n and connecting it to every vertex in C n results in a wheel Wn The n cube denoted by Qn is the graph that has vertices representing the Zn bit strings of length n where two vertices are adjacent iff the bit strings that they represent differ in exactly one bit position The complete graph with n vertices denoted by Kn is the simple graph that contains exactly one edge between each pair of distinct vertices A bipartite graph is a graph where its vertex set Vcan be partitioned into two disjoint nonempty sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 vn and edges v1 v2 v2 v3 and The complete bipartite graph denoted by Km is the simple graph that has its vertex set partitioned into two subsets V1 and V2 with m and n vertices respectively and every vertex in V1 is connected to every vertex in V2 Exercises in 81 and 82 83 Representing Graphs and Graph Is0m0rphism Methods for representing graphs I A simple graph can be represented by an edge list a list of all the edges in the graph or adjacency lists lists that specify all the vertices that are adjacent to each vertex I More general graphs including multigraphs pseudographs and directed multigraphs may be represented by adjacency matricesA aij where an equals to the number of edges that are associated to vi vj I Undirected graphs may also be represented by incidence matrices M mij where mil1 when edge e J is incident with vertex vi and 0 otherwise Graphs with the same structure are said to be isomorphic Formally two simple graphs G1 V1 E1 and G2 V2 E2 are isomorphic if there is a 11 and onto function f from V1 to V2 such that for all a and b in V1 a and b are adjacent in G1 iff a and b are adjacent in G2 Determining whether two simple graphs are isomorphic is usually difficult since there are n possible ll correspondence between the two vertex sets with n vertices However some properties called invariants in the graphs may be used to show that they are not isomorphic Important invariants in isomorphic graphs I Same number of vertices I Same number of edges I The degrees of the vertices must be the same Exercises in 83 84 Connectivity A path of length n in an undirected graph is a sequence of vertices v0 v1 vn such that v0 v1 v1 v2 v n1 vn are n edges in the graph A path of length n in a directed graph is a sequence of vertices v0 v1 v1 V2 vn1 vn are n directed edges in the graph A connected graph is an undirected graph where every pair of vertices is connected by a path A graph that is not connected is the union of two or more connected subgraphs which are called connected components A vertex is a cut vertex or articulation point if removing it and all edges incident with it results in more connected components than in the original graph vn such that v0 v1 o A directed graph is strongly connected if there is a path from a to b and from b to a for all vertices a and b in the graph The graph is weakly connected if the underlying undirected graph is connected The number of different paths of length r from vi to vj is equal to the 139 jth entry of AI where A is the adjacency matrix representing the graph consisting of vertices v1 v2 vn Paths may be used to help identify graphs that are not isomorphic based on the following O Two graphs are isomorphic only if they have simple circuits of the same length O Two graphs are isomorphic only if they contain paths that go through vertices so that the corresponding vertices in the two graphs have the same degree Exercises in 84 86 Shortest Path Problems Graphs that have a number assigned to each edge are called weighted graphs The length of a path in a weighted graph is the sum of the weights of the edges of this path A shortest path between two vertices is the path with the least length between them There can be more than one such path 0 A shortest path algorithm by Dijkstra Algorithm 1 in 86 Exercise in 86 CECS 228 DISCRETE STRUCTURES WITH COMPUTER SCIENCE INSTRUCTOR JEHO PARK SYLLABUS CHAPTER 391 LOGIC 0 Proposition A proposition is a statement that is either true or false but not both Washington D C is the capital ofllm39ted States ofAmerica Call me Mr Park 113 x12 We con ne our attention to declarative sentences CHAPTER 39I LOGIC Logical Operators Negation up Conjunction p q Disjunction p q Exclusive or p 69 q Implication p gt q f Biconditional p lt gt 1 Truth Tables Related Implications Converse Contrapositive and Inverse CHAPTER 391 LOGIC Example Q What are the converse contrapositive and inverse of the following statement quotThe home team wins whenever it is rainingquot A Converse If the home team wins then it is raining Contrapositive If the home teaIn does not win then it is not raining lnverse If it is not raining then the home team does not win CHAPTER 391 LOGIC Compound Propositions Precedence from highest to lowest gtlt gt Translating English Sentences using propositional variables and logical connectives System Speci cations in natural language into logical expressions consistent It should not contain con icting requirements Boolean Searches and Logic Puzzles Logic and Bit Operations GROUP WORKING