Gestalte GoConqr mit. Was sollen wir als Nächstes hinzufügen?

Notizen

Tree Properties

Dante Aviñó Discrete Maths Spanisch 2 Seiten

Inhalt der Notizen (2)

Seite 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.

Seite 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.

Informationen

Beschreibung
Discrete Maths Notiz am Tree Properties, erstellt von Dante Aviñó am 20/11/2019.
Erstellt von
Dante Aviñó · Nov 2019
Aktualisiert
20 Nov 2019
Aufrufe
0
Bewertung

Feedback

Worum geht es?

Was sollen wir als Nächstes hinzufügen?