Notes Graphs Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 8 1 8 5 of Rosen cse235 cse unl edu Introduction I Notes 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 Introduction II Notes Introduction III Notes 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 b4 b1 v2 b2 b5 b3 v3 v4 b6 Introduction IV Notes The question now becomes does there exist a path in the following graph such that every edge is traversed exactly once v1 b0 b1 b5 v2 b2 b4 b3 v4 b6 v3 Definitions I Definition A simple graph G V E is a 2 tuple with 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 Notes Definitions II 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 Definitions III Notes Notes 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 Adjacency For now we will concern ourselves with simple undirected graphs We now look at some more terminology 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 Notes Terminology Notes Degree Definition 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 deg v In a multigraph a loop contributes to the degree twice A vertex of degree 0 is called isolated Terminology Notes Handshake Theorem Theorem Let G V E be an undirected graph Then X 2 E deg v v V 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 Handshake Lemma Corollary An undirected graph has an even number of vertices of odd degree Notes Terminology Directed Graphs I Notes 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 Notes 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 The out degree of v is the number of edges incident from v deg v 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 Theorem Let G V E be a directed graph Then X X deg v deg v E v V v V Notes More Terminology I Notes A path in a graph is a sequence of vertices v1 v2 vk such that vi vi 1 E for all i 1 k 1 We can denote such a path by p v1 vk The length of p is the number of edges in the path p k 1 More Terminology II Notes 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 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 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 Notes Bipartite Graphs Notes Definition 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 We often use G L R E to denote a bipartite graph Bipartite Graphs Notes Theorem A graph is bipartite if and only if it contains no odd length cycles 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 Bipartite Graphs Notes 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 Decomposing Composing Graphs I Notes We can partially decompose graphs by considering subgraphs Definition A subgraph of a graph G V E is a graph H V 0 E …
View Full Document
Unlocking...