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 𝐺𝐺.