Exercises: Unit 12 — Graph Theory

An undirected graph has vertices {A, B, C, D, E} and edges {AB, AC, AD, BC, CD, DE}.

List all simple paths of length 3 that start at vertex A. (A simple path never visits a vertex twice, and its length is its number of edges.)

An undirected graph has vertices {A, B, C, D, E} and edges {AB, AC, BC, BD, CD, CE, DE}.

How many cycles does the graph contain? Count as ACSL's Elementary handout does: a cycle travelled in each of its two directions counts as two cycles (ABCA and ACBA), but starting the same loop at a different vertex does not make a new cycle (ABCA and BCAB are the same).

An undirected graph has vertices {A, B, C, D, E, F} and edges {AB, AC, AF, BC, CD, CE, CF, DE}.

What is the degree of vertex C?

An undirected graph has vertices {A, B, C, D, E} and edges {AB, AE, BC, BD, CD, DE}.

Is the graph traversable, that is, can you travel along every edge exactly once without lifting your pencil? Answer YES or NO.

A complete graph has 9 vertices. How many edges does it have?

An undirected graph has vertices {A, B, C, D, E} and edges {AB, AD, BC, BD, CE, DE}.

List all simple paths from vertex B to vertex E, of any length.

An undirected graph has vertices {A, B, C, D, E} and edges {AB, BC, BD, CD, DE}.

How many simple paths of length 2 does the graph contain in all? A path and its reverse are different paths: ABC and CBA count as two.

An undirected graph has vertices {A, B, C, D} and edges {AB, AC, BC, BD, CD}.

List all the cycles that start and end at vertex C. Write each one from C back to C, and list a cycle once for each direction it can be travelled (so both CABC and CBAC are on the list).

An undirected graph has vertices {A, B, C, D, E, F} and edges {AB, AC, BC, DE, DF, EF}.

Is the graph traversable, that is, can you travel along every edge exactly once without lifting your pencil? Answer YES or NO.

A directed graph has vertices {A, B, C, D, E} and edges {AB, BC, CA, CD, DC, DE, EB, EA}.

How many different cycles does the graph contain? A cycle must follow the direction of the edges, and each cycle is counted once, whichever vertex it is written from.

An undirected graph has vertices {A, B, C, D, E} and edges {AB, AE, BC, BE, CD, CE, DE}.

How many different cycles does the graph contain? Count each cycle once: ABEA, AEBA and BEAB are all the same cycle.

A directed graph has vertices {A, B, C, D} and edges {AB, AC, BC, BD, CA, CD, DA}.

How many paths of length 2 go from A to D? A path follows the direction of the edges and may repeat vertices, as the entries of M² count them.

A directed graph has this adjacency matrix, where the entry in row i and column j is 1 when there is an edge from i to j:

How many paths of length 3 go from C back to C? A path follows the direction of the edges and may repeat vertices, as the entries of M³ count them.

An undirected graph has vertices {A, B, C, D, E} and edges {AB, AC, BC, BD, DE}.

How many paths of length 2 start at vertex B? A path may end anywhere, and it may repeat vertices and go back along the edge it came by (so BAB counts), as the entries of M² count them.

An undirected graph has vertices {A, B, C, D, E, F, G, H, I} and edges {AE, BG, CE, DF, GH}.

How many connected components does the graph have?

A forest is made of separate trees. It has 15 vertices and 11 edges in all.

How many trees is it made of?

The first line of input is UNDIRECTED or DIRECTED. The second line holds the vertex letters, in alphabetical order, run together (such as ABCD). The third line holds the edges, separated by single spaces, each written as two letters (such as AB); in a directed graph AB goes from A to B.

Print the adjacency matrix, one row per line, with the entries of each row separated by single spaces. The rows and the columns follow the order of the second line. Then print one line for each vertex, in the same order: its letter, the number of 1s in its row, and the number of 1s in its column, separated by single spaces. (For an undirected graph both numbers are the degree; for a directed graph they are the out-degree and the in-degree.)

Constraints

• There are between 2 and 10 vertices, and between 1 and 30 edges.
• No edge joins a vertex to itself, and no edge appears twice. In an undirected graph, AB and BA never both appear.
• A vertex may have no edges at all.
• The two letters of an undirected edge can come in either order (DA is the edge between A and D).

Sample Input

DIRECTED
ABCD
AB AD BA BD CA DB DC

Sample Output

0 1 0 1
1 0 0 1
1 0 0 0
0 1 1 0
A 2 2
B 2 2
C 1 1
D 2 2

The edges AB and BA are two different edges, one each way.

The first line of input holds the vertex letters of a directed graph, in alphabetical order, run together. The second line holds its edges, separated by single spaces; AB goes from A to B. The third line holds two vertex letters X and Y, separated by a space.

Print two lines: the number of paths of length 2 from X to Y, and then the number of paths of length 3 from X to Y. A path follows the direction of the edges and may repeat vertices and edges, as the entries of M² and M³ count them.

Constraints

• There are between 2 and 10 vertices, and between 1 and 40 edges.
• No edge joins a vertex to itself, and no edge appears twice.
• X and Y may be the same vertex; then the paths go from X back to X.

Sample Input

ABCD
AB AC BC BD CA CD DA
A D

Sample Output

2
1

The two paths of length 2 are ABD and ACD, and the path of length 3 is ABCD.

An undirected weighted graph has vertices {A, B, C, D, E, F} and edges {AB4, AC2, BC1, BD5, CD8, CE10, DE2, DF6, EF3}, where the number after an edge is its weight (AB4 joins A and B with weight 4).

What is the smallest total weight of a path from A to F?

Each option is a directed graph, given by its edge set.

• (A) {AB, BC, CA}
• (B) {AB, AC, BD, CD}
• (C) {AB, BC, CD, DB}
• (D) {AD, BA, BC, CD}
• (E) {AB, BA}

Which options are DAGs (directed graphs with no cycles)? (The option labels are only names; they have nothing to do with the vertices A, B, … inside the edge sets.)

An undirected graph has vertices {A, B, C, D, E} and edges {AB, AC, BC, CD, CE, DE}.

How many different spanning trees does it have? Two spanning trees are different when they do not use exactly the same edges.

A directed graph has vertices {A, B, C, D} and edges {AA, AB, AC, BC, CA, CD, DB}. The edge AA is a loop from A back to A, and a path may use it.

How many paths from A to D have length 2, 3 or 4? Give the total of all three lengths. A path follows the direction of the edges and may repeat vertices and edges, as the entries of M^p count them.

The first line of input holds the vertex letters of an undirected weighted graph, in alphabetical order, run together. The second line holds its edges, separated by single spaces. Each edge is two vertex letters followed by its weight, a whole number, such as AB4 or CE12. The third line holds two different vertex letters X and Y, separated by a space.

Print the smallest total weight of a path from X to Y. If there is no path from X to Y at all, print NONE.

Constraints

• There are between 2 and 8 vertices, and between 1 and 20 edges.
• Every weight is between 1 and 99.
• No edge joins a vertex to itself, and no two edges join the same pair of vertices.

Sample Input

ABCD
AB3 AC1 BC1 BD4 CD6
A D

Sample Output

6

This is Example 5 of Lesson 2: the cheapest path is ACBD, with weight 1 + 1 + 4.

A directed graph has vertices {A, B, C, D} and edges {AB, AD, BC, CA, CD, DA, DB}.

List every cycle that passes through vertex A, each written from A back to A. A cycle must follow the direction of the edges.

A directed graph has vertices {A, B, C, D} and edges {AB, BC, CA, CD, DB}. Then two edges, AD and DA, are added.

How many more paths of length 3 start at vertex A after the two edges are added than before? A path may end at any vertex, follows the direction of the edges, and may repeat vertices and edges, as the entries of M³ count them.

The first line of input holds the vertex letters of a directed graph, in alphabetical order, run together. The second line holds its edges, separated by single spaces; AB goes from A to B.

Print the number of different cycles in the graph. A cycle follows the direction of the edges, visits no vertex twice except that it ends where it started, and is counted once, whichever vertex it is written from. A cycle may have just two vertices: ABA is a cycle when both AB and BA are edges.

Constraints

• There are between 2 and 8 vertices, and between 1 and 30 edges.
• No edge joins a vertex to itself, and no edge appears twice.
• The graph may have no cycles at all; then print 0.

Sample Input

ABCDE
AB BA BC CD DC DB DE

Sample Output

3

This is ACSL's wiki sample: the cycles are ABA, BCDB and CDC.