Graphs Flashcards
Define a graph
Defined by G = (V,E)
V is a set of nodes (or vertices) in the graph
E is the set of edges where E is a subset of V x V
What is the degree of a node?
The number of edges incident on a node
What is a path?
A sequence of nodes and edges that link two nodes
Define the path length
Number of edges in a path
What is a sub graph?
Sub set of the original nodes and edges, all nodes touched by an edge are included in the sub graph
What does it mean for a graph to be connected?
A graph is connected if there is a path between every pair of nodes
What are the two types of connectedness in directed graphs?
Weakly connected
Strongly connected
What is a weakly connected directed graph?
When the graph is connected if we ignore the directions of edges
What is a strongly connected directed graph?
When the graph is connected and we respect the directions
What are the three choices of representation for graphs?
Finite state machines
Trees
Hash table
What are the operations we expect from graphs?
Add and remove nodes and edges
Get and set labels
Enumerate elements
Traverse an edge
What are the three ways we could represent the structure of a graph?
Edge list
Adjacency list
Adjacency matrix
How is the graph represented in an edge list?
Node list
Edge list
What information is stored on a node object in an edge list?
Label
Position in node list
What information is stored on an edge object in an edge list?
Label
Position in edge list
End points
