Graphs CSE235 Graphs Introduction Types Classes Representations Isomorphism Slides by Christopher M Bourke Instructor Berthe Y Choueiry Connectivity Euler Hamiltonian Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 56 Sections 9 1 9 5 of Rosen Introduction I Graphs CSE235 Introduction Types Classes Representations Isomorphism Connectivity Euler Hamiltonian 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 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 2 56 Introduction II Graphs CSE235 Introduction Types Classes Representations Isomorphism Connectivity Euler Hamiltonian 3 56 Introduction III Graphs CSE235 Introduction 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 Types Classes Representations Isomorphism v1 Connectivity Euler Hamiltonian b0 b1 v2 b2 b3 v3 4 56 b4 b5 b6 v4 Introduction IV Graphs CSE235 Introduction The question now becomes does there exist a path in the following graph such that every edge is traversed exactly once Types Classes v1 Representations Isomorphism b0 b1 Connectivity Euler Hamiltonian v3 5 56 b5 v2 b2 b4 b3 b6 v4 Definitions I Graphs CSE235 Introduction Definition Types A simple graph G V E is a 2 tuple with Classes Representations Isomorphism Connectivity Euler Hamiltonian V v1 v2 vn a finite set of vertices 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 6 56 Definitions II Graphs CSE235 Introduction Types Classes Representations Isomorphism Connectivity Euler Hamiltonian A multigraph is a graph in which the edge set E is a multiset Multiple distinct or parallel edges can exist between vertices A pseudograph is a graph in which the edge set E can have edges of the form v v called loops 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 A directed multigraph is a multigraph whose edges set consists of ordered pairs 7 56 Definitions III Graphs CSE235 Introduction Types Classes Representations Isomorphism Connectivity If we look at a graph as a relation then among other things Undirected graphs are symmetric Non pseudographs are irreflexive Multigraphs have nonnegative integer entries in their matrix this corresponds to degrees of relatedness Euler Hamiltonian Other types of graphs can include labeled graphs each edge has a uniquely identified label or weight colored graphs edges are colored etc 8 56 Terminology Adjacency Graphs CSE235 Introduction Types For now we will concern ourselves with simple undirected graphs We now look at some more terminology Classes Representations Isomorphism Connectivity Euler Hamiltonian 9 56 Definition Two vertices u v in an undirected graph G V E are called adjacent or neighbors if e u v E 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 Terminology Degree Graphs CSE235 Introduction Definition Types The degree of a vertex in an undirected graph G V E is the number of edges incident with it The degree of a vertex v V is denoted Classes Representations Isomorphism Connectivity deg v Euler Hamiltonian In a multigraph a loop contributes to the degree twice A vertex of degree 0 is called isolated 10 56 Terminology Handshake Theorem Graphs CSE235 Introduction Types Classes Representations Isomorphism Theorem Let G V E be an undirected graph Then X 2 E deg v v V Connectivity Euler Hamiltonian 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 11 56 Terminology Handshake Lemma Graphs CSE235 Introduction Types Classes Representations Isomorphism Connectivity Euler Hamiltonian 12 56 Corollary An undirected graph has an even number of vertices of odd degree Terminology Directed Graphs I Graphs CSE235 Introduction Types In a directed graph digraph G V E we have analogous definitions Classes Representations Isomorphism Let e u v E u is adjacent to or incident on v Connectivity Euler Hamiltonian v is adjacent from or incident from u u is the initial vertex v is the terminal vertex For a loop these are the same 13 56 Terminology Directed Graphs II Graphs CSE235 Introduction We make a distinction between incoming and outgoing edges with respect to degree Types Classes Representations Isomorphism Connectivity Euler Hamiltonian Let v V The in degree of v is the number of edges incident on v deg v The out degree of v is the number of edges incident from v deg v 14 56 Terminology Directed Graphs III Graphs CSE235 Introduction Types Classes 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 Representations Isomorphism Connectivity Euler Hamiltonian Theorem Let G V E be a directed graph Then X X deg v deg v E v V 15 56 v V More Terminology I Graphs CSE235 Introduction A path in a graph is a sequence of vertices Types Classes v1 v2 vk Representations Isomorphism Connectivity Euler Hamiltonian such that vi vi 1 E for all i 1 k 1 We can denote such a path by p v1 The length of p is the number of edges in the path p k 1 16 56 vk More Terminology II Graphs CSE235 Introduction Types Classes A cycle in a graph is a path that begins and ends at the same vertex v1 v2 vk v1 Representations Isomorphism Cycles are also called circuits Connectivity Euler Hamiltonian We define paths and cycles for directed graphs analogously 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 17 56 Classes Of Graphs Graphs CSE235 Introduction Types Classes Bipartite Graphs Representations Isomorphism Connectivity Euler Hamiltonian Complete Graphs Denoted Kn are simple graphs with n vertices where every possible
View Full Document
Unlocking...