Chapter 9   Trees

[References]

1. Discrete Math - 7th Edition , Richard Johnsonbaugh, Pearson

Trees

9.1   Introduction

9.2   Terminology and Characterizations of Trees

Problem-Solving Corner: Trees

9.3   Spanning Trees

9.4   Minimal Spanning Trees

9.5   Binary Trees

9.6   Tree Traversals

9.7   Decision Trees and the Minimum Time for Sorting

9.8   Isomorphisms of Trees

9.9   Game Trees(Skipped)

Tree is a discrete structure that represents hierarchical relationships between individual elements or nodes. A tree in which a parent has no more than two children is called a binary tree.

***

​(DM Ch. 1, Sets and Logic, Lecture Note)

http://matrix.skku.ac.kr/2018-DM/Ch-1/
DM-Ch-1-Lab  http://matrix.skku.ac.kr/2018-DM/DM-Ch-1-Lab.html   (Use Chrome browser, not IE)
(DM Ch. 1, 동영상강의)
Discrete Math 이산수학 Ch 0 Introduction
https://youtu.be/9ahFnOFTWNQ
Discrete Math 이산수학 Ch 1, 1.1, 1.2 Propositions
https://youtu.be/QgdKqmCFW2Y
Discrete Math 이산수학 Ch 1, 1.3, 1.4 Rules of Inference
https://youtu.be/92siPfThf0M
Discrete Math 이산수학 Ch 1, 1.5, 1.6 Nested Quantifiers
https://youtu.be/7M7w9eX5D0Q

​(DM Ch. 2, Proofs, Lecture Note)

(DM Ch. 2, 동영상강의)

​DM Ch 2 Lecture 1 Sec 2.1, 2.2 2.2 More Methods of Proof Problem   https://youtu.be/xEMkHb2AkYk
​DM Ch 2 Lecture 2 Sec 2.4, 2.5 Math Induction and Well-Ordering Property
https://youtu.be/areatkjOjcg

​(DM Ch. 3, Functions, Sequences, and Relations, Lecture Note)

(DM Ch. 3, 동영상강의)
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 1  https://youtu.be/MhM_9ZuGAis
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 2
https://youtu.be/ZjAtN9HkZwM
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 3
https://youtu.be/Uuwsx2aiEPI

Ch 4, Algorithms,

Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-4/

DM-Ch-4-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-4-Lab.html
(DM Ch. 4, 동영상강의)
https://youtu.be/Dtv-9ykjFFA
​DM 이산수학 Ch 4,
...

[Week 6] Ch 5, Introduction to Number Theory (if time permits)

- Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-5/

DM-Ch-5-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-5-Lab.html
(DM Ch. 5, 동영상강의)

​DM 이산수학 Ch 5,

Ch 6, Counting Methods and the Pigeonhole Principle (lightly covered)

- Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-6/

DM-Ch-6-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-6-Lab.html
(DM Ch. 6, 동영상강의)

​DM 이산수학 Ch 6,

Ch 7, Recurrence Relations,   - Lecture Note
http://matrix.skku.ac.kr/2018-DM/Ch-7/

DM-Ch-7-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-7-Lab.html
(DM Ch. , 동영상강의)

​DM 이산수학 Ch ,

Ch 8, Graph Theory (if time permits),  - Lecture Note
http://matrix.skku.ac.kr/2018-DM/Ch-8/

DM-Ch-8-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-8-Lab.html
(DM Ch. , 동영상강의)

Ch 9, Trees (if time permits), Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-9/

DM-Ch-9-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-9-Lab.html
(DM Ch. , 동영상강의)

10 Network Models (if time permits)  http://matrix.skku.ac.kr/2018-DM/Ch-10/
11 Boolean Algebras and Combinatorial Circuits (if time permits)
12 Automata, Grammars, and Languages (if time permits)
13 Computational Geometry (if time permits)
Appendix

DM  Lecture Note & Lab & 동영상강의

******

9  Trees

9.1 Introduction

Figure 1.2 The tree.

 Definition  1.1

 Rooted tree A rooted tree is a tree in which one vertex has been designated as the root.

 Example  1.2 In Figure,  is the root.  Figure is a rooted tree.  The unique simple path from  to  is .

In graph theory rooted trees are typically drawn with their roots at the top.

The simple path from the root to any given vertex is unique, each vertex is on a uniquely determined level.

We call the level of the root level .

The vertices under the root are said to be on level , and so on.

 Level of a Vertex The level of a vertex  is the length of the simple path from the root to .

 Height The height of a rooted tree is the maximum of all level number of its vertices.

 Example  1.3

 Level of vertex Level of vertex Level of vertex

Figure 1.4 Th tree with the root at the top.

 Example  1.4

 Example  1.5 A rooted tree is often used to specify hierarchical relationships.  If vertex  is on a level one less than the level of vertex  and  and  are adjacent,   then is “just above”  and a logical relationship exists between  and :           dominates  or  is subordinate to .

An example of such a tree, which is the administrative organizational chart of a hypothetical university, is given in Figure 1.6.

 Example 1.6

Figure 1.8 The structure of Figure 1.7 shown as a rooted tree.

 Example  1.7 Hierarchical Definition trees Such trees are used to show logical relationships among records in a database.  The tree of Figure 1.9 might be used as a model for setting up a database to maintain   records about books housed in several libraries.

Figure 9.1.9 A hierarchical definition tree.

 Example  1.8 Huffman codes

 Algorithm  1.9 Constructing an Optimal Huffman Code

 Example  1.10

The algorithm beings by repeatedly replacing the smallest two frequencies with the sum until a two-element sequence is

The algorithm then constructs tree working backward beginning with two-element sequence ,  in Figure 1.13.

For example, the second tree is obtained from the frist by replacing the vertex label  by the tree of Figure 1.14.

is the sum of  and .

Finally, to obtain the optimal Huffman coding tree, we replace each frequency by a character having that frequency.

9.2  Terminology and Characterizations of Trees

Problem-Solving Corner: Trees

 Definition  2.1

An internal vertex is a vertex that has at least one child

terminal vertex is a vertex that has no children

The tree in the example has  internal vertices and  terminal vertices

 Example 2.2 (a) The parent of Eros is Aphrodite.  (b) The ancestors of Hermes are Zeus, Kronos and Uranus.  (c) The children of Zeus are Apollo, Athena, Hermes and Heracles.  (d) The descendants of Kronos are Zeus, Poseidon, Hades, Ares, Apollo, Athena,              Hermes and Heracles.  (e) Aphrodite and Prometheus are siblings.  (f) The terminal vertices are Eros, Apollo, Athena, Hermes, Heracles, Poseidon, Hades,       Ares, Atlas and Prometheus.  (g) The internal vertices are Uranus, Kronos and Zeus.  (h) The subtree rooted at Kronos is shown in Figure .

A subtree of a tree  is a tree  such that

and

A tree cannot contain a cycle.

A graph with no cycles is an acyclic graph.

 Theorem  2.3 Let  be a graph with  vertices. The following are equivalent.  (a)  is a tree.  (b)  is connected and acyclic. (“acyclic”= having no circles)  (c)  is connected and has  edges.  (d)  is acyclic and has  edges.

9.3 Spanning Trees

Finding a subgraph  of a graph  such that  is a tree containing all of the vertices of . This tree is spanning tree.

 Definition  3.1 Tree  is a spanning tree of a graph  if  is a subgraph of  that contains    all of the vertices of .

 Example  3.2 A spanning tree of the graph  of Figure 3.1 is shown in black.

 Example  3.3 In general, a graph will have several spanning trees.  Another spanning tree of the graph  of Figure 3.1 is shown in Figure 3.2.

A graph  has a spanning tree .

Let  and  be vertices of .

Since  and  are vertices in  and  in a tree, there is a path  from  to .

However  serves as a path from  to  in ; thus  is connected.

The converse is true.

 Theorem  3.4

 Example  3.5

 Algorithm  3.6 Breath-First Search for a Spanning Tree This algorithm finds a spanning tree using the breadth-first search method.      Input: A connected graph  with vertices ordered     Output: A spanning tree          vertices ordered  edges       vertices of spanning tree  edges of spanning tree        is the root of the spanning tree       is an ordered list                        while (true)            for each , in order,              for each , in order,                 if( is an edge)                    add edge  to  and  to            if (no edges were added)              return             children of  ordered consistently with the original vertex ordering

An alternative to breadth-first search is depth-first search, which proceeds to successive levels in a tree at the earliest possible opportunity.

 Algorithm  3.7 Depth-First Search for a Spanning Tree This algorithm finds a spanning tree using the depth-first search method.      Input: A connected graph  with vertices ordered     Output: A spanning tree           vertices of spanning tree  edges of spanning tree        is the root of the spanning tree                        while (true)         while(there is an edge that when added to  does not create a cycle in            choose the edge  with minimum  that when added to               does not create a cycle in            add  to            add  to                           if            return         parent of  in  // backtrack

Depth-First Search,

Idea : proceeds to successive levels in a tree at the earliest possible opportunity.

 Example  3.8 depth-first search=backtracking

 Example  3.9 Four-Queens Problem

 Algorithm  3.10 Solving the Four-Queens Problem Using Backtracking The algorithm uses backtracking to search for an arrangement of four tokens on a       grid so that no two tokens are on the same row, column or diagonal.       Input: An array row of size      Output: true, if there is a solution false, if there is no solution             [If there is a solution, the  queen is in column , ]  four-queens(row)       // start in column      // start in row      // since row is incremented prior to use, set row to      row     while        row row        // look for a legal move in column        while(rowcolumn , row conflicts)          // try next row             row row       if (row)          if              return true          else // next column                        row                     else // backtrack to previous column                             return false // no solution

The tree that Algorithm  generates is shown in Figure .

The numbering indicates the order in which the vertices are generated. The solution is found at vertex .

The queens problem is to place  tokens on a  grid so that no two tokens are on the same row, column or diagonal.

Checking that there is no solution to the two- or three -queens problem is straightforward.

Many constructions have been given to generate solutions to queens problem for all .

9.4   Minimal Spanning Trees

Given a weighted graph , a minimal spanning tree is a spanning tree of  the sum of whose weights is a minimum.

Figure 4.1 Six cities  and the costs of building roads between certain pairs of them.

 Definition  4.1 is a weighted graph. Minimal spanning tree of  is a spanning tree of  with minimum weight.

 Example  4.2

The algorithm to find a minimal spanning tree that we will discuss is known as Prim’s Algorithm.

 Algorithm  4.3 Prim’s Algorithm This algorithm finds a minimal spanning tree in a connected, weighted graph.    Input: A connected, weighted graph with vertices  and start vertex .         If  is an edge,  is equal to weight of : if  is not an edge,           is equal to (a value greater than any actual weight).   Output: The set of edges  in a minimal spanning tree (mst)        prim          //  if vertex  has been added to mst          //  if vertex  has not been added to mst 1.   for  to  2.            // add start vertex to mst 3.         // begin with an empty edge set 4.         // put  edges in the minimal spanning tree 5.   for  to           // add edge of minimum weight one vertex in mst and one vertex         // not in mst 6.       7.      for  to  8.         if  // if  is a vertex in mst 9.             for  to  10.               if  11.                   add_vertex 12.                    13.                    14.                             // put vertex and edge in mst 15.          16.          17.      18.     return  19.

 Example  4.4

Solution

The start vertex  is .

At line  we add vertex  to the minimal spanning tree.

The first time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are

 Edge Weight

The edge  with minimum weight is selected.

At line  and , vertex  is added to the minimal spanning tree and edge  is added to .

 Edge Weight

The next time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are

The edge  with minimum weight is selected.

At line  and , vertex  is added to the minimal spanning tree and edge  is added to .

 Edge Weight

The next time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are

This time two edges have minimum weight .

A minimal spanning tree will be constructed when either edge is selected.

Edge  is selected.

At line  and , vertex  is added to the minimal spanning tree and edge  is added to .

The next time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are

 Edge Weight

The edge  with minimum weight is selected. At line  and , vertex  is added to the minimal spanning tree and edge  is added to .

The last time we execute the for loop in lines , the edges with one vertex in the tree and one vertex not in the tree are

 Edge Weight

The edge  with minimum weight is selected.

At line  and , vertex  is added to the minimal spanning tree and edge  is added to . The minimal spanning tree constructed in shown in Figure 4.3.

Figure 4.4 A graph that shows that selecting an edge having minimum weight incident on the most recently added vertex does not necessarily yield a shortest path. Starting at , we obtain , but the shortest path from  to  is .

Prim’s Algorithm furnishes an example greedy algorithm.

A greedy algorithm is an algorithm that optimizes the choice at each iteration.

The principle can be summarized as “doing the best locally.” In Prim’s Algorithm, since we want a minimal spanning tree, at each iteration we simply abb an available edge with minimum weight.

 Theorem  4.5 Prim’s Algorithm (Algorithm 4.3) is correct; that is, at the termination of Algorithm     4.3,  is a minimal spanning tree.

9.5 Binary Trees

Every vertex in a binary tree has at most two children.

Each child is designed as either a left child or a right child.

When a binary tree is drawn,

a left child is drawn to the left or

a right child is drawn to the right.

 Definition  5.1 A binary tree is a rooted tree in which each vertex has either no children, one        child, or two children.  A vertex has one child, that child is designated as either a left child or a right          child(but not both).  A vertex has two children,      one child is designated a left child and      the other child is designated a right child.

 Example  5.2 In the binary tree of Figure 5.1,  Vertex  is the left child of vertex .  Vertex  is the right child of vertex .  Vertex  is the right child of vertex ; vertex  has no left child.  Vertex  is the left child of vertex ; vertex  has no right child.

Figure 5.1 A binary tree.

 Example  5.3 A tree that defines a Huffman code is a binary tree.  The Huffman coding tree of Figure 1.10,   moving from a vertex to a left child corresponds to using the bit ,   moving from a vertex to a right child corresponds to using the bit .

Figure 1.10 A Huffman code.

A full binary tree is a binary tree in which

each vertex has two children or zero children.

 Theorem  5.4

There are  internal vertices (, ,  and ) and  terminal vertices (, , ,  and ) for a total of  vertices.

 Example  5.5 Single-elimination tournament The graph of a single-elimination tournament is a full binary tree.  The contestants’ name are listed on the left.  Winner programs to the right.  Eventually, there is a single winner at root.  If the number of contestants is not a power of , some contestants receive byes.  In Figure 5.2, contestant  has a first-round bye.  There are  contestants in a single-elimination tournament, a total of  matches    are played.

Solution

The number of contestants is the same as the number of terminal vertices, and the number of matches  is the same as the number of internal vertices.

By Theorem 5.4,

so that .

Figure 5.2 The graph of a single-elimination tournament.

About binary trees relates the number of terminal vertices to the height.

 Theorem  5.6

and

Then

 Example  5.7 The binary tree in Figure 5.3 has height  and the number of terminals .  For this tree, the inequality  becomes an equality.

Figure 5.3 A binary tree of heigh  with  terminals. For this binary tree, .

If all  terminal vertices of a full binary tree  have the same level heigh of , then

.

Binary Search Trees

If data item  is stored in vertex  and data item  is stored in vertex , then if  is a left child(or right child) of , some ordering relationship will be guaranteed to exist between  and . This is binary search tree.

 Definition  5.8 A binary search tree is a binary tree  in which data are associated with the      vertices. The data are arranged so that, for each vertex  in , each data item in the   left subtree of is less than the data item in , and each data item in the right        subtree of  is greater than the data item in .

Alphabetical Order

Alphabetical or lexicographic order is the order of the dictionary:

a) start with an ordered set of symbols  can be infinite or finite.

b) Let  and  be strings over .

Then define  if

or if  for all ,

for some  such that  and

or if  and  for all .

Example of Alphabetical Order

Let  set of letters of the alphabet ordered according to precedence, i.e.

Let  and .

In this case,

.

So we go the fourth letter:  and .

Since  we have that .

 Example  5.9 The words                        OLD  PROGRAMMERS  NEVER  DIE THEY  JUST  LOSE  THEIR  MEMORIES  may be placed in a binary search tree as shown in Figure 5.4.  Notice that for any vertex ,    each data item in the left subtree of  is less than the data item in  and    each data item in the right subtree of  is greater than the data item in .

Figure  5.4 A binary search tree.

OLD PROGRAMMERS NEVER DIE THEY JUST LOSE THEIR MEMORIES

 Algorithm  5.10 Constructing a Binary Search Tree This algorithm constants a binary search tree. The input is read in the order           submitted. After each words is read, it is inserted into the tree.   Input: A sequence  of distinct words and the length  of the sequence  Output: A binary search tree     make_bin_search_tree        let  be the tree with one vertex, root       store  in root       for  to            root          search  true // find spot for           while(search)              word in               if                  if( has no left child)                   add a left child  to                    store  in                    search  false // end search                                 else                    left child of               else //                  if( has no right child)                   add a right child  to                    store  in                    search  false // end search                                 else                    right child of          // end while      // end for       return

9.6   Tree Traversals

Breadth-first search and depth-first search provide ways to “walk” a tree, that is, to traverse a tree in a systematic way so that vertex is visited exactly once. In this section we consider three additional tree-traversal methods.

 Algorithm  6.1 Preorder Traversal This recursive algorithm processes the vertices of a binary tree using preorder          traversal.        Input: PT, the root of a binary tree, or the special value null to indicate than no                 trees is input        Output: Dependent on how “process” is interpreted in line      preorder(PT)   1.       if   2.          return  3.       process PT  4.        left child of PT  5.       preorder()  6.        right child of PT  7.       preorder()

The input consists of a tree with a single vertex.

We set  to the root and call preorder().

Since  is not equal to null, we proceed to line , where we process the root.

At line , we call preorder with  equal to null since there is no left child.

We just saw that when no tree is input to preorder, thing is processed.

At line , when no tree is input to preorder, again nothing is processed.

Thus when the input consists of a tree with a single vertex, we process the root and return.

The input is the tree of Figure 6.1.

We set  to the root and call preorder().

Since  is not equal to null, we proceed to line , where are process the root.

At line  we call preorder with  equal to the left child of the root.

The tree input to preorder consists of a single vertex, preorder processes that vertex.

We next process vertex .

At line , we process vertex .

The vertices are processed in order .

 Example  6.2 In what order are the vertices of the tree of Figure 6.3 processed if preorder traversal   is used?

Solution

Following lines (root/left/right) of Algorithm 6.1, the traversal proceeds as shown in Figure 6.4. Thus the order of processing is .

Inorder traversal and postorder traversal are obtained by channing the position of line  (root) in Algorithm 6.1. “Pre,” “in” and “post” refer to the position of the root in the traversal; that is “preorder” means root first, “inorder” means root second and “postorder” means root last.

 Algorithm  6.3 Inorder Traversal This recursive algorithm processes the vertices of a binary tree using inorder traversal.   Input: PT, the root of a binary tree, or the special value null to indicate than no                 trees is input        Output: Dependent on how “process” is interpreted in line       inorder(PT)   1.       if   2.          return  3.        left child of PT  4.       inorder()  5.       process PT  6.        right child of PT  7.       inorder()

 Example  6.4 In what order are the vertices of the binary tree of Figure 6.3 processed if inorder      traversal is used?

Solution

Following lines (left/root/right) of Algorithm 6.3, we obtain the inorder listing

 Algorithm  6.5 Postorder Traversal This recursive algorithm processes the vertices of a binary tree using postorder traversal.   Input: PT, the root of a binary tree, or the special value null to indicate than no                 trees is input        Output: Dependent on how “process” is interpreted in line       postorder(PT)   1.       if   2.          return  3.        left child of PT  4.       postorder()  5.        right child of PT  6.       postorder()  7.       process PT

Preorder traversal                     Inorder traversal

Root-Left-Right                          Left-Root-Right

Postorder traversal

Left-Right-Root

 Example  6.6 In what order are the vertices of the binary tree of Figure 6.3 processed if postorder    traversal is used?

Solution

Following lines (left/root/right) of Algorithm 6.5, we obtain the postorder listing .

Figure 6.5 Preorder traversal.           Figure 6.6 Reverse postorder traversal.

Figure 6.7 The binary tree representation of the expression

The variables  and  are referred to as operands.

The operators , * and  operate on pairs of operands or expression.

infix form of an expression

fully parenthesized form of the express

postfix from of the expression(or reverse Polish notation)  *

prefix from of the expression(or Polish notation)  *

9.7   Decision Trees and the Minimum Time for Sorting

Decision Tree

 Definition A binary tree containing an algorithm to decide which course of action to take. Use   to specify algorithms   to obtain lower bounds on the worst-case time for sorting

 Example  7.1 Five-Coins Puzzle Five coins are identical in appearance, but one coin is either heavier or lighter than the    others, which all weigh the same. The problem is  to identify the bad coin and  determine whether it is heavier or lighter than the others  using only a pan balance, which compares the weights of two sets of coins.

Solution

An algorithm to solve the puzzle is given Figure  as a decision tree.

The coins are labeled .

As shown, we begin at the root place coin  in the left pan and coin  in the right pan.  At edge labeled  means that left side of the pan balance is heavier than the right side.

Edge labeled means that right side of the pan balance is heavier than the left side.

Edge labeled  means that the two side balance.

For example , at the root when we compare  with ,

if the left side is heavier than the right side,

we know that either  is the heavy coin or   is the light coin.

In this case, as shown in the decision tree, we next compare  with (which is known to be a good coin) and immediately determine whether the bad coin is  or  and whether it is heavy or light.

The terminal vertices give the solution.

For example, when we compare  with  and the pans balance, we follow the edge to the terminal vertex labeled . The bad coin is .

The coin  is light than the others coin.

Figure 9.7.2 A pan balance for comparing weights of coins.

Figure 9.7.3 An algorithm to solve the five-coins puzzle.

The five-coins puzzle has  outcomes:

,,          ,,          ,,          ,,          ,,

,,          ,,          ,,          ,,          ,.

Figure 9.7.4 A five-coins puzzle algorithm that uses at most two weightings.

Figure 9.7.5 A four-coins puzzle algorithm that begins by comparing two coins against two coins.

Figure 9.7.6 A four-coins puzzle algorithm that begins by comparing one coin against one coin.

The sorting problem is easily described: Given  items

,

arrange them in nondecreasing(or nonincreasin) order. We  restrict our attention to sorting algorithms that repeatedly compare two elements and based on the result of the comparison, modify the original list.

An algorithm to sort  is given by the decision tree of Figure . Each edge is labeled with the arrangement of the list based on the answer to the question at an internal vertex. The terminal vertices give the sorted order.

Let us define the worst-case time to sort to be the number of comparisons in the worst case. The height of a decision tree that solves a sorting problem is equal to the worst-case time.

But the problem of sorting three items has six possible outcomes(when the items are distinct), corresponding to the  ways that three items can be arranged:

,,,        ,,,        ,,,        ,,,        ,,,        ,,.

This is a contradiction. Therefore, no algorithm that sorts three items has worst-case time less than , and the algorithm of Figure  is optimal.

Figure 9.7.7 An algorithm to sort

Figure 9.7.8 A sorting algorithm that makes at most two comparisons.

Since , there are  possible outcomes to the problem of sorting four items(when the items are distinct). To accommodate  terminal vertices, we must have a tree of height at least (see Figure ). Therefore, any algorithm that sorts four items requires at least five comparisons in the worst case.

 Level Number of Vertices

Figure 9.7.9 Level compared with the maximum number of vertices in that level in a binary tree.

Figure 9.7.9 Level compared with the maximum number of vertices in that level in a binary tree.

 Theorem  7.3 If  is the number of comparisons needed to sort  items in the worst case by a    sorting algorithm, then .

Proof

is the decision tree that represents the algorithm for input of size .

denoted the height of .

Then the algorithm requires  comparisons in the worst case, so

(7.1)                                  .

The tree  has at least  terminal vertices, so by Theorem ,

(7.2)                                  .

Shows that ; for some positive constant ,

(7.3)

for all but finitely many integer .

Combining (7.1) through (7.3), we obtain

for all but finitely many integer .

Therefore

9.8   Isomorphisms of Trees

The simple graphs  and  are isomorphic if and only if there is a one-to-one, onto function  from the vertex set of  to the vertex set of  that preserves the adjacency relation in the sense that vertices  and  are adjacent to  if and only if the vertices   and  are adjacent in .

Since a tree is a simple graph, tree  and  are isomorphic if and only if there is a one-to-one, onto function  from the vertex set of  to the vertex set of  that preserves the adjacency relation; that is, vertices  and  are adjacent to  if and only if the vertices   and  are adjacent in .

 Example  8.1

That two trees are not isomorphic if we can exhibit an invariant that the trees do not share.

 Example  8.2

 Theorem  8.3 There are three nonisomorphic trees with five vertices.

Proof

For two rooted trees  and  are isomorphic, there is a one-to-one, onto function  from  to that preserves the adjacency relation and that preserves the root. The latter condition means that

 Definition  8.4

 Example  8.5

 Example  8.6

 Theorem  8.7 There are four nonisomorphic rooted trees with four vertices. These four rooted trees    are shown in Figure 8.9.

(a)                (b)              (c)            (d)

Figure 8.9 The four nonisomorphic rooted trees with four vertices.

 Definition  8.8

 Example  8.9

 Example  8.10

The trees  and  of Figure 8.11 are isomorphic as rooted trees and as free trees.

As rooted trees, either of the trees of Figure 8.11 is isomorphic to the rooted tree  of Figure 8.9(c).

 Theorem  8.11 There are five nonisomorphic binary trees with three vertices.  These five binary trees are shown in Figure .

(a)                (b)              (c)             (d)               (e)

Figure 8.12 The five nonisomorphic binary trees with three vertices.

If  is a set of trees of a particular type( is a set of free trees or  is a set of rooted trees or  is a set of binary trees) and we define a relation  on  by the rule  if  and  are isomorphic,  is an equivalence relation. Each equivalence class consists of a set of mutually isomorphic trees.

 Theorem  8.12 There are  nonisomorphic binary trees with  vertices where    is the  Catalan number.

Figure 8.13 The two nonisomorphic binary trees with two vertices.

and  is nonemptyset, after which we check that left subtrees of  and  are isomorphic and that the right subtrees of  and  are isomorphic.

 Algorithm  8.13 Testing Whether Two Binary Trees Are Isomorphic Input: The roots  and  of two binary trees.             (If the first tree is empty,  has the special value null.             If the second tree is empty,  has the special value null.)     Output: true, if the trees are isomorphic             false, if the trees are not isomorphic         bin_tree_isom   1.           if  2.             return true         // now one or both of  or  is not null  3.           if  4.             return false         // now neither of  or  is null  5.       left child of   6.       left child of   7.       right child of   8.       right child of   9.      return bin_tree_isom

 Theorem  8.14 The worst-case time of Algorithm 8.13 is , where  is the total number of       vertices in the two trees.

Exercises

(이 강의록은 성균관대 김응기 박사님, 이영수 박사님, 김장수 교수님 등의 기존 강의록과 교재 및 참고자료를 바탕으로 이상구 교수가 새로 만든 2018년 1학기 용 강의록입니다.)

(강의록에 실습실을 추가하여 이론과 실습을 같이 할 수 있는 새로운 수학 강의 의 모델입니다)

http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm

*** References   (Calculus)

< Calculus 미적분학 1, 2 >

http://matrix.skku.ac.kr/Cal-Book/

(Lecture Movie 동영상 강의) SKKU 성균관대

- Calculus with Sage Lectures (Youtube 동영상 강의)

<미적분학 동영상 강의이상구 교수성균관대

- Calculus with Sage Lectures (Youtube 동영상 강의)

1.1 History of Calculus : http://youtu.be/ODfMaHgIhAc

Calculus with Sage Week 1

how to manage our class Review : http://youtu.be/XWEQFlv4jKc

Chapter 1. Functions

http://youtu.be/cl8GqIWIRD0 (동영상 강의)

1.1 Functions and its graph

1.2 Symmetry (문제 풀이)

1.3 Common Functions

1.4 Translation, Stretching and Rotation of Functions

1.5 A Few Basic Concepts

Chapter 2. Limits and Continuity

2.1 Limits of functions : http://youtu.be/VBCeAllP1M0 (동영상 강의)

2.2 Continuity : http://youtu.be/zGxx3PUCTnM (동영상 강의)

Chapter 3. Theory of Differentiation

3.1 Definition of Derivatives, Differentiation : http://youtu.be/A-vDsF9ulTs (동영상 강의)

3.2 Derivatives of Polynomials, Exponential Functions, Trigonometric Functions, The product rule: http://youtu.be/XXMnCESesfQ

3.3 The Chain Rule and Inverse Functions : http://youtu.be/HfScHEsPfKI

3.4 Approximation and Related Rates : http://youtu.be/ViRwEJ0Wfkw

Chapter 4. Applications of Differentiation

4.1 Extreme values of a function : http://youtu.be/mXVU8OqIHJY (동영상 강의)

4.2 The Shape of a Graph : http://youtu.be/cZrAF_77On4

4.3 The Limit of Indeterminate Forms and L’Hospital’s Rule :

http://youtu.be/vp-gck5-gKE

4.4 Optimization Problems : http://youtu.be/k0NtkmZFnh8

4.5 Newton’s Method : http://youtu.be/VxCfl2JzMYU

Chapter 5. Integrals

5.1 Areas and Distances : http://youtu.be/mT_oxlD6RSA (동영상 강의)

5.2 The Definite Integral : http://youtu.be/GIm3Oz58Ti8

5.3 The Fundamental Theorem of Calculus : http://youtu.be/Zf1HT2H2fbA

5.4 Indefinite Integrals and the Net Change Theorem : http://youtu.be/E6I3EDzAVuU

5.5 The Substitution Rule : http://youtu.be/h7tmvmNOliU

5.6 The Logarithm Defined as an Integral : http://youtu.be/kD0Z9PqetsA

Midterm Exam : 4월 24일 수요일 4시에 강의실

미적분학 with Sage Midterm Exam, http://youtu.be/QAEI7A2DMMM

Chapter 6. Applications of Integration

미적분학 with Sage Sec-6-1 Areas between Curves, http://youtu.be/o53phm5cqJE

미적분학 with Sage Sec-6-2 Volumes, http://youtu.be/4-ChOAFbJAs

미적분학 with Sage Sec-6-3 Volumes by Cylindrical Shells,

http://youtu.be/qM1izf8qeX8 (동영상 강의)

미적분학 with Sage Sec-6-4 Work : http://youtu.be/u3ZaJWhKy6k

미적분학 with Sage Sec-6-5 Average Value of a Function

http://youtu.be/zmEeGmwQTB0

Chapter 7. Techniques of Integration

미적분학 with Sage Sec-7-1 Integration by Parts http://youtu.be/WX-6C9tCneE

미적분학 with Sage Sec-7-2 Trigonometric Integrals http://youtu.be/sIR0zNGQbus

미적분학 with Sage Sec-7-3 Trigonometric Substitution http://youtu.be/avTqiEUi8u8

미적분학 with Sage Sec-7-4 Integration of Rational Functions by the Method of Partial Fractions http://youtu.be/KLTHp_7G4cI

미적분학 with Sage Sec-7-5 Guidelines for Integration http://youtu.be/Fgn8U4We60o

미적분학 with Sage Sec-7-6 Integration Using Tables http://youtu.be/tn9jLkgTMp8

미적분학 with Sage Sec-7-7 Approximate Integration http://youtu.be/hg2pw1n1cZI

미적분학 with Sage Sec-7-8 Improper Integrals http://youtu.be/rquxbYrC0Yc

Chapter 8. Further Applications of Integration

미적분학 with Sage Sec-8-1 Arc Length http://youtu.be/7OVqI20z_Bw

미적분학 with Sage Sec-8-2 Area of a Surface of Revolution

http://youtu.be/Eq4i2A8eKxA

미적분학 with Sage Sec-8-3 Applications of Integral Calculus

http://youtu.be/1ZAJeP16pAQ

*미적분학 with Sage Sec-8-4 Differential equations http://youtu.be/uHfOjz8I4-s

Chapter 9. Parametric Equations and Polar Coordinates

9.1 Parametric Equations

9.2 Calculus with Parametric Curves

9.3 Polar Coordinates

9.4 Areas and Lengths in Polar Coordinates

9.5 Conic Section

Chapter 10. Infinite Sequences and Infinite Series

10.1 Sequences and Series

10.2 Tests for convergence of series with positive terms

10.3 Alternating Series and Absolute Convergence

10.4 Power Series

강의에 앞서 http://youtu.be/YtxYZW3Enko (동영상 강의)

Chapter 11. Vectors and the Geometry of Space

11.1 Three-Dimensional Coordinate Systems

11.2 Vectors

11.3 The Dot Product

11.4 The Vector or Cross Product

11.5 Equations of Lines and Planes

Chapter 12. Vector Valued Functions

12.1 Vector-Valued Functions and Space Curves http://youtu.be/0pvywjBjsQw

12.2 Calculus of Vector Functions

12.3 Arc Length and Curvature

*12.4 Motion Along A Space Curve: Velocity and Acceleration

Chapter 13. Partial Derivatives

13.1 Multivariate Functions

13.2 Limits and Continuity of Multivariate Functions

13.3 Partial Derivatives http://youtu.be/LR89Ct3cEDY (동영상 강의)

13.4 Differentiability and Total Differentials

13.5 The Chain Rule http://youtu.be/r3dGYL1vkEU

13.6 Directional Derivatives and Gradient http://youtu.be/o8L_ShRANjo

13.7 Tangent Plane and Differentiability http://youtu.be/uOf-5YHKGI4

13.8 Extrema of Multivariate Functions http://youtu.be/oDZUkOEszOQ

13.9 Lagrange Multiplier

Chapter 14. Multiple Integrals

14장 앞부분 복습 내용http://youtu.be/5eCO2GjlJHs (동영상 강의)

Chapter 14. Multiple Integrals

14.1 Double Integrals http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-1-Sol.html

14.2 Double Integrals in Polar Coordinates

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-2-Sol.html

14.3 Surface Area http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-3-Sol.html

14.4 Cylindrical Coordinates and Spherical Coordinates http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-4-Sol.html

14.5 Triple Integrals

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-5-Sol.html

14.6 Triple Integrals in Cylindrical and Spherical Coordinates

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-6-Sol.html

14.7 Change of Variables in Multiple Integrals

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-14-7-Sol.html

14.1 Double Integrals http://youtu.be/jZ2pAmPZYOE (동영상 강의)

14.2 Double Integrals in Polar Coordinates http://youtu.be/olQgihl5aZg

14.3 Surface Area http://youtu.be/p9R0TTLfBzk

14.4 Cylindrical and Spherical Coordinates http://youtu.be/q3FKd2UxV_I

14.5 Triple Integrals http://youtu.be/r1tzH9Ibbqk

14.6 Triple Integrals in Cylindrical &Spherical Co http://youtu.be/xd0U4_C2ePY

14.7 Change of Variables in Multiple Integrals http://youtu.be/INn-bkgXYNg

Chapter 15. Vector Calculus

Chapter 15. Vector Calculus

15.1 Vector Differentiation

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-1-Sol.html

15.2 Line Integrals http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-2-Sol.html

15.3 Independence of the Path

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-3-Sol.html

15.4 Green’s Theorem in Plane

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-4-Sol.html

15.5 Curl and Divergence

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-5-Sol.html

15.6 Surface and Area

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-6-Sol.html

15.7 Surface Integrals

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-7-Sol.html

15.8 Stokes’ Theorem

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-8-Sol.html

15.9 Divergence Theorem

http://matrix.skku.ac.kr/Cal-Book/part2/CS-Sec-15-9-Sol.html

15.1 Vector Differentiation http://youtu.be/q0aVmUCXgTI (동영상 강의)

15.2 Line Integrals http://youtu.be/wHINlpNXYaU

15.3 Independence of the Path http://youtu.be/jGGOL3QDj1Y

15.4 Green’s Theorem in Plane http://youtu.be/WxdTbaSb_ZI

15.5 Curl and Divergence http://youtu.be/IswmJUCTeNA

15.6 Surface and Area http://youtu.be/xX6tNVpegbs

15.7 Surface Integrals http://youtu.be/nrzIrM4doLo

15.8 Stokes’ Theorem http://youtu.be/t4skc_PzJvg

15.9 Divergence Theorem http://youtu.be/3BmcFr81kuQ

(SKKU 선형대수학 Jordan 표준형, SGLee : http://youtu.be/Dn4qBxgUJcA )

**************************************************

<Calclus 미적분학 1, 2>

http://matrix.skku.ac.kr/Cal-Book/

(동영상) <성균관대 학생 문제 풀이 설명 (by Students)>

Chapter 1. Functions

미적분학 with Sage Sec-1-1 Functions and Graph, Problem, 문제풀이 by 황인철 http://youtu.be/rQ2CB8EvkoE

미적분학 with Sage Sec-1-2 Symmetry, Problem, 문제풀이 by 곽주현 http://youtu.be/BNKUzSohiD8

미적분학 with Sage Sec-1-3 Common Functions, Problem, 문제풀이 by 장찬영 http://youtu.be/x0E0ZMxZ3Og

미적분학 with Sage Sec-1-4 Translation, Stretching and Rotation of Functions, Problem, 문제풀이 by 임효정 http://youtu.be/vx7GCWY68Zw

Chapter 2. Limits and Continuity

미적분학 with Sage Sec-2-1 Limits of functions, Problem, 문제풀이 by 장재철-이훈정 http://youtu.be/LZSmRPAAXME

미적분학 with Sage Sec-2-2 Continuity, Problem, 문제풀이 by 이훈정 http://youtu.be/azrkT1RP4-c

미적분학 with Sage Sec-2-2 Continuity, Epsilon-Delta Proof, by 황인철 http://youtu.be/hj8d-j_DGf4

Chapter 3. Theory of Differentiation

미적분학 with Sage Sec-3-1 Definition of Derivatives, Differentiation, Problem, 문제풀이 by 김태현 http://youtu.be/7wTBWuk2CzU

미적분학 with Sage Sec-3-2 Derivatives of Polynomials, Exponential Functions, Trigonometric, Problem, 문제풀이 by 조건우 http://youtu.be/Ei5KGW9vZhE

미적분학 with Sage Sec-3-3 The Chain Rule and Inverse Functions, Problem, 문제풀이 by 유휘의 http://youtu.be/aSKm12922FE

미적분학 with Sage Sec-3-4 Approximation and Related Rates, Problem, 문제풀이 김종민 http://youtu.be/JmBOv6_D6qA

Chapter 4. Applications of Differentiation

미적분학 with Sage Sec-4-1 Extreme values of a function, Problem, 문제풀이 by 김태영 http://youtu.be/_V4MryNEzWY

미적분학 with Sage Sec-4-2 The Shape of a Graph, Problem, 문제풀이 by 김태영 http://youtu.be/SVOWADHlzV8

미적분학 with Sage Sec-4-3 Indeterminate Forms and L'Hospital's Rule, Problem, 문제풀이 by 신종희 http://youtu.be/gR2luDDPsMY

미적분학 with Sage Sec-4-4 Optimization, Problem, 문제풀이 by 이승철 http://youtu.be/AELEV2ElaeQ

미적분학 with Sage Sec-4-5 Newton's Method, Problem, 문제풀이 by 이승철http://youtu.be/fdBHQ46g9RE

Chapter 5. Integrals

미적분학 with Sage Sec-5-1 Area and Distance, Problem, 문제풀이 by 남택현 http://youtu.be/Y_nCn76RPmY

미적분학 with Sage Sec-5-2 Definite Integral, Problem, 문제풀이 by 남택현http://youtu.be/iUsf1h_hTAE

미적분학 with Sage Sec-5-3 and 5-4 Fun Theorem of Calculus Net Change Theorem, Problem, 문제풀이 by 정승찬 & Kim http://youtu.be/Pa4Z38KkDVY

(미적분학 with Sage Sec-5-4 Net Change Theorem, Problem, 문제풀이 by Kim *** )

미적분학 with Sage Sec-5-5 Substitution, Problem, 문제풀이 by 이한울 http://youtu.be/0TMbpCPO4Uc

미적분학 with Sage Sec-5-6 Log and Exponential, Problem, 문제풀이 by 이한울 http://youtu.be/ymDImdIQ90c

Chapter 6. Applications of Integration

미적분학 with Sage Sec-6-2 Volumes, 문제풀이 by 김종민 http://youtu.be/Fd4Mguf2dbU

미적분학 with Sage Sec-6-3 Volumes by Cylindrical Shells, Problem, 문제풀이 by 신영찬 http://youtu.be/gNaKkA0UNHg

미적분학 with Sage Sec-6-4 Work, Problem, 문제풀이 by 김건호 http://youtu.be/SmIo2yaxNsY

미적분학 with Sage Sec-6-5 Average Value of a Function, Problem, 문제풀이 by 신종희 http://youtu.be/BVahd-DJoe8

Chapter 7. Techniques of Integration

미적분학 with Sage Sec-7-1 Integration by Parts, 문제풀이 by 이인행 http://youtu.be/jKCAGJ4HqvQ

미적분학 with Sage Sec-7-2 Trigonometric Integrals, 문제풀이 by 김태현 http://youtu.be/ytETYf1wLbs

미적분학 with Sage Sec-7-3 Trigonometric Substitution, Problem, 문제풀이 by 이훈정 http://youtu.be/utTQHIabTyI

미적분학 with Sage Sec-7-4 Integration of Rational Functions by the Method of Partial Fractions, Problem, 문제풀이 by 장재철 http://youtu.be/SkNW_bax0YI

미적분학 with Sage Sec-7-5 Guidelines for Integration, Problem, 문제풀이 by 김대환 http://youtu.be/-N9Fe_Arp2c

미적분학 with Sage Sec-7-6 Integration Using Tables, Problem, 문제풀이 by 조건우 http://youtu.be/EnEQ9ZS3B_k

미적분학 with Sage Sec-7-8 Improper Integrals, Problem, 문제풀이 by 이인행 http://youtu.be/dfSkjvmSXYo

Chapter 8. Further Applications of Integration

미적분학 with Sage Sec-8-1 Arc Length, 문제풀이 by 남택현 http://youtu.be/A8N-mDD0ja8

미적분학 with Sage Sec-8-2 Area of a Surface of Revolution, 문제풀이 by 정승찬 http://youtu.be/yZFJDJgTJfw

(미적분학 with Sage Sec-8.3 Center of Mass

(미적분학 with Sage Sec-8.4 Differential equations

Chapter 9. Infinite Sequences and Infinite Series

미적분학 with Sage Sec-9-1 Sequences and Series, 문제풀이 by 이원준 http://youtu.be/O6y1v5fJA0k

미적분학 with Sage Sec-9-2 Tests for convergence of series with positive terms, 문제풀이 by 김범윤 http://youtu.be/1flKAnlv9LA

미적분학 with Sage Sec-9.3 Alternating Series and Absolute Convergence ?

(미적분학 with Sage Sec-9.4 Power Series ?

(미적분학 with Sage Sec-9.5 Taylor, Maclaurin, and Binomial Series ?

Chapter 10. Parametric Equations and Polar Coordinates

미적분학 with Sage Sec-10-1 Parametric Equations, 문제풀이 by 임효정 http://youtu.be/Ybs68e0iMZI

미적분학 with Sage Sec-10-2 Calculus with Parametric Curves, 문제풀이 by 장찬영 http://youtu.be/yF5oZOQVnCE

미적분학 with Sage Sec-10-3 Polar Coordinates, Problem, 문제풀이 by 황인철 http://youtu.be/4hoVKvk8dq0

미적분학 with Sage Sec-10-4 Areas and Lengths in Polar Coordinates, Problem, 문제풀이 by 곽주현 http://youtu.be/LRmasW9uqYY

미적분학 with Sage Sec-10-5 Conic Section, Problem, 문제풀이 by 이한울 http://youtu.be/CZ9SHMtqVy4

Chapter 11. Vectors and the Geometry of Space

미적분학 with Sage Sec-11.1 Three-Dimensional Coordinate Systems, 문제풀이 by 김태현 http://youtu.be/_s_2T1VVob8

미적분학 with Sage Sec-11.2 Vectors, 문제풀이 by 오교혁 http://youtu.be/BFgh6irMqsc

(미적분학 with Sage Sec-11.3 The Dot Product ?

(미적분학 with Sage Sec-11.4 The Vector or Cross Product ?

미적분학 with Sage Sec-11.5 Equations of Lines and Planes, 문제풀이 by 구본우 http://youtu.be/lxuGE_Erthg

(미적분학 with Sage Sec-11.6 Cylinders and Quadric Surfaces ?

Chapter 12. Vector Valued Functions

미적분학 with Sage Sec-12.1 Vector-Valued Functions and Space Curves, 문제풀이 by 최양현 http://youtu.be/jvMI6OzdR_I

미적분학 with Sage Sec-12.2 Calculus of Vector Functions , 문제풀이 by 김동윤 http://youtu.be/VS5rPyOjP2I

(미적분학 with Sage Sec-12.3 Arc Length and Curvature ?

(미적분학 with Sage Sec-12.4 Motion Along A Space Curve: Velocity and Acceleration ?

Chapter 13. Partial Derivatives

미적분학 with Sage Sec-13.1 Multivariate Functions, 문제풀이 by 구본우 http://youtu.be/As_0AYApHlM

(미적분학 with Sage Sec-13.2 Limits and Continuity of Multivariate Functions, 문제풀이 by 김건호?

(미적분학 with Sage Sec-13.3 Partial Derivatives, 문제풀이 by 김동윤?

미적분학 with Sage Sec-13.4 Differentiability and Total Differentials, 문제풀이 by 김범윤 http://youtu.be/qDmCWBiXbIA

미적분학 with Sage Sec-13.5 The Chain Rule, 문제풀이 by 김유경 http://youtu.be/vzN5By6qzvM

미적분학 with Sage Sec-13.6 Directional Derivatives and Gradient, 문제풀이 by 김태현 http://youtu.be/2_7TOUuzJoE

미적분학 with Sage Sec-13.7 Tangent Plane and Differentiability, 문제풀이 by 서용태 http://youtu.be/GDkE8OqUvsk

미적분학 with Sage Sec-13.8 Extrema of Multivariate Functions, 문제풀이 by 오교혁 http://youtu.be/FWmk_MasIjE

미적분학 with Sage Sec- 13.9 Lagrange Multiplier, 문제풀이 by 이원준 http://youtu.be/YMGdQWBzyrI

Chapter 14. Multiple Integrals

미적분학 with Sage Sec-14.1 Double Integrals, 문제풀이 by 이인행 http://youtu.be/w8g9fgcEP4A

미적분학 with Sage Sec-14.2 Double Integrals in Polar Coordinates, 문제풀이 by 이지석 http://youtu.be/jpsObxtZ50A

(미적분학 with Sage Sec-14.3 Surface Area, 문제풀이 by 이한울?

(미적분학 with Sage Sec-14.4 Cylindrical Coordinates and Spherical Coordinates, 문제풀이 by 최양현?

미적분학 with Sage Sec-14.5 Triple Integrals, 문제풀이 by 이인행 http://youtu.be/Voq67ooqQJs

(미적분학 with Sage Sec-14.6 Triple Integrals in Cylindrical and Spherical Coordinates, 문제풀이 by 구본우?

(미적분학 with Sage Sec-14.7 Change of Variables in Multiple Integrals, 문제풀이 by 김건호 최양현?

Chapter 15. Vector Calculus

(미적분학 with Sage Sec-15.1 Vector Differentiation, 문제풀이 by 김동윤?

미적분학 with Sage Sec-15.2 Line Integrals, 문제풀이 by 김범윤 http://youtu.be/ZdRjCfJeHM8

미적분학 with Sage Sec-15.3 Independence of the Path, 문제풀이 by 김유경 http://youtu.be/TreCe8ESEiU

(미적분학 with Sage Sec-15.4 Green’s Theorem in Plane, 문제풀이 by 김태현?

미적분학 with Sage Sec-15.5 Curl and Divergence, 문제풀이 by 서용태 http://youtu.be/wLTHYaANwtI

미적분학 with Sage Sec-15.6 Surface and Area, 문제풀이 by 오교혁 http://youtu.be/j7F3xVNdHvA

미적분학 with Sage Sec-15.7 Surface Integrals, 문제풀이 by 이원준 http://youtu.be/s_MRgW2By38

(미적분학 with Sage Sec-15.8 Stokes’ Theorem, 문제풀이 by 이인행?

미적분학 with Sage Sec-15.9 Divergence Theorem, 문제풀이 by 최주영 http://youtu.be/vGMLoGWF1Is