Chapter 13: Graphs

Chapter 13: Graphs

13.1 Introduction to graphs

PARTICIPATION ACTIVITY

Graph terminology

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Check Show answer

Check Show answer

Check Show answer

Proof.

Example 13.1.1: Undirected graphs in applications.

PARTICIPATION ACTIVITY

13.1.5: Constraint graphs.

Common graphs

PARTICIPATION ACTIVITY

13.1.6: Notation for common graphs.

Reset

Additional exercises

EXERCISE

EXERCISE

EXERCISE

13.2 Graph representations

PARTICIPATION ACTIVITY

Adjacency list representation for graphs

Animation content:

Animation captions:

Matrix representation for graphs

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

CHALLENGE ACTIVITY

Start

Additional exercises

EXERCISE

EXERCISE

EXERCISE

EXERCISE

13.3 Graph isomorphism

Definition 13.3.1: Isomorphic graphs.

Animation content:

Animation captions:

Proof.

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

Proof 13.3.2: Degree sequence preserved under isomorphism,

Proof.

PARTICIPATION ACTIVITY

Additional exercises

EXERCISE

EXERCISE

EXERCISE

EXERCISE

13.4 Walks, trails, circuits, paths, and cycles

Animation content:

Animation captions:

Animation content:

Animation captions:

CHALLENGE ACTIVITY

Start

Additional exercises

EXERCISE

EXERCISE

EXERCISE

13.5 Graph connectivity

Connected components

Animation content:

Animation captions:

k-connectivity

Edge connectivity

Animation content:

Animation captions:

Proof.

PARTICIPATION ACTIVITY

Check Show answer

Check Show answer

Check Show answer

Check Show answer

Check Show answer

Additional exercises

EXERCISE

EXERCISE

EXERCISE

EXERCISE

EXERCISE

13.6 Euler circuits and trails

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

x

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Finding an Euler circuit and the proof of sufficient conditions for an Euler circuit

Proof.

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Proof.

Proof 13.6.3: Every vertex in G' has an even degree.

Proof.

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Euler trails

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

CHALLENGE

ACTIVITY

Start

CHALLENGE

ACTIVITY

Start

Additional exercises

EXERCISE

EXERCISE

13.7 Hamiltonian cycles and paths

Animation content:

Animation captions:

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

CHALLENGE ACTIVITY

Start

CHALLENGE ACTIVITY

Additional exercises

EXERCISE

13.7.2: Finding Hamiltonian cycles in small graphs.

EXERCISE

13.7.3: Hamiltonian paths in small graphs.

EXERCISE

13.8 Planar graphs

Definition 13.8.1: Planar graphs.

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Characterizing planar graphs

Animation content:

Static figure:

Animation captions:

Type 1:

Type 2:

Proof 13.8.1: Euler’s Identity.

Proof.

PARTICIPATION ACTIVITY

Proof.

PARTICIPATION ACTIVITY

Additional exercises

EXERCISE

13.9 Graph coloring

Definition 13.9.1: Graph coloring.

The chromatic number of a graph

Greedy coloring

Figure 13.9.6: The greedy coloring algorithm.

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

PARTICIPATION ACTIVITY

Additional exercises

EXERCISE

Source