Unit 4 - Practice Quiz

In graph theory, a graph is defined as an ordered pair G = (V, E), where V is the set of vertices (or nodes) and E is the set of edges that connect pairs of vertices.

The degree of a vertex, denoted as deg(v), is the count of edges connected to that vertex. By convention, a loop is counted twice.

A complete graph, denoted as for n vertices, is a simple undirected graph where every distinct pair of vertices is adjacent. It has the maximum possible number of edges for a simple graph with n vertices.

An adjacency matrix A for a simple graph is a square matrix where the entry is 1 if an edge exists between vertex i and vertex j, and 0 otherwise.

A graph is connected if for any two vertices u and v, there exists a path from u to v. This means the graph is a single component.

Dijkstra's algorithm is a fundamental algorithm for solving the single-source shortest path problem in a weighted graph, provided the edge weights are non-negative.

A necessary condition for two graphs to be isomorphic is that they must have the same number of vertices and the same number of edges. This is a basic structural property that must be preserved.

The definition of a bipartite graph is that its vertex set can be partitioned into two sets where no two vertices within the same set are adjacent. Therefore, all edges must go between the two sets.

In an undirected graph, if there is an edge between vertex i and vertex j, there is also an edge between j and i. This means the adjacency matrix A will have , which is the definition of a symmetric matrix.

A simple path is defined as a path in a graph where no vertices are repeated. If the start and end vertices are the same and no other vertices are repeated, it is a simple cycle.

A loop, also known as a self-loop, is an edge that starts and ends on the same vertex. Simple graphs do not have loops.

A graph is k-regular if every vertex has a degree of k. If all vertices have the same degree, regardless of what that degree is, the graph is called regular.

An incidence matrix relates vertices to edges. It is typically an matrix where rows correspond to vertices and columns correspond to edges. An entry (i, j) is 1 if vertex i is an endpoint of edge j, and 0 otherwise.

A cycle graph consists of n vertices connected in a closed chain. Each vertex is connected to two others, forming a single cycle. This structure results in exactly n edges, one for each vertex in the cycle.

Dijkstra's algorithm works by greedily selecting the vertex with the smallest known distance. This greedy choice is only guaranteed to be optimal if paths can never be shortened by adding more edges, which requires all edge weights to be non-negative.

A directed graph is strongly connected if for every pair of distinct vertices (u, v), there is a path from u to v and also a path from v to u. This is a much stronger condition than simple connectivity.

A graph invariant is a property that depends only on the abstract structure of the graph. The degree sequence (the multiset of vertex degrees) is one such property. If two graphs are isomorphic, they must have the same degree sequence.

A complete bipartite graph has its vertex set partitioned into two subsets of size m and n. The total number of vertices is . Every vertex in the first set is connected to every vertex in the second set, so there are edges in total.

A diagonal entry represents an edge from vertex i to itself. By definition, such an edge is a loop. For a simple graph, which has no loops, all diagonal entries are 0.

A wheel graph is constructed from a cycle graph by adding a new, central vertex and connecting it to all n vertices of the cycle. Therefore, has vertices.

In a complete bipartite graph , every vertex in the set of vertices is connected to every vertex in the set of vertices. Thus, the total number of edges is . The n-cube graph has vertices, and it is an -regular graph (each vertex has degree ). By the handshaking lemma, the sum of degrees is , so , which gives .

The entry in the matrix gives the number of different paths of length from vertex to vertex . Therefore, for , the entry represents the number of paths of length 2 between vertex and vertex . A path of length 2 from to must go through an intermediate vertex , such that . The number of such paths is the number of common neighbors.

1. Start at S. Distances: S=0, A=, B=, C=. Finalize S.
2. Update neighbors of S: dist(A)=2, dist(B)=5. Smallest distance is A(2). Finalize A.
3. Update neighbors of A: dist(B)=min(5, 2+1)=3, dist(C)=2+4=6. Smallest unsettled distance is B(3). Finalize B.
4. Update neighbors of B: dist(C)=min(6, 3+2)=5. Finalize C.
   The order of finalization is S, A, B, C.

Isomorphic graphs must have the same number of vertices, same number of edges, and the same degree sequence. These are necessary conditions. However, having the same degree sequence is not sufficient. For example, two non-isomorphic graphs can have the degree sequence (2, 2, 2, 2, 2, 2): a cycle and two disjoint triangles (). The bijection preserving adjacency is the definition of isomorphism, so it's both necessary and sufficient.

The question asks for the edge connectivity of . A wheel graph (for ) always has a minimum degree of 3 (the vertices on the cycle). The central hub has degree . The edge connectivity of a graph is always less than or equal to its minimum degree. In , the minimum degree is 3. By removing the 3 edges incident to any vertex on the outer cycle, that vertex becomes isolated, disconnecting the graph. Therefore, the edge connectivity is 3.

In the adjacency matrix of a directed graph, an entry is 1 if there is an edge from vertex to vertex , and 0 otherwise. Each directed edge corresponds to exactly one '1' in the matrix. Therefore, the sum of all entries in the adjacency matrix is equal to the total number of edges, which is .

Let's analyze the options:

• The cube graph has vertices and is 3-regular. This matches the description.
• The wheel graph has vertices.
• The complete graph is 7-regular.
• The cycle graph is 2-regular.
  Therefore, the only graph that is 3-regular and has 8 vertices is .

The handshaking lemma states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges (). The right side, , is always an even number. The sum on the left can be split into the sum of degrees of even-degree vertices and the sum of degrees of odd-degree vertices. The sum of even degrees is even. For the total sum to be even, the sum of odd degrees must also be even. This is only possible if there is an even number of odd-degree vertices.

In a directed cycle, you can travel from any vertex to any other vertex by following the cycle's direction, and you can get back by continuing along the cycle until you loop around. A DAG, by definition, has no cycles, so you cannot have a path from back to if there is a path from to . A directed path only allows one-way travel. The complete graph with ordered directed edges is also a DAG.

A graph is bipartite if and only if it contains no odd-length cycles. A cycle graph is itself a cycle of length . Therefore, is bipartite if and only if its length, , is even. Among the given options, only is an even number.

Dijkstra's algorithm is a greedy algorithm that assumes that once a vertex is finalized (marked as visited), its shortest path from the source has been found. This assumption holds only if all edge weights are non-negative. If there's a negative edge, the algorithm might finalize a vertex too early, because a shorter path might be found later via a path that includes the negative edge. For graphs with negative edges, algorithms like Bellman-Ford are required.

is a 2-regular graph, so its degree sequence is (2, 2, 2, 2, 2, 2). has two vertices with degree 1 (the endpoints) and four vertices with degree 2. Its degree sequence is (1, 1, 2, 2, 2, 2). Since isomorphic graphs must have the same degree sequence, and these are different, the graphs are not isomorphic. Both have 6 vertices, are connected, but has 6 edges while has 5, so different number of edges is also a valid reason, but the degree sequence is a more fundamental structural property.

An incidence matrix is typically defined with rows corresponding to vertices and columns to edges. The entry is 1 if vertex is an endpoint of edge , and 0 otherwise. When we sum the entries across a single row (for a specific vertex), we are counting how many edges are incident to that vertex. This is precisely the definition of the degree of that vertex.

An adjacency matrix for a graph with vertices always uses space. An adjacency list uses space, where is the number of edges. In a dense graph, is close to . Therefore, the space complexity of an adjacency list becomes , which is the same as the adjacency matrix. However, the adjacency matrix has lower overhead per entry and is often simpler and faster for edge lookups in dense graphs, making it the preferred choice for efficiency.

This is a direct application of Turan's Theorem. The theorem states that the maximum number of edges in an -vertex graph that does not contain a subgraph is achieved by the Turan graph . For a triangle-free graph, we want to avoid , so . The graph that maximizes edges is a complete bipartite graph with partitions as balanced as possible. For , we split the vertices into two sets of size 5. The number of edges in the complete bipartite graph is .

An adjacency matrix is symmetric if , which means for all . In the context of a graph, means there is an edge from to . Symmetry means that if there is an edge from to , there must also be an edge from to . This is the definition of an undirected edge. Therefore, a symmetric adjacency matrix represents an undirected graph.

The vertex connectivity is the minimum number of vertices that must be removed to disconnect the graph or reduce it to a single vertex. In a complete graph , every vertex is connected to every other vertex. If you remove any set of vertices where , the remaining vertices still form a complete graph , which is connected. To disconnect the graph, you must remove all other vertices, leaving a single vertex behind. Therefore, the vertex connectivity is .

1. Start at A. Distances: A=0, B=, C=, D=. Finalize A.
2. Update neighbors of A: dist(B)=1, dist(C)=4. Smallest is B(1). Finalize B.
3. Update neighbors of B: dist(C)=min(4, 1+2)=3, dist(D)=1+5=6. Smallest is C(3). Finalize C.
4. Update neighbors of C: dist(D)=min(6, 3+1)=4. Finalize D.
   The shortest path to D is A -> B -> C -> D with a total weight of 1 + 2 + 1 = 4.

Let have vertices and edges. Its complement has edges. If is isomorphic to , they must have the same number of edges. So, , which implies , or . Since is a multiple of 4, must also be a multiple of 4.

• If is a multiple of 4 (), then is a multiple of 4. So .
• If is a multiple of 4 (), then is a multiple of 4. So .
  If or , then is not a multiple of 4. Thus, must be congruent to 0 or 1 mod 4.

A graph is bipartite if it does not contain any odd-length cycles.

• The wheel graph consists of a cycle and a central hub vertex connected to all vertices of the cycle. This creates triangles (cycles of length 3), for example, between the hub and any two adjacent vertices on the cycle. Since it has odd cycles, it is not bipartite.
• (the hypercube) is always bipartite.
• is an even cycle, so it is bipartite.
• is bipartite by definition.

The entry of the matrix gives the number of walks of length from vertex to vertex . The trace, , is the sum of the diagonal elements, . Each represents the number of walks of length 3 starting and ending at vertex . A walk of length 3 from to is a cycle , which is a triangle. Each triangle involving vertices is counted 6 times in the trace: once for each vertex () and for each direction of traversal (e.g., and ). Therefore, .

Adding a constant to each edge weight penalizes paths with more edges more heavily. Let a path have length and edges, and path have length and edges. In , we might have . In , their new lengths are and . If , it's possible that . For example, a path with weights (1, 1, 1) is shorter than a path with weight (4). If , the new paths are (3, 3, 3) with total 9, and (6). The shorter path has changed. Therefore, the shortest path is not guaranteed to be the same.

Let be a self-complementary graph with vertices and edges. The number of edges in its complement is . Since is isomorphic to , they must have the same number of edges. Thus, , which implies , so . Since the number of edges must be an integer, must be divisible by 4. If is of the form or , then is divisible by 4. If , , which is not divisible by 4. If , , which is not divisible by 4. Thus, must be of the form or .

All three connectivity measures can be different. Consider the following counterexample graph: Take two copies of (complete graph on 5 vertices). Let's call them and . Add a new vertex . Connect to 2 vertices in and 2 vertices in . Now, the minimum degree is 4 (the vertices in and that are not connected to ). The vertex connectivity is 1, because removing disconnects the graph. The edge connectivity is 2, because removing the two edges from to (or ) disconnects from a part of the graph. In this constructed example, we have , , and . Thus, it is possible for all three to be different and satisfy .

A 4-cycle in an -cube corresponds to a 2-dimensional sub-cube. To form a 2-dimensional sub-cube, we must choose 2 dimensions out of to vary, and fix the remaining dimensions. There are ways to choose the two dimensions that will vary. For the remaining dimensions, the bit values can be fixed in ways. Each such choice defines a unique 4-cycle (a square face of the hypercube). Therefore, the total number of 4-cycles is .

We want to maximize the product . Maximizing is equivalent to maximizing , since log is a monotonically increasing function. . Maximizing this sum is equivalent to minimizing its negative: . Since each , its logarithm is non-positive (), so is non-negative (). We can therefore use Dijkstra's algorithm by transforming each edge weight to a new weight . The shortest path in this transformed graph will correspond to the most reliable path in the original graph.

The condensation graph has the strongly connected components (SCCs) of as its vertices. An edge exists from SCC to if there's an edge in from a vertex in to a vertex in . The condensation graph is always a DAG. The condition given is that the graph is 'semi-connected'. This implies that if we consider any two SCCs, and , there must be a path between them in one direction in . Since is a DAG, it cannot have paths in both directions. Therefore, the SCCs can be linearly ordered such that there is a path from to if and only if . This structure is a simple directed path (or more precisely, a transitive tournament, which has a Hamiltonian path).

If and are isomorphic, it means there exists a permutation of vertices of that results in . This translates to the existence of a permutation matrix such that (or since for permutation matrices). This is a similarity transformation. A fundamental property of similar matrices is that they have the same characteristic polynomial, and therefore the same eigenvalues (the spectrum of the graph). While options C and D are also true (they relate to the number of edges, which is an isomorphism invariant), having the same eigenvalues is a much stronger and more fundamental spectral property. Option A is only true if the vertex labeling is identical, which is not required for isomorphism.

Let the number of vertices in the four components be and the number of edges be . We know and . A tree with vertices has exactly edges. Since the first three components are trees, we have , , and . The total number of edges in these three components is . The total number of edges in the graph is . Substituting, we get . We also know that , so . Substituting this into the edge equation: , which simplifies to , so . The fourth component must be connected, so it must have at least edges. The minimum number of vertices in a component is 1. If , , impossible for a single vertex. If , , impossible. The number of edges in a simple graph with vertices is at most . We need to find where . The total vertices are 12, and the first three components (trees) must have at least 1 vertex each, so . Testing values for , we find that for , , but . For , , and . This is a valid solution. However, this is too complex. The logic must be simpler. Let's re-evaluate. The number of edges in the first three components is . Total edges . Total vertices . From the vertex equation, . Substitute this into the edge equation: . The number of vertices in the first three components must be at least 1. So . This means . The number of edges in the fourth component is . Since it's a connected component, . Wait, there's a property relating vertices, edges, and components: . Here . This is true. The number of edges 'wasted' (above the minimum for connectivity) is . This 'excess' of 10 edges must reside in the components that are not trees. Since only the fourth component is not a tree, it must contain all 10 excess edges. A tree component has . A non-tree component has . The number of edges in a component can be written as , where is the cyclomatic number (number of fundamental cycles). For a tree, . So, . We have . Since components 1, 2, 3 are trees, . So , which means . The number of edges in the fourth component is . The question asks for , not . The question is flawed. Ah, let's re-read. It asks for the number of edges, not cycles. My logic was correct until the last step. The mistake is in the interpretation. Let's restart. The total number of edges required to make components into spanning trees is . Here, . The graph has 18 edges. So there are 'extra' edges. Since the first three components are trees, they have no extra edges. All 10 extra edges must be in the fourth component. So the number of edges in the fourth component is (edges to make it a tree) + (10 extra edges). Let the fourth component have vertices. Its edges are . This is what I got before. This still doesn't give a number. Let's reconsider the problem statement. Is there an unstated assumption? Maybe the components are non-trivial? No. The logic must be simpler. Let's try again. . . . Substitute: . From the vertex sum, . So . This relationship is fixed. What is ? The question seems unanswerable. Let me re-read the topic. "graph terminologies". Perhaps there is a simple theorem I'm missing. Okay, let's rethink the structure of my explanation. The number of 'excess' edges in a graph with vertices, edges, and components is . These excess edges are distributed among the components. For a component , its excess is . The total excess is . We are given (since they are trees). Thus, the total excess . . So . This means . The question asks for . It is not uniquely determined. Let me create a better question for this topic. NEW Q:

The complexity of Dijkstra's is dominated by two operations: vertex extraction from the priority queue (Extract-Min) and updating distances (Decrease-Key). There are extractions and updates.\n- Binary Heap: Extract-Min is , Decrease-Key is . Total: . For a dense graph, this is .\n- Fibonacci Heap: Extract-Min is , Decrease-Key is amortized. Total: . For a dense graph, this is .\n- Simple Array: To find the minimum, we scan the whole array, so Extract-Min is . Decrease-Key is . Total: . For a dense graph, this is .\nComparing the Fibonacci Heap () and the Simple Array () for a dense graph (), both yield complexity. However, the simple array implementation is much easier and has lower constant factors, making it the preferred and most efficient choice for dense graphs.