A / B / \ I C / D \ E / \ G F / / H J \ K
Inductive Step: Assume that any tree with k nodes has
k-1 edges, for k <= n.
Show Also true for k = n+1:
If we add a node to a tree of n nodes, we either add it as the root,
as a leaf or add it between two existing nodes. In the first two
cases, we need exactly one edge to connect it to the rest of the tree
(connecting the leaf to its parent, or the root to its child, the old
root). In these cases the number of edges is (n-1)+1 = n, which is
(n+1)-1. If we add the node between two other nodes, then we add two
edges, one connecting the node to its parent, and one connecting to
its child. But we also removed one edges, that was originally
connecting the parent to the child, before we added the new node. Thus
the number of edges is (n-1)+2-1= n. In either case when we add a node
to get N+1 nodes, we have n edges, and so the property holds.
Since it holds inductively, it holds for all values of n >+1.
Component Edges | Component Nodes | Unconnected Nodes |
---|---|---|
A | B C D E F | |
(A B) | A B | C D E F |
(A B) (B D) | A B D | C E F |
(A B) (B D) (C D) | A B C D | E F |
(A B) (B D) (C D) (D F) | A B C D F | E |
(A B) (B D) (C D) (D F) (E F) | A B C D E F |
Inductive Step: Assume that any graph with k nodes and
< k-1 edges, is unconnected for k <= n.
Show Also true for k = n+1:Since the graph with k
nodes and k-2 edges is unconnected that means it contains at least 2
unconnected components. If we add a node then it has 3 unconnected
components. Now we can only add at most one more edge to keep below
(K+1)-1 edges total. Each edge can connect (at most) two
components. But if we start with three, we will still have at least
two after adding the edge. Thus this property is true for graphs with
k+1 nodes, and thus, by induction, for all graphs with n>=2 nodes.
1 #1 2 2 #3 3 3 #5 4 4 #6 0 5 #2 6 6 #4 0 7 #1 8 8 #2 9 9 #3 10 10 #4 3Cells 1-4 are created by the first list call, and bound to list1 when mystery is called. Cells 5-6 are created by the second list call, and bound to list2 inside of mystery. Inside of mystery, cells 7-8 are created by the outer call, and 9-10 by the recursive call. When the outer call finishes, it reutns cell 7, which is what setq binds X to.
1000,500,400,200,800 Allocate 500 500,500,400,200,800 Allocate 600 500,500,400,200,200 Allocate 500 500,400,200,200 Allocate 400 100,400,200,200
1000,500,400,200,800 Allocate 500 1000,400,200,800 Allocate 600 1000,400,200,200 Allocate 500 500,400,200,200 Allocate 400 500,200,200
Unsorted Sorted Start: 1 12 3 8 4 9 Pass 1: 12 3 8 4 9 1 Pass 2: 3 8 4 9 1 12 Pass 3: 8 4 9 1 3 12
9 / \ 8 6 / \ / \ 7 5 4 2 / \ 1 3
(defun mergesort (unsorted) (cond ((null unsorted) unsorted) ;empty list is sorted ((null (cdr unsorted) unsorted)) ; list with one elt is sorted (t (mergelists (mergesort (firsthalf unsorted)) (mergesort (secondhalf unsorted)))))) (defun mergelists (list1 list2) (cond ((null list1) list2) ((null list2) list1) ((< (car list1) (car list2)) ;> (cons (car list1) (mergelists (cdr list1) list2))) (t (cons (car list2) (mergelists list1 (cdr list2))))))
A / / \ \ / / \ / | \ E C B /| | \ / | | \ F G D