Notes
Tree Properties
Content of the notes (2)
Page 1
Definition. A tree is a connected and acyclic (that is, without cycles) graph.
Definition. A forest is a graph where each connected component is a tree.
Definition. A leaf in a tree (or forest) is a node with degree
Every tree has the following properties:
1. Every connected subgraph is a tree.
2. There is a unique path between every pair of vertices.
3. Adding an edge between non-adjacent nodes produces a graph with a cycle.
4. Removing any edge produces a disconnected graph.
5. If the tree has at least two vertices then it has at least 2 leaves.
6. If v is the number of vertices and e is the number of edges then v = e + 1.
Page 2
Recursive definition of trees:
BASIC STEP: Any graph with a single vertex is a tree.
RECURSIVE STEP: Suppose that T is a tree. Then, the new graph formed by adding to T a new node x and an edge (x,y) joining x with exactly one node y in T, is also a tree.
Information
- Description
- Discrete Maths Note on Tree Properties, created by Dante Aviñó on 20/11/2019.
- Created by
- Dante Aviñó
- Views
- 0
- Rating