February 16th, 2016

Glossary. Here are some definitions that we use.
1. A self-loop is an edge that connects a vertex to itself.
2. Two edges are parallel if they connect the same pair of vertices.
3. When an edge connects two vertices, we say that the vertices are adjacent to one another and that the edge is incident on both vertices.
4. The degree of a vertex is the number of edges incident on it.
5. A subgraph is a subset of a graph’s edges (and associated vertices) that constitutes a graph.
6. A path in a graph is a sequence of vertices connected by edges. A simple path is one with no repeated vertices.
7. A cycle is a path (with at least one edge) whose first and last vertices are the same. A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).
8. The length of a path or a cycle is its number of edges.
9. We say that one vertex is connected to another if there exists a path that contains both of them.
10. A graph is connected if there is a path from every vertex to every other vertex.
11. A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs.
12. An acyclic graph is a graph with no cycles.
13. A tree is an acyclic connected graph.
14. A forest is a disjoint set of trees.
15. A spanning tree of a connected graph is a subgraph that contains all of that graph’s vertices and is a single tree.
16. A spanning forest of a graph is the union of the spanning trees of its connected components.
17. A bipartite graph is a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set.

Robert Sedgewick and Kevin Wayne.

Classwork:
Video: Watch 14.1 and 14.2 in classroomsalon.com and answer the questions.

Homework
Undirected Graphs – Ex 4.1.4-4.1.6