Algorithmik

IT Security - Semester 3 - Algorithmik bei Hower

6 flashcards · Computer Science · by manuel-tiedtke

1. Was versteht man unter einem Baum (tree)?

   Ein Baum ist ein azyklischer Graph, also ein Graph in dem es nicht moeglich ist, sich von einem Knoten fortzubewegen und zu ihm zurueckzukehren ohne eine Kante dabei zwei mal zu beschreiten.

2. Was versteht man unter einem free tree?

   Die genauere Bezeichnung fuer einen Baum (tree), also einen azyklischen Graphen.

3. Another very important property of trees is the fact that for every two vertices in a tree, there always exists exactly one simple path from one of these vertices to the other.

   Think about what type of graph a tree is and what's the defining property of that type of graph.

4. The number of edges in a tree is always one less than the number of its vertices.

5. For any vertex v in a tree T, all the vertices on the simple path from the root to that vertex are called ancestors of v. The vertex itself is usually considered its own ancestor. The set of ancestors that excludes the vertex itself is referred to as the set of proper ancestors.

6. If (u, v) is the last edge of the simple path from the root to vertex v (and u != v), u is said to be the parent of v and v is called a child of u. Vertices that have the same parent are said to be siblings.