New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Discrete Struc

by: Zackary Cronin
Zackary Cronin

GPA 3.89


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




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.

Popular in Computer Science and Engineering


Reviews for Discrete Struc


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.