Math 428 Sections 1.1-1.2 PDF

Math 428 1.1, Graphs and Graph Models Definitions A graph (represented by an ordered pair) G V, E consists of a finite (non-empty) set of vertices V and a finite set of edges E. An edge is specified by giving the pair of vertices it connects. The order (n) of a graph...

Math 428 1.1, Graphs and Graph Models Definitions A graph (represented by an ordered pair) G V, E consists of a finite (non-empty) set of vertices V and a finite set of edges E. An edge is specified by giving the pair of vertices it connects. The order (n) of a graph G is the number of vertices of G, and size (m) of G is the number of edges. Two vertices are adjacent if they are joined by an edge. An edge w a, b is incident to vertices a and b if it joins them by an edge. The degree of a vertex u, deg u , is the number of vertices adjacent to u. Problem. What is the sum of degrees of all vertices? S Mgc Definitions A directed graph is a graph where every edge has a direction associated with it. (We’ll mostly discuss undirected graphs.)  A walk v1, v2, , vn is a sequence of vertices such that consecutive vertices vk , vk 1 are adjacent. (Edges may be repeated in a walk.) A trail is a walk in which no edges are repeated. A path is a walk in which all vertices are distinct. A circuit is a closed trail of length 3 or more. A cycle is circuit that repeats no vertex except for the first and last. A cycle of odd length is called an odd cycle, and a cycle of even length is called an even cycle. in ii in title Problem. Determine if the walk is a path, trail, circuit, and/or cycle. iii i iii iii Definitions A connected graph is a graph where every two vertices are connected by some path. G G A subgraph V V , E of a graph G V, E is a graph where V V and E E. A subgraph G is a proper subgraph if V V and E E. A graph F is an induced subgraph of a graph G if – F is a subgraph of G, and – whenever u, v are vertices of F and u, v is an edge of G, then u, v E F.  1.1/#3. Let S 2, 3, 4, 7, 11, 13. Sketch a graph G such that a) V G S, and b) if u, v S and (u v or u v in S), then uv E G. Theorem 1.6: If a graph G contains a u v walk of length l, then G contains a u v path of length at most l. Proof: Definitions The distance between vertices u and v is the smallest length of any path u v in G. (denoted by dG u, v or d u, v ) The diameter of a connected graph G is the greatest distance between any two vertices in G (denoted by diam G ) Au v geodesic is a u v path of length d u, v. Problem. Find a) d t, s , b) diam G , and c) a u v geodesic.