Consider Problem 0.14 (and its solution). Write a Java program that reads in a graph and outputs the clique from pile A and the independent set from pile B. Your program should read from standard input and write to standard output.

The input is a parenthesized list of elements. Each element is a parenthesized identifier or parenthesized pair of identifiers. In the former case, it represents a vertex with the given identifier. In the latter case, it represents an edge between vertices with the given identifiers. There are no ordering constraints, so a vertex may be presented after an edge that uses it. Further, vertices that are mentioned in edges are implicitly assumed to exist, even if they are not explicitly provided in the input. You may assume that the identifiers follow the rules for Java identifiers.

Problem 14 for reference.

Solution to 14

Anything helps! :)

H For example, the graph depicted on the left above may be presented as input ((a b) (b c) (b) (ca) (a)) The (a) and (b) are redundant and may or may not) be skipped in such input. The graph on the right may be provided as: (a) (b c) (d a) (cd) (ce) (f g) (h)). The input may contain arbitrary whitespace (including none, except when needed to separate identifiers). So the second example may also be provided as ((a) (b c) (d a)(c d) e) (f g) (h) or with several blank lines inserted between the first b and c occurrences. The output should be a the clique followed by the independent set, both encoded as above. However, the output encoding should use vertex specifiers of the form (x) only when strictly needed. Further, each graph's representation should be lexicographically sorted (with identifiers compared lexicographically as well). A*0.14 Ramsey's theorem. Let G be a graph. A clique in G is a subgraph in which every two nodes are connected by an edge. An anti-clique, also called an independent set, is a subgraph in which every two nodes are not connected by an edge. Show that every graph with n nodes contains either a clique or an anti-clique with at least log, n nodes. 0.14 Make space for two piles of nodes: A and B. Then, starting with the entire graph, repeatedly add each remaining node to A ifits degree is greater than one half the number of remaining nodes and to B otherwise, and discard all nodes to which r isn't (is) connected if it was added to A (B). Continue until no nodes are left. At most half of the nodes are discarded at each of these steps, so at least log, n steps will occur before the process terminates. Each step adds a node to one of the piles, so one of the piles ends up with at least log, n nodes. The A pile contains the nodes of a clique and the B pile contains the nodes of an anti-clique. H For example, the graph depicted on the left above may be presented as input ((a b) (b c) (b) (ca) (a)) The (a) and (b) are redundant and may or may not) be skipped in such input. The graph on the right may be provided as: (a) (b c) (d a) (cd) (ce) (f g) (h)). The input may contain arbitrary whitespace (including none, except when needed to separate identifiers). So the second example may also be provided as ((a) (b c) (d a)(c d) e) (f g) (h) or with several blank lines inserted between the first b and c occurrences. The output should be a the clique followed by the independent set, both encoded as above. However, the output encoding should use vertex specifiers of the form (x) only when strictly needed. Further, each graph's representation should be lexicographically sorted (with identifiers compared lexicographically as well). A*0.14 Ramsey's theorem. Let G be a graph. A clique in G is a subgraph in which every two nodes are connected by an edge. An anti-clique, also called an independent set, is a subgraph in which every two nodes are not connected by an edge. Show that every graph with n nodes contains either a clique or an anti-clique with at least log, n nodes. 0.14 Make space for two piles of nodes: A and B. Then, starting with the entire graph, repeatedly add each remaining node to A ifits degree is greater than one half the number of remaining nodes and to B otherwise, and discard all nodes to which r isn't (is) connected if it was added to A (B). Continue until no nodes are left. At most half of the nodes are discarded at each of these steps, so at least log, n steps will occur before the process terminates. Each step adds a node to one of the piles, so one of the piles ends up with at least log, n nodes. The A pile contains the nodes of a clique and the B pile contains the nodes of an anti-clique