Introduction I Graphs Slides by Christopher M Bourke Instructor Berthe Y Choueiry Graph theory was introduced in the 18th century by Leonhard Euler via the Ko nigsberg bridge problem In Ko nigsberg old Prussia a river ran through town that created an island and then split off into two parts Fall 2007 Seven bridges were built so that people could easily get around Euler wondered is it possible to walk around Ko nigsberg crossing every bridge exactly once Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 9 1 9 5 of Rosen cse235 cse unl edu Introduction II Introduction III To solve this problem we need to model it mathematically Specifically we can define a graph whose vertices are the land areas and whose edges are the bridges v1 b0 b1 v2 b2 b3 v3 Introduction IV b4 b5 v4 b6 Definitions I The question now becomes does there exist a path in the following graph such that every edge is traversed exactly once A simple graph G V E is a 2 tuple with v1 b0 b1 v3 b4 b5 v2 b2 Definition b3 b6 v4 I V v1 v2 vn a finite set of vertices I E V V e1 e2 em an unordered set of edges where each ei v v 0 is an unordered pair of vertices v v 0 V Since V and E are sets it makes sense to consider their cardinality As is standard V n denotes the number of vertices in G and E m denotes the number of edges in G Definitions II Definitions III I A multigraph is a graph in which the edge set E is a multiset Multiple distinct or parallel edges can exist between vertices I A pseudograph is a graph in which the edge set E can have edges of the form v v called loops I A directed graph is one in which E contains ordered pairs The orientation of an edge v v 0 is said to be from v to v 0 I A directed multigraph is a multigraph whose edges set consists of ordered pairs If we look at a graph as a relation then among other things I Undirected graphs are symmetric I Non pseudographs are irreflexive I Multigraphs have nonnegative integer entries in their matrix this corresponds to degrees of relatedness Other types of graphs can include labeled graphs each edge has a uniquely identified label or weight colored graphs edges are colored etc Terminology Terminology Adjacency Degree For now we will concern ourselves with simple undirected graphs We now look at some more terminology Definition The degree of a vertex in an undirected graph G V E is the number of edges incident with it Definition Two vertices u v in an undirected graph G V E are called adjacent or neighbors if e u v E The degree of a vertex v V is denoted deg v We say that e is incident with or incident on the vertices u and v Edge e is said to connect u and v u and v are also called the endpoints of e In a multigraph a loop contributes to the degree twice A vertex of degree 0 is called isolated Terminology Terminology Handshake Theorem Handshake Lemma Theorem Let G V E be an undirected graph Then X 2 E deg v Corollary v V An undirected graph has an even number of vertices of odd degree The handshake lemma applies even in multi and pseudographs proof By definition each e v v 0 will contribute 1 to the degree of each vertex deg v deg v 0 If e v v is a loop then it contributes 2 to deg v Therefore the total degree over all vertices will be twice the number of edges Terminology Directed Graphs I In a directed graph digraph G V E we have analogous definitions I Let e u v E I u is adjacent to or incident on v I v is adjacent from or incident from u I u is the initial vertex I v is the terminal vertex I For a loop these are the same Terminology Directed Graphs II We make a distinction between incoming and outgoing edges with respect to degree I Let v V I The in degree of v is the number of edges incident on v deg v I Terminology Directed Graphs III Every edge e u v contributes 1 to the out degree of u and 1 to the in degree of v Thus the sum over all vertices is the same The out degree of v is the number of edges incident from v deg v More Terminology I A path in a graph is a sequence of vertices v1 v2 vk Theorem such that vi vi 1 E for all i 1 k 1 Let G V E be a directed graph Then X X deg v deg v E v V We can denote such a path by p v1 vk The length of p is the number of edges in the path v V p k 1 More Terminology II A cycle in a graph is a path that begins and ends at the same vertex v1 v2 vk v1 Cycles are also called circuits We define paths and cycles for directed graphs analogously Classes Of Graphs I Complete Graphs Denoted Kn are simple graphs with n vertices where every possible edge is present I Cycle Graphs Denoted Cn are simply cycles on n vertices I Wheels Denoted Wn are cycle graphs on n vertices with an additional vertex connected to all other vertices I n cubes Denoted Qn are graphs with 2n vertices corresponding to each bit string of length n Edges connect vertices whose bit strings differ by a single bit I Grid Graphs finite graphs on the N N grid A path or cycle is called simple if no vertex is traversed more than once From now on we will only consider simple paths and cycles Bipartite Graphs Bipartite Graphs Definition Theorem A graph is called bipartite if its vertex set V can be partitioned into two disjoint subsets L R such that no pair of vertices in L or R is connected A graph is bipartite if and only if it contains no odd length cycles We often use G L R E to denote a bipartite graph Bipartite Graphs Another way to look at this theorem is as follows A graph G can be colored here we color vertices by at most 2 colors such that no two adjacent vertices have the same color if and only if G is bipartite Decomposing Composing Graphs I We can partially decompose graphs by considering subgraphs A bipartite graph is complete if every u L is connected to every v R We denote a complete bipartite graph as Kn1 n2 which means that L n1 and R n2 Examples Definition A subgraph of a graph G V E is a graph H V 0 E 0 where I V 0 V and I E 0 E Subgraphs are simply part s of the original graph Decomposing Composing …
View Full Document
Unlocking...