Contents
xi
SECTiOn 7.1 Review
566
ExErCiSES 7.1
566
7.2 EULER PATH AND HAMILTONIAN
CIRCUIT
571
Euler Path Problem
571
Hamiltonian Circuit Problem
576
SECTiOn 7.2 Review
577
ExErCiSES 7.2
577
7.3 SHORTEST PATH AND MINIMAL
SPANNING TREE
581
Shortest-Path Problem
581
Minimal Spanning Tree Problem
587
special interest page
Pathfinding
589
SECTiOn 7.3 Review
591
ExErCiSES 7.3
591
7.4 TRAVERSAL ALGORITHMS
596
Depth-First Search
596
Breadth-First Search
598
Analysis
601
Applications
601
SECTiOn 7.4 Review
604
ExErCiSES 7.4
604
7.5 ARTICULATION POINTS AND
COMPUTER NETWORkS
607
The Problem Statement
607
The Idea behind the Algorithm
608
The Algorithm Itself
610
SECTiOn 7.5 Review
612
ExErCiSES 7.5
612
Chapter 7 Review
614
On the Computer
615
CHAPTEr 8
Boolean Algebra and
Computer Logic
617
8.1 BOOLEAN ALGEBRA STRUCTURE
618
Models or Abstractions
619
Definition and Properties
620
Isomorphic Boolean Algebras
626
What is Isomorphism?
626
Isomorphism as Applied
to Boolean Algebra
628
SECTiOn 8.1 Review
631
ExErCiSES 8.1
631
8.2 LOGIC NETWORkS
638
Combinational Networks
638
Basic Logic Elements
638
Boolean Expressions
639
Truth Functions
640
Networks and Expressions
641
Canonical Form
642
Minimization
645
Programmable Logic
Devices
647
A Useful Network
648
Other Logic Elements
650
Constructing Truth Functions
652
special interest page
Pruning Chips and Programs
654
SECTiOn 8.2 Review
655
ExErCiSES 8.2
655
8.3 MINIMIzATION
663
Minimization Process
663
Karnaugh Map
665
Maps for Three and
Four Variables
666
Using the karnaugh Map
668
Quine–McCluskey Procedure
673
SECTiOn 8.3 Review
677
ExErCiSES 8.3
678
Chapter 8 Review
683
On the Computer
684
CHAPTEr 9
Modeling Arithmetic,
Computation, and
Languages
685
9.1 ALGEBRAIC STRUCTURES
686
Definitions and Examples
686
Basic Results about Groups
695
Subgroups
698
Isomorphic Groups
702