HOME SCHEDULE EXERCISES ASSIGNMENTS BOOK FIRE TIME-EDIT
SCHEDULE EXERCISES ASSIGNMENTS BOOK FIRE TIME-EDIT

Assignment 6 - Graphs and Combinatorics

Please submit using the Fire system

Question 1

For a directed graph ("riktad graf") G with n nodes, let A(n) be the maximum number of arrows ("pilar", "riktade kanter") G can have, without G having a cycle.

Your job is to investigate what A(n) is.

Examples:

  • A directed graph with 2 nodes can have 1 arrow without there being a cycle, but it must have a cycle with more than 1 arrow. So A(2) = 1.

  • A directed graph with 3 nodes can have 3 arrows without there being a cycle, but it must have a cycle with more than 3 arrows. So A(3) = 3.

  • A directed graph with 4 nodes can have 6 arrows without there being a cycle, but it must have a cycle with more than 6 arrows. So A(4) = 6.

Express your answer A(n) in terms of n. For your answer, explain both:

(a) that there exist directed graphs with n nodes that have A(n) arrows and no cycles, and

(b) that directed graphs with n nodes with more arrows than A(n) must have a cycle.

Hint: A graph without cycles must have a topological order. Once you know the order of the nodes, which arrows can you add without introducing a cycle?

Question 2

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: (a) Write a program that enumerates all possibilities, and (b) 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 Fri, Oct 25, at 13:00. 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 Fri, Nov 1, at midnight to submit a completely correct version.

You can submit your answers (in Swedish or English) in any of the following formats:

  • A simple text file, ending in .txt. You can make text files in any text editor, and then upload it to the Fire system.

    (When using a text file, you may sometimes need to "invent" notation. Please be clear about what your notation means. A list of suggested notation for text files is provided by us. You may also use Unicode.)

  • A picture you have made in a painting program, ending in .gif, .jpg, or .png. You can use for example MS Paint, or Google Docs to make a picture, and upload it to the Fire system.

  • A PDF-file, ending in .pdf. You can make PDF files by for example using OpenOffice, LibreOffice, Microsoft Word, or Google Docs, and choosing export as PDF. Then, upload the PDF-file to the Fire system.

  • A scanned in document, ending in .pdf or .jpg. You can write your answer on a piece of paper, and use a scanner to scan it in and convert to a PDF-file. Or you can use a camera or your mobile phone to take pictures of the papers, and upload these to the Fire system.

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.