16.2: Basics — Read — Invisible Network

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.

Definition: Trivial Path

a path that consists of a single vertex

Definition: Cycle

a closed path

Definition: Proper Cycle

a nontrivial cycle that is also a trail

Note \(\PageIndex{1}\)

If \(G\) contains vertices \(v,v'\) and edge \(e = \{v,v'\}\text{,}\) then \(v,e,v',e,v\) is a nontrivial cycle which is not proper.

Definition: Acyclic Graph

contains no proper cycles

Definition: Forest

synonym for acyclic graph

Definition: Tree

a connected, acyclic graph

Example \(\PageIndex{1}\): A forest of trees.

The graph in Figure \(\PageIndex{1}\) is acyclic. Each of its connected components is a tree.

Figure \(\PageIndex{1}\): A nonconnected acyclic graph.

Example \(\PageIndex{2}\): Decision trees are trees.

In Worked Example 15.2.3, we attempted to determine all possible trails from one node to another in a given graph. The graph in Figure 15.2.2 that we used to explore possible trails in the given graph is an example of a decision tree — at each node we “branched out” to new possibilities in continuing the trail. As the name suggested, the connected graph we ended up with is a tree.

Proposition \(\PageIndex{1}\): Subgraphs of forests.

Every subgraph of an acyclic graph is acyclic.
Every connected subgraph of an acyclic graph is a tree. In particular, each connected component of an acyclic graph is a tree.

This page titled 16.2: Basics was last modified on Tue, 01 Sep 2026 03:35:28 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