CSC1031 – Semester 2 Examina3on
Fundamentals Of Computing
Topic 1: Graphs and Trees
Directed Graph is a pair G={N, E} consisting of
- Non-empty set N of nodes (each with a unique name)
- Set E of directed edges between notes where EÍN´N and (n,m) Î E represents edge from node n
to node m
Path in a directed graph G={N, E} is a sequence of node
n0 n1 ... nk
such that (ni, ni+1)ÎE is an edge in the directed graph G for each i=0,...,k-1.
Circuits
- Circuit is a path n0 n1 ... nk whose start and end nodes are the same, i.e. n0=nk.
Cycle
- A cycle is a circuit of length 1 or more in which you never visit the same node twice except for the
start and end.
Subgraphs
Given graphs G=(N,E) and G’=(N’,E’) we say G is a subgraph of G’ if,and only if, N Í N’ and E Í E’
Hamiltonian Cycle
- Definition: A Hamiltonian path in a graph is a path that includes all nodes in the graph.
- Note the length of a Hamiltonian cycle must be equal to the number of nodes in the graph.
1
, CSC1031 – Semester 2 Examina3on
Programming with Graphs
Given a graph with n nodes an adjacency matrix M is an n by n matrix where:
- Represent a directed edge from node i to node j by setting the entry at row i and column j in M to
the value 1.
- If no edge exists from node i to node j then the entry at (i , j) is set to 0.
Rooted Trees
- A tree is a special kind of directed graph used to model hierarchical information. A (rooted) tree is
simply a directed graph which satisfies the following properties:
§ Contains a single root node that has no edge pointing to it.
§ Every node in the tree has a unique path to it from the root node.
- A node that has no outgoing edges is called a leaf node.
- Every node except the root has exactly one ingoing edge pointing to it.
- Each node has edges to zero or more subtrees.
- Normally draw trees top down starting from the root node.
Binary Trees
- A binary tree is a tree in which each node is allowed no more than two subtrees.
- For each node in binary tree we normally identify left child and right child (depending on how tree is
drawn).
- The properties of a binary tree are the following:
1. Theorem 1: A binary tree has a maximum of 2L nodes at any level LÎN.
2. Theorem 2: A binary tree of depth d contains at most 2(d+1) -1 nodes
Proof use theorem 1
• By Theorem 1 we know at each level L=0,...,d there are at most 2L nodes.
• This gives us the sum:
20+ 21 + 22 + ... + 2d
• Can show that this sum is equivalent to 2 d+1-1 as required.
2
Fundamentals Of Computing
Topic 1: Graphs and Trees
Directed Graph is a pair G={N, E} consisting of
- Non-empty set N of nodes (each with a unique name)
- Set E of directed edges between notes where EÍN´N and (n,m) Î E represents edge from node n
to node m
Path in a directed graph G={N, E} is a sequence of node
n0 n1 ... nk
such that (ni, ni+1)ÎE is an edge in the directed graph G for each i=0,...,k-1.
Circuits
- Circuit is a path n0 n1 ... nk whose start and end nodes are the same, i.e. n0=nk.
Cycle
- A cycle is a circuit of length 1 or more in which you never visit the same node twice except for the
start and end.
Subgraphs
Given graphs G=(N,E) and G’=(N’,E’) we say G is a subgraph of G’ if,and only if, N Í N’ and E Í E’
Hamiltonian Cycle
- Definition: A Hamiltonian path in a graph is a path that includes all nodes in the graph.
- Note the length of a Hamiltonian cycle must be equal to the number of nodes in the graph.
1
, CSC1031 – Semester 2 Examina3on
Programming with Graphs
Given a graph with n nodes an adjacency matrix M is an n by n matrix where:
- Represent a directed edge from node i to node j by setting the entry at row i and column j in M to
the value 1.
- If no edge exists from node i to node j then the entry at (i , j) is set to 0.
Rooted Trees
- A tree is a special kind of directed graph used to model hierarchical information. A (rooted) tree is
simply a directed graph which satisfies the following properties:
§ Contains a single root node that has no edge pointing to it.
§ Every node in the tree has a unique path to it from the root node.
- A node that has no outgoing edges is called a leaf node.
- Every node except the root has exactly one ingoing edge pointing to it.
- Each node has edges to zero or more subtrees.
- Normally draw trees top down starting from the root node.
Binary Trees
- A binary tree is a tree in which each node is allowed no more than two subtrees.
- For each node in binary tree we normally identify left child and right child (depending on how tree is
drawn).
- The properties of a binary tree are the following:
1. Theorem 1: A binary tree has a maximum of 2L nodes at any level LÎN.
2. Theorem 2: A binary tree of depth d contains at most 2(d+1) -1 nodes
Proof use theorem 1
• By Theorem 1 we know at each level L=0,...,d there are at most 2L nodes.
• This gives us the sum:
20+ 21 + 22 + ... + 2d
• Can show that this sum is equivalent to 2 d+1-1 as required.
2
