代写720S1C、代写c++,java编程

日期：2022-04-12 11:16

Computer Science 720S1C – (2022)

Assignment 2 (Trees and Treewidth)

Due: Saturday, April 16

Requirements

This assignment deals with trees and graphs of bounded treewidth. The first part tests your under-

standing of rooted tree isomorphism and the second part has you develop a linear-time algorithm (for

graphs of bounded treewidth) for a known NP-hard graph optimization problem.

You will submit your source code to https://www.automarker.cs.auckland.ac.nz/. If you have not

used the automarker before, please read the help/FAQ page.

Determine Tree Groups

We want to group together the same rooted trees from a collection of rooted trees. In general we have

the following constraints:

The root node always remains in this position, i.e., as root.

Each other node remains connected to its original parent node.

Each node (root or not) branches out to the same set of nodes but the order of outgoing branches

may change in an arbitrary way.

Thus, in the following diagram, the trees (a) and (b) could represent the same tree, but the trees

represented in (c) and (d) are certainly different. The roots are labeled by 0 in this example.

1

We want to write a program that will identify matching trees (rooted tree isomorphism) under these

reshuffling rule, i.e., trees that could represent the same tree. This matching is an equivalence relation

and the problem can be solved by annotating each tree with the number of its equivalence class. Your

task is to determine which trees are equivalent.

Input Format

Input (from stdin) consists of a number of scenarios, with each scenario consisting of a number of trees.

Each scenario starts with a line containing a single number, n (1 ≤ n ≤ 100) specifying the number of

trees in the scenario, followed by n descriptions. Each description consists of a number k (1 ≤ k ≤ 1000)

specifying the number of nodes in the tree, followed by k numbers specifying the parent of each node in

turn (using ?1 for the root node, which has no parent). Each tree is implicitly numbered by its position

in this list. The sequence of scenarios is terminated by an empty scenario, i.e., a line containing only a

zero (‘0’).

Output Format

Output (to stdout) consists of one line for each scenario, starting with a scenario sequence number (0

based), a colon (‘:’), a space, and followed by a succession of class numbers, one for each tree, in input

order, and separated by single spaces. All trees in a matching class are annotated by the same class

number. Class numbers are allocated successively in input tree order, starting with 0, and increased by

1 at the first occurrence of an tree not matching any of the previous.

Sample Input and Output

Input Output

Chromatic Sum

For this part, you will do some basic programming regarding the t-parse representation of graphs.

We use the following t-parse input format for graphs of bounded treewidth. The first token will be an

integer 0 ≤ t ≤ 9 denoting the pathwidth/treewidth of the graph (i.e., it indicates a t-parse will follow).

The interpretation for the remaining tokens are given in the next table.

token semantic meaning

i a vertex operator i, represented as an integer, where 0 ≤ i ≤ t ≤ 9

ij an edge operator (i, j) where t ≥ i > j ≥ 0 (note: no space between i and j)

( a begin marker for a pathwidth t-parse (can be nested for treewidth t-parses)

) an end marker for a pathwidth/treewidth t-parse

Thus, if you read/encounter the two tokens ‘)’ and ‘(’ in sequence then this denotes a circle plus ⊕

operator. Note that it is guaranteed that each right token ‘(’ will have a matched left token ‘)’. Each

’(’ except first token must be preceded by a parenthesis and ’)’ may be succeeded “up the parse tree”

by pathwidth operators. We assume boundary vertices 0, 1, . . . , t precede the first token of a pathwidth

t-parse (and these empty boundaried graph axioms are not given in the input format). Assume left-

associativity for all operators and at least one space between each of them, including the parentheses.

Input will consist of several test cases, each on its own line. The input is terminated by a t = 0 case,

which is also processed.

For this part of the assignment you will learn how to exploit the structure of bounded pathwidth/treewidth

for a known NP-hard graph problem: 3-ChromaticSum. For input graph of bounded pathwidth or

treewidth in t-parse representation as described above, decide if it can be colored with at most 3 colors

and if so output its chromatic sum, otherwise output ‘None’ .

A graph G = (V,E) is 3-colorable if there is a function (e.g. proper coloring) f : V → {1, 2, 3} such

that for all (u, v) ∈ E we have f(u) 6= f(v). The chromatic sum of a graph G is the minimum sum

Σv∈V f(v) of a proper coloring f of G. Note the minimum number of colors needed (chromatic number)

may not necessarily correspond with its minimum chromatic sum as shown in the following example.

The 2-coloring on the left has a sum of 12 while the 3-coloring on the right has a smaller sum of 11.

3

Sample Input/Output

Typical input instances and expected output of the two problems are shown below. Note that you can

assume that each input graph fits on one line.

Sample input

2 ( 10 21 1 10 21 0 10 20 2 20 21 )

2 ( ( 10 21 1 10 21 1 21 10 ) ( 21 2 21 20 ) ( 10 ) )

4 ( ( 10 20 30 41 4 41 31 ) ( ( 40 21 32 42 ) ( 10 0 43 10 20 ) ) )

0 ( ( 0 ) ( 0 0 ) )

Sample output

Submission and Marks

All input should be taken from the keyboard (stdin) and output to the console (stdout). This assignment

is worth 10% of your final grade. Marks (out of a total 10) for each part’s test cases are specified on

the automarker scoreboard. Note that your final grade may be marked with more difficult test cases

than what is provided to the automarker. If you exceed 8 submissions per any problem test case then

a 20% deduction will occur (on that case) if you eventually get it correct. Partial marks may be given

later so try to submit something even if you know it is not 100% correct.