1.6. Data Structures to Represent Graphs

Try these first

1. 1.

   What is an adjacency matrix?

   Hint

   Think of it as a grid or table showing connections.

2. 2.

   Define a proper subgraph.

   Hint

   Remember, it's 'proper' because it’s less than the complete graph.

3. 3.

   What structure is preferred for representing dense graphs?

   • Adjacency List
   • Incidence Matrix
   • Adjacency Matrix

   Hint

   Think about how many edges a dense graph has.

4. 4.

   True or False: A cut vertex upon removal will always lead to increased graph connectivity.

   • True
   • False

   Hint

   Consider what happens if you take away an important point.

5. 5.

   Given three graphs, determine if any pairs are isomorphic by analyzing their vertex-degree sequences and connectivity.

   Hint

   Start by writing down the degree of each vertex for each graph.

6. 6.

   Construct a graph using an adjacency list and then derive the corresponding adjacency matrix. Verify the correctness of your transformations.

   Hint

   Ensure all neighbors are correctly noted from the list to the matrix.