Graph Theory Basics Quiz

Graph ADT: Adjacency Matrices

• A graph of 𝑛𝑛 nodes can be represented as a two-dimensional array called adjacency matrix.
• Let 𝐺𝐺 be the undirected graph corresponding to an adjacency matrix 𝐴𝐴.
• An edge in 𝐺𝐺 between nodes 𝑖𝑖 and 𝑗𝑗 exists if 𝐴𝐴 𝑖𝑖 𝑗𝑗 = 1 for row 𝑖𝑖 and column 𝑗𝑗.
• No edge in 𝐺𝐺 between nodes 𝑖𝑖 and 𝑗𝑗 exists if 𝐴𝐴 𝑖𝑖 𝑗𝑗 = 0 for row 𝑖𝑖 and column 𝑗𝑗.
• Adjacency matrix is symmetric for undirected graphs, meaning 𝐴𝐴 𝑖𝑖 𝑗𝑗 = 𝐴𝐴 𝑗𝑗 𝑖𝑖 for 𝑖𝑖 ∈ {1, … , 𝑛𝑛} and 𝑗𝑗 ∈ {1, … , 𝑛𝑛}.
• For an undirected graph, two cells are always modified when we add or remove an edge.

Graph ADT

• The Graph ADT supports adding and removing both nodes and edges, checking if two nodes are adjacent, and getting the neighbors of one node.
• The Graph ADT methods include:
  • void addNode(Node 𝒏𝒏)
  • void removeNode(Node n)
  • void addEdge(Node n, Node m)
  • void removeEdge(Node n, Node m)
  • boolean adjacent(Node n, Node m)
  • Node[] getNeighbours(Node n)
• Semantics: Nodes are identified by values (names) so add_edge and rem_edge can find the nodes being referred to.

Graph ADT: List-based Implementation

• The GraphNode class represents a node in the graph, with a label (id) and a set of edges.
• The GraphList class represents the graph, with a head node and methods to add and remove nodes and edges.

Graph ADT: Adding and Finding Nodes

• The addNode method adds a new node to the graph, with a given label.
• The findNode method finds a node in the graph by its label.

Graph ADT: Adding and Removing Edges

• The addEdge method adds a new edge between two nodes, by adding the nodes to each other's edges.
• The removeEdge method removes an edge between two nodes, by removing the nodes from each other's edges.

Graph ADT: Removing a Node

• The removeNode method removes a node from the graph, by removing all edges to and from the node and then removing the node from the list.

Graph ADT: Get Neighbors and Adjacency

• The getNeighbors method returns an array of nodes that are neighbors of a given node.
• The adjacent method checks if two nodes are adjacent.

Graph ADT: Displaying the Graph

• The print method prints the graph, showing each node and its neighbors.

Graph ADT: Implementation Cost

• The memory complexity of the list-based implementation is 𝑂𝑂(𝑁𝑁 + 𝐸𝐸) for graphs with 𝑁𝑁 nodes and 𝐸𝐸 edges.
• The time complexity of the list-based implementation includes:
  • Adding a node: 𝑂𝑂(1)
  • Removing a node: 𝑂𝑂(𝑁𝑁)
  • Finding/accessing a node: 𝑂𝑂(𝑁𝑁)
  • Adding and removing an edge: 𝑂𝑂(𝑁𝑁)
  • Adjacency check: 𝑂𝑂(𝑁𝑁)

Graphs

• A graph can be directed or undirected.
• Undirected edges can be traversed in both directions, while directed edges can only be traversed in the indicated direction.
• A subgraph 𝑆𝑆 of a graph 𝐺𝐺 is a subset of the nodes and edges of 𝐺𝐺.
• A subgraph 𝑆𝑆 is a spanning subgraph of 𝐺𝐺 if it is formed from all nodes of 𝐺𝐺 and some of the edges of 𝐺𝐺.

Test your knowledge on the basics of graph theory including nodes, edges, directed and undirected graphs, subgraphs, and graph traversal.