Trees

• A tree is a connected unidirectional graph with no cycles
  • There is just one path between each pair of vertices

Examples of trees:

Tree Types §

• A tree is classed as rooted if one vertex is designated and every edge is directed away from the root

  • A rooted tree only has one root

• A binary tree is a tree graph with each vertex (or node) having no more than two child nodes

  • Nodes with children are called parent nodes
  • Nodes are referred to as left or right node / child
  • The root is the ancestor of all nodes

Tree components §

• Trees have components

Paths §

• A path is the route between any two vertexes
  • More specifically, it is a sequence of edges that begins at a vertex, travelling from vertex to vertex until the destination vertex is found

Explorer’s Problem §

• An explorer wants to explore all the routes between a number of cities
• Can a tour be found which traverses each route (edge) only once?
  • Particularly, find a tour which starts at A, goes along each road exactly once, and ends back at A
    • Cities can be visited more than once

A B C D E F B G C E G F A

Traveller’s Problem §

• The traveller’s problem is the inverse of the explorer’s problem. Aka travelling salesman problem
  • We can re-use edges, but only visit a vertex once
• A traveller wants to visit a number of cities. Can a tour be found which visits each city once?
  • Particularly, find a tour which starts at A, goes to each city exactly once, and ends back at A

A B C D E G F A