Summary
Summary Topic 1: Graphs and Trees - Fundamental of Computing (CSC1031)
- Institution
- CSC1031- Fundamentals Of Computing
Cheat Sheet and summary sheet for CSC1031 module. Topic 1 notes
[Show more]
Seller
Follow
Content preview
CSC1031 – Semester 2 Examina3onFundamentals 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller giovanniconstantina04. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £3.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
66579 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now