Due date for on-time submission: 11:55pm on Wed. Sept. 28, 2016 [30 points]
A tree is a graph with no cycles. A caterpillar is a tree which does not contain the following graph as a subgraph:
Write a C or C++ program that takes an integer n as a command line parameter. The program has no other inputs. The output of the program should be exactly one caterpillar from each isomorphism class of the n-vertex caterpillars. For each output caterpillar, print one line containing its upper triangular adjacency matrix.
Your program should be called LastName.c or LastName.cpp. For example, I might use LastName.c. Upload your program to connex for Assignment #1 B.
You can use
#define NMAX 32
and print an error message if n is greater than 32.
To ensure your program compiles on my computer please
use:
#include <stdio.h>
#include <stdlib.h>
at the top of your program.
Up to isomorphism, the number of caterpillars on 4 vertices is 2. Here they are:
If you decide to label them as shown in the picture, then the output from running your program with command line parameter 4 could be:
4 001011
4 010011
The The On-Line Encyclopedia of Integer Sequences is a very helpful resource for when you have written a program for generating some combinatorial objects and you want to check to make sure you are getting the correct number of objects up to isomorphism. To check if your counts are correct for larger values of n, go to The On-Line Encyclopedia of Integer Sequences and type caterpillar into the search box.
All code submitted must be your original work. If you use code taken from the internet, an API, other students, previous model solutions or other sources and submit it as your own work you will not get credit for that code. Further if your source is not acknowledged, you are subject to disciplinary action according to the department policies for plagiarism.