Assignment Week 6 - Graphs and Combinatorics
Please submit using the Fire system
Assignments
(1.) Given an undirected graph G where every node has a degree ("gradtal") of 2 or more. Show that G cannot be a tree.
Hint 1: Draw some example graphs where every node has degree >= 2 and try to make them look like trees. You will find this is impossible because you will need to draw too many edges. Think about this: What is the minimum number of edges you need to draw for a graph with n nodes in order to make the degree of every node at least 2?
Hint 2: You may use any part of Theorem 12.9.3 from the book, but only if you clearly state which part you used. Also look at exercise 10, week 7.
|
(2.) Take a look at the directed graph below. How many topological orderings are there for this graph? Motivate your answer.
|
(3.) How many different strings can you form using exactly the 8 letters A, N, A, C, O, N, D, A in any order?
Compute your answer in two different ways: (1) Write a program that enumerates all possibilities, and (2) Show how the answer can be calculated using formulas from combinatorics.
Ideally, you should get the same answer :)
Hint: If you write your program in Haskell, use the standard Haskell functions nub and permutations from the module Data.List. Don't forget to import Data.List.
|
Submission
Submission of this assignment should be done electronically through the Fire system.
The submission deadline is Friday, October 21, at 23:59. At this time, you should have submitted a serious attempt to solve the assignment. A serious attempt is either an answer you believe to be correct, or a partial answer plus a detailed explanation of what you have tried to come up with a full answer. An empty document is not a serious attempt.
After submitting, you have until Sunday October 30 (midnight) to submit a completely correct version.
You can submit your answers in any of the following formats:
If you submit multiple files, please name and/or number them such that the order in which we should read them is obvious. You can also write a text file, and have it refer to pictures that you upload separately.
|