Slides for Rosen, 5th edition - Academics | WPI

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


Recently Viewed Presentations

  • Epic Title -

    Epic Title -

    Introduction to Landscape Conservation Cooperatives. The idea was initially formulated by FWS Director Sam Hamilton and formally established by Department of Interior (DOI) Secretarial Order 3289 issued by Secretary Ken Salazar in Sept 2009 stated "…Interior bureaus and agencies must...
  • NAPW 2012 -

    NAPW 2012 -

    The Difference. The environment must be conducive for those students that do want the rigorous structure of professional-track ballet training without taking away from the attention given to, or the experience of, the recreational dancers.
  • Tannins - Texas A&amp;M AgriLife

    Tannins - Texas A&M AgriLife

    Tannins. Stephanie Diamond, Emilee Landers, Andrea Sierra-Cadavid. ... Tannins bind carbohydrates and proteins and become insoluble ... Extract from pomegranate ellagitanninscould be used for colon cancer prevention and treatment . Red Wine Tannins. Belongs to Non-hydrolyzable group.
  • C


    Rejecting configuration: q = q. r, or u = e and transition says move leftHalting configuration: Accepting/rejecting configuration. One-step execution semantics: for non-halting configuration C, Next(C) is the configuration resulting from executing one transition of M.
  • Cours 5 - Électricité

    Cours 5 - Électricité

    Temps de relaxation Temps nécessaire pour atteindre l'équilibre de charge dans un matériau Induction Un corps acquérant une charge électrique sans contact l'obtient par induction Constante de permittivité du vide ε0 (epsilon 0) ε0 = 8.85 x 10-12 C2/N.m2 avec...
  • Volume A - Cengage

    Volume A - Cengage

    Volume C Late Nineteenth Century: 1865-1910 Stephen Crane This photograph captures some of the chaos and random-ness of the Civil War as experienced in Fred Collins's quest for water in the midst of battle, in Stephen Crane's "A Mystery of...
  • ENGI 1313 Mechanics I

    ENGI 1313 Mechanics I

    Yes, at G Example 30-01 (cont.) Support Reaction G What equilibrium equation? Example 30-01 (cont.) Draw Section FBD Assume all truss member forces are in tension Example 30-01 (cont.) Equilibrium Equation? Example 30-02 Determine the force in members OE, LE,...
  • Community Volunteering Learning Goals Students will be able

    Community Volunteering Learning Goals Students will be able

    is open to all students at the Academy, we meet by-weekly to plan liturgies, activates and fundraising ideas. The Chaplaincy Team is split into three groups- Prayer, Publicity and Projects.