Graphs and Their Representations Flashcards
What is a graph in computer science?
A graph is a mathematical object modeling a binary relation over a finite set, consisting of vertices (nodes) and edges (connections).
What are the components of a graph?
Vertices (nodes) and edges (links between nodes).
What is a directed graph (digraph)?
A graph where edges have direction, representing asymmetric relationships.
What is an undirected graph?
A graph where edges are bidirectional, representing symmetric relationships.
How is an edge drawn in an undirected graph?
As a straight line without an arrow.
What two features are excluded in graphs for this class?
Self-loops and multi-edges.
What is a self-loop in a graph?
An edge that connects a vertex to itself.
What are multi-edges in a graph?
Multiple edges between the same two vertices.
Give examples of real-world systems modeled as graphs.
- Computer networks
- Social networks
- Ecological networks
- Electrical circuits
- Programs
- Mapping systems like Google Maps.
What do nodes and edges represent in a computer network graph?
Nodes are servers; edges are communication links.
What do nodes and edges represent in a social network graph?
Nodes are people; edges are social relationships (e.g., friendships).
Name some common problems solved using graph algorithms.
- Graph traversal
- Cycle detection
- Node ranking
- Shortest path finding
- Spanning trees
- Flows.
What is an adjacency matrix?
A square matrix where each cell A[i][j] is 1 if there is an edge from node i to node j, otherwise 0.
What is the space complexity of an adjacency matrix?
O(n^2), where n is the number of vertices.
Why is the adjacency matrix inefficient for sparse graphs?
Because most entries are zero, wasting space.
What is an adjacency list?
A list where each node points to a list of its adjacent (neighbor) nodes.
What is the space complexity of an adjacency list?
O(n + m), where n is the number of vertices and m is the number of edges.
When should you use an adjacency list over a matrix?
When the graph is sparse.
What is the incidence matrix (briefly mentioned)?
A node-edge matrix that connects graph theory with linear algebra (e.g., graph Laplacian).
What is graph sparsity?
When a graph has far fewer edges than the maximum possible, which is common in real-world graphs.
Why are real-world graphs often sparse?
Most entities (e.g., people or servers) connect to only a limited number of other entities.
