# Slides for Rosen, 5th edition - Academics | WPI Module #22 - Graphs University of Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) by Kenneth H. Rosen 02/02/20 (c)2001-2003, Michael P. Frank 1

Module #22 - Graphs Module #22: Graph Theory Rosen 5th ed., chs. 8-9 ~44 slides (more later), ~3 lectures 02/02/20 (c)2001-2003, Michael P. Frank 2 Module #22 - Graphs What are Graphs? Not General meaning in everyday math:

A plot or chart of numerical data using a coordinate system. Technical meaning in discrete mathematics: A particular class of discrete structures (to be defined) that is useful for representing relations and has a convenient webbylooking graphical representation. 02/02/20 (c)2001-2003, Michael P. Frank 3 Module #22 - Graphs Applications of Graphs Potentially anything (graphs can represent relations, relations can describe the extension of any predicate). Apps in networking, scheduling, flow optimization, circuit design, path planning.

More apps: Geneology analysis, computer game-playing, program compilation, objectoriented design, 02/02/20 (c)2001-2003, Michael P. Frank 4 Module #22 - Graphs Simple Graphs Correspond to symmetric, irreflexive binary relations R. A simple graph G=(V,E) Visual Representation consists of: of a Simple Graph a set V of vertices or nodes (V corresponds to the universe of the relation R), a set E of edges / arcs / links: unordered pairs

of [distinct] elements u,v V, such that uRv. 02/02/20 (c)2001-2003, Michael P. Frank 5 Module #22 - Graphs Example of a Simple Graph Let V be the set of states in the farsoutheastern U.S.: I.e., V={FL, GA, AL, MS, LA, SC, TN, NC} Let E={{u,v}|u adjoins v} ={{FL,GA},{FL,AL},{FL,MS}, {FL,LA},{GA,AL},{AL,MS}, MS {MS,LA},{GA,SC},{GA,TN}, {SC,NC},{NC,TN},{MS,TN}, LA {MS,AL}} 02/02/20

(c)2001-2003, Michael P. Frank TN AL NC SC GA FL 6 Module #22 - Graphs Multigraphs Like simple graphs, but there may be more than one edge connecting two given nodes. A multigraph G=(V, E, f ) consists of a set V of vertices, a set E of edges (as primitive objects), and a function

Parallel edges f:E{{u,v}|u,vV uv}. E.g., nodes are cities, edges are segments of major highways. 02/02/20 (c)2001-2003, Michael P. Frank 7 Module #22 - Graphs Pseudographs Like a multigraph, but edges connecting a node to itself are allowed. (R may be reflexive.) A pseudograph G=(V, E, f ) where f:E{{u,v}|u,vV}. Edge eE is a loop if f(e)={u,u}={u}. E.g., nodes are campsites

in a state park, edges are hiking trails through the woods. 02/02/20 (c)2001-2003, Michael P. Frank 8 Module #22 - Graphs Directed Graphs Correspond to arbitrary binary relations R, which need not be symmetric. A directed graph (V,E) consists of a set of vertices V and a binary relation E on V. E.g.: V = set of People, E={(x,y) | x loves y} 02/02/20

(c)2001-2003, Michael P. Frank 9 Module #22 - Graphs Directed Multigraphs Like directed graphs, but there may be more than one arc from a node to another. A directed multigraph G=(V, E, f ) consists of a set V of vertices, a set E of edges, and a function f:EVV. E.g., V=web pages, E=hyperlinks. The WWW is a directed multigraph... 02/02/20 (c)2001-2003, Michael P. Frank

10 Module #22 - Graphs Types of Graphs: Summary Summary of the books definitions. Keep in mind this terminology is not fully standardized across different authors... Term Simple graph Multigraph Pseudograph Directed graph Directed multigraph 02/02/20 Edge type Undir.

Undir. Undir. Directed Directed Multiple edges ok? No Yes Yes No Yes (c)2001-2003, Michael P. Frank Selfloops ok? No No Yes Yes

Yes 11 Module #22 - Graphs 8.2: Graph Terminology You need to learn the following terms: Adjacent, connects, endpoints, degree, initial, terminal, in-degree, out-degree, complete, cycles, wheels, n-cubes, bipartite, subgraph, union. 02/02/20 (c)2001-2003, Michael P. Frank 12 Module #22 - Graphs

Adjacency Let G be an undirected graph with edge set E. Let eE be (or map to) the pair {u,v}. Then we say: u, v are adjacent / neighbors / connected. Edge e is incident with vertices u and v. Edge e connects u and v. Vertices u and v are endpoints of edge e. 02/02/20 (c)2001-2003, Michael P. Frank 13 Module #22 - Graphs Degree of a Vertex Let G be an undirected graph, vV a vertex. The degree of v, deg(v), is its number of

incident edges. (Except that any self-loops are counted twice.) A vertex with degree 0 is called isolated. A vertex of degree 1 is called pendant. 02/02/20 (c)2001-2003, Michael P. Frank 14 Module #22 - Graphs Handshaking Theorem Let G be an undirected (simple, multi-, or pseudo-) graph with vertex set V and edge set E. Then deg(v) 2 E vV

Corollary: Any undirected graph has an even number of vertices of odd degree. 02/02/20 (c)2001-2003, Michael P. Frank 15 Module #22 - Graphs Directed Adjacency Let G be a directed (possibly multi-) graph, and let e be an edge of G that is (or maps to) (u,v). Then we say:

02/02/20 u is adjacent to v, v is adjacent from u e comes from u, e goes to v. e connects u to v, e goes from u to v the initial vertex of e is u the terminal vertex of e is v (c)2001-2003, Michael P. Frank 16 Module #22 - Graphs Directed Degree Let G be a directed graph, v a vertex of G. The in-degree of v, deg(v), is the number of edges going to v. The out-degree of v, deg(v), is the number of edges coming from v. The degree of v, deg(v):deg(v)+degdeg(v), is the

sum of vs in-degree and out-degree. 02/02/20 (c)2001-2003, Michael P. Frank 17 Module #22 - Graphs Directed Handshaking Theorem Let G be a directed (possibly multi-) graph with vertex set V and edge set E. Then: 1 deg (v) deg (v) deg(v) E 2 vV vV vV

Note that the degree of a node is unchanged by whether we consider its edges to be directed or undirected. 02/02/20 (c)2001-2003, Michael P. Frank 18 Module #22 - Graphs Special Graph Structures Special cases of undirected graph structures: Complete graphs Kn Cycles Cn Wheels Wn

02/02/20 n-Cubes Qn Bipartite graphs Complete bipartite graphs Km,n (c)2001-2003, Michael P. Frank 19 Module #22 - Graphs Complete Graphs For any nN, a complete graph on n vertices, Kn, is a simple graph with n nodes in which every node is adjacent to every other node: u,vV: uv{u,v}E.

K1 K3 K2 K4 K5 K6 n 1 n(n 1) Note that Kn has i 2 edges. i 1 02/02/20

(c)2001-2003, Michael P. Frank 20 Module #22 - Graphs Cycles For any n3, a cycle on n vertices, Cn, is a simple graph where V={v1,v2, ,vn} and E={{v1,v2},{v2,v3},,{vn1,vn},{vn,v1}}. C3 C4 C5 C6 C7

C8 How many edges are there in Cn? 02/02/20 (c)2001-2003, Michael P. Frank 21 Module #22 - Graphs Wheels For any n3, a wheel Wn, is a simple graph obtained by taking the cycle Cn and adding one extra vertex vhub and n extra edges {{vhub,v1}, {vhub,v2},,{vhub,vn}}. W3 W4

W5 W6 W7 How many edges are there in Wn? 02/02/20 (c)2001-2003, Michael P. Frank W8 22 Module #22 - Graphs n-cubes (hypercubes) For any nN, the hypercube Qn is a simple

graph consisting of two copies of Qn-1 connected together at corresponding nodes. Q0 has 1 node. Q0 Q1 Q2 Q3 Q4 Number of vertices: 2n. Number of edges:Exercise to try! 02/02/20 (c)2001-2003, Michael P. Frank 23

Module #22 - Graphs n-cubes (hypercubes) For any nN, the hypercube Qn can be defined recursively as follows: Q0={{v0},} (one node and no edges) For any nN, if Qn=(V,E), where V={v1,,va} and E={e1,,eb}, then Qn+deg1=(V{v1,,va}, E{e1,,eb}{{v1,v1},{v2,v2},, {va,va}}) where v1,,va are new vertices, and where if ei={vj,vk} then ei={vj,vk}. 02/02/20 (c)2001-2003, Michael P. Frank 24 Module #22 - Graphs Bipartite Graphs

Defn.: A graph G=(V,E) is bipartite (twopart) iff V = V1V2 where V1V2= and eE: v1V1,v2V2: e={v1,v2}. In English: The graph can be divided into two parts in such a way that all edges go between the two parts. This definition can easily be adapted for the case of multigraphs and directed graphs as well. 02/02/20 (c)2001-2003, Michael P. Frank V1 V2 Can represent with zero-one matrices. 25

Module #22 - Graphs Complete Bipartite Graphs For m,nN, the complete bipartite graph Km,n is a bipartite graph where |V1| = m, |V2| = n, and E = {{v1,v2}|v1V1 v2V2}. That is, there are m nodes in the left part, n nodes in the right part, and every node in the left part is connected to every node in the right part. 02/02/20 K4,3 Km,n has _____ nodes and _____ edges. (c)2001-2003, Michael P. Frank

26 Module #22 - Graphs Subgraphs A subgraph of a graph G=(V,E) is a graph H=(W,F) where WV and FE. G 02/02/20 H (c)2001-2003, Michael P. Frank 27 Module #22 - Graphs

Graph Unions The union G1G2 of two simple graphs G1=(V1, E1) and G2=(V2,E2) is the simple graph (V1V2, E1E2). 02/02/20 a b d e c

a d (c)2001-2003, Michael P. Frank b c f 28 Module #22 - Graphs 8.3: Graph Representations & Isomorphism Graph representations: Adjacency lists. Adjacency matrices. Incidence matrices.

Graph isomorphism: Two graphs are isomorphic iff they are identical except for their node names. 02/02/20 (c)2001-2003, Michael P. Frank 29 Module #22 - Graphs Adjacency Lists A table with 1 row per vertex, listing its adjacent vertices. Adjacent b a

c d f 02/02/20 e Vertex a b c d e f Vertices b, c a, c, e, f

a, b, f b c, b (c)2001-2003, Michael P. Frank 30 Module #22 - Graphs Directed Adjacency Lists 1 row per node, listing the terminal nodes of each edge incident from that node. 02/02/20 (c)2001-2003, Michael P. Frank 31

Module #22 - Graphs Adjacency Matrices A way to represent simple graphs possibly with self-loops. Matrix A=[aij], where aij is 1 if {vi, vj} is an edge of G, and is 0 otherwise. Can extend to pseudographs by letting each matrix elements be the number of links (possibly >1) between the nodes. 02/02/20 (c)2001-2003, Michael P. Frank 32 Module #22 - Graphs Graph Isomorphism

Formal definition: Simple graphs G1=(V1, E1) and G2=(V2, E2) are isomorphic iff a bijection f:V1V2 such that a,bV1, a and b are adjacent in G1 iff f(a) and f(b) are adjacent in G2. f is the renaming function between the two node sets that makes the two graphs identical. This definition can easily be extended to other types of graphs. 02/02/20 (c)2001-2003, Michael P. Frank 33 Module #22 - Graphs Graph Invariants under Isomorphism Necessary but not sufficient conditions for G1=(V1, E1) to be isomorphic to G2=(V2, E2):

We must have that |V1|=|V2|, and |E1|=|E2|. The number of vertices with degree n is the same in both graphs. For every proper subgraph g of one graph, there is a proper subgraph of the other graph that is isomorphic to g. 02/02/20 (c)2001-2003, Michael P. Frank 34 Module #22 - Graphs Isomorphism Example If isomorphic, label the 2nd graph to show the isomorphism, else identify difference. d b

a d e 02/02/20 b c f c (c)2001-2003, Michael P. Frank a f

e 35 Module #22 - Graphs Are These Isomorphic? If isomorphic, label the 2nd graph to show the isomorphism, else identify difference. a b d c 02/02/20 e

(c)2001-2003, Michael P. Frank Same # of vertices Same # of edges Different # of verts of degree 2! (1 vs 3) 36 Module #22 - Graphs 8.4: Connectivity In an undirected graph, a path of length n from u to v is a sequence of adjacent edges going from vertex u to vertex v. A path is a circuit if u=v. A path traverses the vertices along it.

A path is simple if it contains no edge more than once. 02/02/20 (c)2001-2003, Michael P. Frank 37 Module #22 - Graphs Paths in Directed Graphs Same as in undirected graphs, but the path must go in the direction of the arrows. 02/02/20 (c)2001-2003, Michael P. Frank 38

Module #22 - Graphs Connectedness An undirected graph is connected iff there is a path between every pair of distinct vertices in the graph. Theorem: There is a simple path between any pair of vertices in a connected undirected graph. Connected component: connected subgraph A cut vertex or cut edge separates 1 connected component into 2 if removed. 02/02/20 (c)2001-2003, Michael P. Frank 39

Module #22 - Graphs Directed Connectedness A directed graph is strongly connected iff there is a directed path from a to b for any two verts a and b. It is weakly connected iff the underlying undirected graph (i.e., with edge directions removed) is connected. Note strongly implies weakly but not viceversa. 02/02/20 (c)2001-2003, Michael P. Frank 40 Module #22 - Graphs Paths & Isomorphism Note that connectedness, and the existence

of a circuit or simple circuit of length k are graph invariants with respect to isomorphism. 02/02/20 (c)2001-2003, Michael P. Frank 41 Module #22 - Graphs Counting Paths w Adjacency Matrices Let A be the adjacency matrix of graph G. The number of paths of length k from vi to vj is equal to (Ak)i,j. The notation (M)i,j denotes mi,j where [mi,j] = M. 02/02/20

(c)2001-2003, Michael P. Frank 42 Module #22 - Graphs 8.5: Euler & Hamilton Paths An Euler circuit in a graph G is a simple circuit containing every edge of G. An Euler path in G is a simple path containing every edge of G. A Hamilton circuit is a circuit that traverses each vertex in G exactly once. A Hamilton path is a path that traverses each vertex in G exactly once. 02/02/20 (c)2001-2003, Michael P. Frank

43 Module #22 - Graphs Bridges of Knigsberg Problem Can we walk through town, crossing each bridge exactly once, and return to start? A D B C The original problem 02/02/20 Equivalent multigraph (c)2001-2003, Michael P. Frank 44

Module #22 - Graphs Euler Path Theorems Theorem: A connected multigraph has an Euler circuit iff each vertex has even degree. Proof: () The circuit contributes 2 to degree of each node. () By construction using algorithm on p. 580-581 Theorem: A connected multigraph has an Euler path (but not an Euler circuit) iff it has exactly 2 vertices of odd degree. One is the start, the other is the end. 02/02/20 (c)2001-2003, Michael P. Frank 45

Module #22 - Graphs Euler Circuit Algorithm Begin with any arbitrary node. Construct a simple path from it till you get back to start. Repeat for each remaining subgraph, splicing results back into original cycle. 02/02/20 (c)2001-2003, Michael P. Frank 46 Module #22 - Graphs Round-the-World Puzzle Can we traverse all the vertices of a dodecahedron, visiting each once?`

Dodecahedron puzzle 02/02/20 Equivalent graph (c)2001-2003, Michael P. Frank Pegboard version 47 Module #22 - Graphs Hamiltonian Path Theorems Diracs theorem: If (but not only if) G is connected, simple, has n3 vertices, and v deg(v)n/2, then G has a Hamilton circuit. Ores corollary: If G is connected, simple, has

n3 nodes, and deg(u)+degdeg(v)n for every pair u,v of non-adjacent nodes, then G has a Hamilton circuit. 02/02/20 (c)2001-2003, Michael P. Frank 48 Module #22 - Graphs HAM-CIRCUIT is NP-complete Let HAM-CIRCUIT be the problem: Given a simple graph G, does G contain a Hamiltonian circuit? This problem has been proven to be NP-complete! This means, if an algorithm for solving it in polynomial time were found, it could be used to

solve all NP problems in polynomial time. 02/02/20 (c)2001-2003, Michael P. Frank 49 Module #22 - Graphs 8.6: Shortest-Path Problems Not covering this semester. 02/02/20 (c)2001-2003, Michael P. Frank 50 Module #22 - Graphs

8.7: Planar Graphs Not covering this semester. 02/02/20 (c)2001-2003, Michael P. Frank 51 Module #22 - Graphs 8.8: Graph Coloring Not covering this semester. 02/02/20 (c)2001-2003, Michael P. Frank 52

Module #22 - Graphs 9.1: Introduction to Trees A tree is a connected undirected graph that contains no circuits. Theorem: There is a unique simple path between any two of its nodes. A (not-necessarily-connected) undirected graph without simple circuits is called a forest. You can think of it as a set of trees having disjoint sets of nodes. A leaf node in a tree or forest is any pendant or isolated vertex. An internal node is any non-leaf vertex (thus it has degree ___ ). 02/02/20 (c)2001-2003, Michael P. Frank

53 Module #22 - Graphs Tree and Forest Examples Leaves in green, internal nodes in brown. A Tree: 02/02/20 A Forest: (c)2001-2003, Michael P. Frank 54 Module #22 - Graphs Rooted Trees

A rooted tree is a tree in which one node has been designated the root. Every edge is (implicitly or explicitly) directed away from the root. You should know the following terms about rooted trees: Parent, child, siblings, ancestors, descendents, leaf, internal node, subtree. 02/02/20 (c)2001-2003, Michael P. Frank 55 Module #22 - Graphs Rooted Tree Examples Note that a given unrooted tree with n nodes yields n different rooted trees.

root Same tree except for choice of root root 02/02/20 (c)2001-2003, Michael P. Frank 56 Module #22 - Graphs Rooted-Tree Terminology Exercise Find the parent, children, siblings, ancestors, &

descendants of node f. e i o n h d r m b a root c

g q f p 02/02/20 j k (c)2001-2003, Michael P. Frank l 57 Module #22 - Graphs

n-ary trees A rooted tree is called n-ary if every vertex has no more than n children. It is called full if every internal (non-leaf) vertex has exactly n children. A 2-ary tree is called a binary tree. These are handy for describing sequences of yes-no decisions. Example: Comparisons in binary search algorithm. 02/02/20 (c)2001-2003, Michael P. Frank 58 Module #22 - Graphs Which Tree is Binary?

Theorem: A given rooted tree is a binary tree iff every node other than the root has degree ___, and the root has degree ___. 02/02/20 (c)2001-2003, Michael P. Frank 59 Module #22 - Graphs Ordered Rooted Tree This is just a rooted tree in which the children of each internal node are ordered. In ordered binary trees, we can define: left child, right child left subtree, right subtree For n-ary trees with n>2, can use terms like

leftmost, rightmost, etc. 02/02/20 (c)2001-2003, Michael P. Frank 60 Module #22 - Graphs Trees as Models Can use trees to model the following: Saturated hydrocarbons Organizational structures Computer file systems In each case, would you use a rooted or a non-rooted tree? 02/02/20

(c)2001-2003, Michael P. Frank 61 Module #22 - Graphs Some Tree Theorems Any tree with n nodes has e = n1 edges. Proof: Consider removing leaves. A full m-ary tree with i internal nodes has n=mi+deg1 nodes, and =(m1)i+deg1 leaves. Proof: There are mi children of internal nodes, plus the root. And, = ni = (m1)i+deg1. Thus, when m is known and the tree is full, we can compute all four of the values e, i, n, and , given any one of them. 02/02/20

(c)2001-2003, Michael P. Frank 62 Module #22 - Graphs Some More Tree Theorems Definition: The level of a node is the length of the simple path from the root to the node. The height of a tree is maximum node level. A rooted m-ary tree with height h is called balanced if all leaves are at levels h or h1. Theorem: There are at most mh leaves in an mary tree of height h. Corollary: An m-ary tree with leaves has height hlogm . If m is full and balanced then h=logm. 02/02/20 (c)2001-2003, Michael P. Frank

63 Module #22 - Graphs 9.2: Applications of Trees Binary search trees A simple data structure for sorted lists Decision trees Minimum comparisons in sorting algorithms Prefix codes Huffman coding Game trees 02/02/20 (c)2001-2003, Michael P. Frank 64

Module #22 - Graphs Binary Search Trees A representation for sorted sets of items. Supports the following operations in (log n) average-case time: Searching for an existing item. Inserting a new item, if not already present. Supports printing out all items in (n) time. Note that inserting into a plain sequence ai would instead take (n) worst-case time. 02/02/20 (c)2001-2003, Michael P. Frank 65

Module #22 - Graphs Binary Search Tree Format Items are stored at individual tree nodes. We arrange for the tree to always obey this invariant: Example: 3 For every item x, Every node in xs left subtree is less than x. Every node in xs right subtree is greater than x. 02/02/20

7 1 0 (c)2001-2003, Michael P. Frank 12 5 2 9 8 15 11 66

Module #22 - Graphs Recursive Binary Tree Insert procedure insert(T: binary tree, x: item) v := root[T] if v = null then begin root[T] := x; return Done end else if v = x return Already present else if x < v then return insert(leftSubtree[T], x) else {must be x > v} return insert(rightSubtree[T], x) 02/02/20 (c)2001-2003, Michael P. Frank 67 Module #22 - Graphs

Decision Trees (pp. 646-649) A decision tree represents a decision-making process. Each possible decision point or situation is represented by a node. Each possible choice that could be made at that decision point is represented by an edge to a child node. In the extended decision trees used in decision analysis, we also include nodes that represent random events and their outcomes. 02/02/20 (c)2001-2003, Michael P. Frank 68 Module #22 - Graphs

Coin-Weighing Problem Imagine you have 8 coins, one of which is a lighter counterfeit, and a free-beam balance. No scale of weight markings is required for this problem! How many weighings are needed to guarantee that the counterfeit coin will be found? 02/02/20 (c)2001-2003, Michael P. Frank ? 69 Module #22 - Graphs

As a Decision-Tree Problem In each situation, we pick two disjoint and equalsize subsets of coins to put on the scale. A given sequence of weighings thus yields a decision tree with branching factor 3. The balance then decides whether to tip left, tip right, or stay balanced. 02/02/20 (c)2001-2003, Michael P. Frank 70 Module #22 - Graphs

Applying the Tree Height Theorem The decision tree must have at least 8 leaf nodes, since there are 8 possible outcomes. In terms of which coin is the counterfeit one. Recall the tree-height theorem, hlogm. Thus the decision tree must have height h log38 = 1.893 = 2. Lets see if we solve the problem with only 2 weighings 02/02/20 (c)2001-2003, Michael P. Frank 71 Module #22 - Graphs

General Solution Strategy The problem is an example of searching for 1 unique particular item, from among a list of n otherwise identical items. Somewhat analogous to the adage of searching for a needle in haystack. Armed with our balance, we can attack the problem using a divideand-conquer strategy, like whats done in binary search. We want to narrow down the set of possible locations where the desired item (coin) could be found down from n to just 1, in a logarithmic fashion. Each weighing has 3 possible outcomes. Thus, we should use it to partition the search space into 3 pieces that are as close to equal-sized as possible. This strategy will lead to the minimum possible worst-case number of weighings required. 02/02/20 (c)2001-2003, Michael P. Frank

72 Module #22 - Graphs General Balance Strategy On each step, put n/3 of the n coins to be searched on each side of the scale. If the scale tips to the left, then: The lightweight fake is in the right set of n/3 n/3 coins. If the scale tips to the right, then: The lightweight fake is in the left set of n/3 n/3 coins. If the scale stays balanced, then: The fake is in the remaining set of n 2n/3 n/3 coins that were not weighed!

Except if n mod 3 = 1 then we can do a little better by weighing n/3 of the coins on each side. You can prove that this strategy always leads to a balanced 3-ary tree. 02/02/20 (c)2001-2003, Michael P. Frank 73 Module #22 - Graphs Coin Balancing Decision Tree Heres what the tree looks like in our case: left: 123 1 vs. 2 L:1 02/02/20

123 vs 456 right: 456 balanced: 78 4 vs. 5 7 vs. 8 R:2 B:3 L:4 R:5 B:6 L:7 (c)2001-2003, Michael P. Frank R:8 74

Module #22 - Graphs Prefix Codes & Huffman Coding pp. 649-651 02/02/20 (c)2001-2003, Michael P. Frank 75 Module #22 - Graphs Game Trees pp. 651-656 02/02/20 (c)2001-2003, Michael P. Frank

76 Module #22 - Graphs 9.3: Tree Traversal Universal address systems Traversal algorithms Depth-first traversal: Preorder traversal Inorder traversal Postorder traversal Breadth-first traversal Infix/prefix/postfix notation 02/02/20 (c)2001-2003, Michael P. Frank 77

Module #22 - Graphs 9.4: Spanning Trees Not covering this semester. 02/02/20 (c)2001-2003, Michael P. Frank 78 Module #22 - Graphs 9.5: Minimum Spanning Trees Not covering this semester. 02/02/20 (c)2001-2003, Michael P. Frank

79