Graphs and Trees

Question 1

Self loop

Answer 1

Edge leading to and from the same node

Question 2

Degree

Answer 2

Number of edges leading to or from a node

Question 3

When counting the degree of a node, self loops should be counted…

Answer 3

Twice

Question 4

Path

Answer 4

Edges that can be used to reach a node

Question 5

Length of a path

Answer 5

k - 1 (k being the number of nodes)

Question 6

Circuit

Answer 6

A path where the start and end nodes are the same

Question 7

Cycle

Answer 7

A circuit where you don’t visit the same node (except the start/end node) twice

Question 8

Hamiltonian

Answer 8

A circuit including all nodes

Question 9

Root node

Answer 9

No edges pointing towards it

Question 10

True or false: A leaf node has both in and outgoing edges

Answer 10

False! A leaf node has no outgoing edges.

Question 11

Depth

Answer 11

Number of edges to a node from the root

Question 12

True or false: The number of nodes in a tree is exponential to its depth

Answer 12

True!

Question 13

Binary tree

Answer 13

A tree with no more than 2 subtrees per node

Question 14

In a binary tree, there are no more than _ nodes at any level

Answer 14

2 to the power of L (L being the current level)

Question 15

True or false: There are multiple ways to reach each node in a tree

Answer 15

False! Each node has a unique path leading to it.