• A graph G=(V,E) is said to be connected iff for every pair of vertices u and v Î V, there is a path from u to v.

• A digraph G =(V,E) is said to be strongly connected iff for every pair of vertices u and v Î V, there is a path from u to v and also a path from v to u.

• Connected component :
  A maximal connected subgraph of G is called a connected component of G.

• A graph with no cycles is called an acyclic graph .

• Topological sort
  • reference
  • MST and Topological sorting

• Graph search (traversal)

  Problem: Given a directed graph and a starting node u, follow arcs of the graph to visit each node exactly once
  (Note: if we allowed nodes to be revisited, search procedure may not terminate)
  The set of arcs that are followed has no cycle (since nodes never revisited) -- so it forms a search tree
  To avoid cycles, we can mark nodes as we visit them and never revisit marked nodes
  Which arcs to visit, and in what order?

  • Breadth-first search: First, visit all of u's successors by following arcs from u; next, visit all successors of u's successors by following arcs from u's successors; and so on.  (We visit the nodes near u as early as possible.)
  • Depth-first search: Starting at u, visit successors recursively.  (We visit nodes far from u as early as possible.)
  Depth-first search -- recursive version

  DFS(G,v):

  • Mark v "visited";
  • For every arc (v,w):
    • if w is marked "unvisited", then
      • DFS(G,w).
  Arcs followed in execution of dfs form a depth-first search tree
  What if graph not connected?  We may not be able to visit all nodes from u.
  In this case, pick another starting node and run dfs again.  Repeat until all nodes visited.  Set of arcs that are followed is a depth-first search forest.

  DFSForest(G):

  • For every node v in G:
    • Mark v "unvisited".
  • For every node v in G:
    • If v is marked "unvisited", then
      • DFS(G,v).

Tree

• A free tree T is a simple graph satisfying the following :
  If v and w are vertices in T, there is a unique path from v to w.

• A rooted tree is a tree in which a particular vertex is designated the root.

• The level of a vertex v is the length of the simple path from the root to v.

• The height of a rooted tree is the maximum level number that occurs.

• Some properties of tree
  • Any tree with two or more vertices has a vertex of degree 1.
  • A tree is a planar graph.
  • A tree is a bipartite graph.

• Let T be a tree with root v₀. Suppose that x, y , and z are vertices in T and that (v₀,v₁,..., v_n) is a simple path in T. Then
  1. v_n-1 is the parent of v_n.
  2. v₀,...v_n-1 are ancestors of v_n.
  3. v_n is a child or v_n-1.
  4. If x is an ancestor of y, then y is a descendant of x.
  5. If x and y are children of z, then x and y are siblings.
  6. If x has no children, then x is a terminal vertex (or a leaf).
  7. If x is not a terminal vertex, then x is an internal (or branch) vertex.
  8. The subtree of T rooted at x, is a graph with vertex set V and edge set E, where V is x together with the descendants of x and
     E = {e | e is an edge on a simple path from x to some vertex in V }.

• Let T be a graph with n vertices. The following are equivalent.
  1. T is a tree.
  2. T is connected and acyclic.
  3. T is connected and has n-1 edges.
  4. T is acyclic and has n-1 edges.

  Proof : see page 333-334 of the text.

• A graph G with n vertices and fewer than n-1 edges is not connected.

• Spanning Trees

  A tree T is a spanning tree of a graph G if T is a subgraph of G that contains all of the vertices of G.

• A graph G has a spanning tree if and only if G is connected.

• Minimal Spanning Trees

  Let G be a weighted graph. A minimal spanning tree of G is a spanning tree of G with minimum weight.

  There are two well-known algorithms to find a minimal spanning tree:

  1. Prim's Algorithm Demo
  2. Kruskal's Algorithm Demo
     reference
  Reference

• Binary Trees

  A binary tree is a rooted tree in which each vertex has either no children, one child or two children. A vertex , with the excetion of being the root, is either left child or right child of its parent.

  reference

  • A full binary tree is a binary tree in which each vertex has either two children or zero children.

  • Theorem : If T is a full binary tree with i internal vertices, the T has i+1 terminal vertices and 2i+1 total vertices.

  • Theorem: If a binary tree of height h has t terminal vertices, then
    lg t £ h .

  • A binary tree is completely full if it is of height, h, and has 2^h+1-1 nodes.

    A binary tree of height, h, is complete iff

    1. it is empty or
    2. its left subtree is complete of height h-1 and its right subtree is completely full of height h-2 or
    3. its left subtree is completely full of height h-1 and its right subtree is complete of height h-1.
    A complete tree is filled from the left:
    • all the leaves are on
      • the same level or
      • two adjacent ones and
    • all nodes at the lowest level are as far to the left as possible.
  • A binary search tree is a binary tree T in which data are associated with the vertices. The data are arranged so that, for each vertex v in T, each data item in the left subtree of v is less than the data item in v, and each data item in the right subtree of v is greater than the data item in v.

  • Binary Tree Traversals

    Binary Tree Traversals

    • Inorder:
      • Traverse left subtree
      • Visit root
      • Traverse right subtree
    • Preorder:
      • Visit root
      • Traverse left subtree
      • Traverse right subtree
    • Postorder:
      • Traverse left subtree
      • Visit root
      • Traverse right subtree
    • Preorder Traversal

      procedure preorder(T)              
      1. if T is empty then
      2.     return
      3.  process T
      4.  left := left child of T
      5.    preorder(left)
      6.  right := right child of T
      7.   preorder(right)
      8.  end preorder
      

    • Inorder Traversal

      procedure inorder(T)              
      1. if T is empty then
      2.     return
      3.  left := left child of T
      4.    inorder(left)
      5.  process T
      6.  right := right child of T
      7.   inorder(right)
      8.  end inorder
      

    • Postorder Traversal

      procedure preorder(T)              
      1. if T is empty then
      2.     return
      3.  left := left child of T
      4.    postorder(left)
      5.  right := right child of T
      6.   postorder(right)
      7.  process T
      8.  end postorder
      

      Tree traversal demo

    • Applications
      
      • Huffman codes reference
      • infix expression , postfix notation reference

      Animation
      

• Homework #7
• Homework #8