16: Trees and searches — Read

From LibreTexts, under GNU Free Documentation, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

16.1: Motivation
Reducing redundancy. You have set up your own tree-fort communication system out of tin cans and strings.
16.2: Basics
Trivial Path: a path that consists of a single vertex
16.3: Identifying Trees
Theorem: Characterizations of trees. The following are equivalent for a graph G=(V,E) with |V|=n vertices.
16.4: Depth-first and breadth-first searches
Let G be a graph. Given vertices v,v′ of G, we might wish to find a path from v to v′, if one exists. We can do this by constructing a tree T⪯G.
16.5: Spanning Trees
Spanning Subgraph: a subgraph that contains all the vertices of the parent graph
16.6: Binary Searches
Binary Search Tree: a tree in which every node has degree 1 or 3, except for a single node of degree 2.
16.7: Activities
16.8: Exercises

This page titled 16: Trees and searches was last modified on Tue, 01 Sep 2026 03:33:55 GMT and is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform.

Contents

Text