Test -2 Review

Chapter 7: From 7.5 onwards

Euler and Hamilton circuits/paths

All the theorems (not proofs)

All the definitions

What is gray code? How can you use Qn and Hamilton circuit

Shortest path: Dijkstra’s algorithm

Planar graph: Definition and two theorems (no proofs)

Graph coloring problem, what is chromatic number/edge chromatic number

Theorem 1: Four color problem

Chapter 8

Basic definitions: tree, rooted tree, siblings/parent,..

Theorem 1-5 and the corollary (no proofs)

Problems similar to those in the assignment

What is a spanning tree, how to create a spanning tree

Two algorithms for creating minimum spanning trees

Chapter 9

Identities

Abstract concept of Boolean algebra

Given a function you should be able to construct corresponding circuit and vice versa

Develop mathematical form of a function as sum of minterms

Reduce a function using Karnaugh map