Graphs terminology Flashcards
Undirected graph
A non-empty graph where the edges do not have a specified direction
Directed graph (digraph)
A non-empty graph where the edges have a specified direction
Source
Digraph - where an edge starts
Sink
Digraph - where an edge ends
Subgraph
A subset of the vertices and edges in a graph
undirected -> directed
Assing a directionality, then give each edge an additional symetric edge
directed -> undirected
Remove the directionality of each edge, then remove duplicate edges
Weighted graph
Graph with real-valued weights assigned to the edges - stored instead of bools in adjacency list/matrix
Adjacency (undirected)
Two nodes are adjacent if they are connected by an edge
Adjacency (directed)
Node A is adjacent to node B if there is an edge from B to A.
Generally, a node is adjacent to another node if the first node has an inbound edge from the second node
Connected
(undirected) A path exists from every node to every other node
Weakly connected
(dircted) A path exists from every node to every other node ignoring directionality
Strongly connected
(directed) A path exists from every node to every other node taking directionality into account
Complete
Every node has an edge to every other node
Clique
A complete subgraph containing two or more nodes
Maximum clique
The largest clique of a given graph
Maximal clique
A clique that is not a part of a larger clique
Acyclic
A graph that does not contain any cycles (non-self loops)
In-degree
(directed) The number of incoming edges to a node
Out-degree
(directed) The number of outgoing edges from a node
Reflexive
All nodes have self loops
Irreflexive
No nodes have self loops
Symmetric
(directed) All edges are reciprocated
Anti-symmetric
(directed) No edge is reciprocated (does not exclude self loops)
Transitive
If a path exists between two nodes, there must be an edge directly linking them
path
The route(s) from one node to another
Subpath
A section of a path
Path length (weighted)
The combined/total weight/cost of traversing a given path
Settled
Refers to Dijsktra’s: The shortest path to this node from the starting node has been found
Frontier
Refers to Dijsktra’s: Just discovered this node, working on confirming the shortest path
Unexplored
Refers to Dijsktra’s: The algorithm has not seen this node yet
