Vertices and Edges

Vertices

Adjacent
Pair connected by an edge
Neighborhood
Vertices adjacent to a vertex
Cut/Articulation
Block-Cut vertex interfacing Trees

Edges

Walk
Adjacency Sequence (⇒ Subgraph).
Trail
Walk, distinct edges
Eulerian Trail
Walk on every edge once (⇒ Trail).
Path
Walk, distinct vertices (⇒ Trail).
Hamiltonian Path
Walk on every vertex once (⇒ Path).
Induced Path
Path being an induced graph
Bridge/Cut-Edge
Edge not in cycle, removal of which increases the number of CCs.
Matching
Set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share common vertices.

Graphs and Subgraphs

Graphs

Complete
All Vertices Adjacent
Directed/Digraph
Graph with Directed Edges
Acyclic
No cycles. DAG: Directed & Acyclic
Rooted
All paths stem from single Root edge
Complete
All pairs of vertices are edges
Edgeless
No pairs of vertices are edges
Bipartite
Nodes form two independant sets
Matchstick
Planar, with all edges length one
Scale-Free
Power-Law degree distribution (asymptotically: fraction of nodes having k connections P(k) ∼ k−γ)
Line-Graph
Graph dual from original, edges becoming vertices, and common endpoint vertices becoming edges.

Subgraphs

Induced Subgraph
G'=(V',E'), V' subset of V, E' from (u,v) of E when both in V'
Independant Set
G'=(V',{}), V' subset of V, where no (u,v) is in E when both in V'
Clique
G'=(V',E'), V' subset of V, where (u,v) is in E when both in V'
Connected Component
Connected Sub. not part of another Block/Biconnected Component
SCC
Min. vertex cluster producing a DAG, when shrinked to a point
WCC
Min. vertex cluster producing a Path, when shrinked to a point

Common Graphs Taxonomy

    graph TD
      Directed --> DAG
      Acyclic --> DAG
      DAG --> Tree
      Rooted --> Tree
      Graph --> Directed
      Graph --> Acyclic
      Graph --> Rooted

Common Trees Taxonomy

  graph TD
    Tree --> Out-Tree
    Tree --> In-Tree
    In-Tree --> Binary-Tree
      Binary-Tree ----> BST
        BST --> Red-Black
        BST --> Treap
        BST --> AVL
      Binary-Tree --> Trie
        Trie --> Radix-Tree
    In-Tree --> Star
        Star --S3--> Claw

Complements / Inverses

A graph complement or inverse is made from the original, by flipping all values in the adjacency matrix.

Duals under Inversion
Clique Independant Set
Complete Edgeless

Morphisms and Algorithms

Algorithm Provides result Cond.
Edge preserving bijection (u,v)∈E ⇔ (f(u),f(v))∈E'
Dijkstra s → shortest(s,v) ∀v∈V P
Bellman-Ford s → shortest(s,v) ∀v∈V D
Floyd-Warshall shortest(v,w) ∀(v,w)∈V² D
Tarjan's strongly connected comp. DA
Prim's {e} min. span. tree C
Kruskal's {e} min. span. tree
Gabriel Graph (p,q)∈E ⇔ ⊙(pq)=Ø E
Delaunay Triangulation(p,q)∈E ⇔ ⊙△(pqr)=Ø ∀r∈V E
P Positive weights
D Only if Directed
C Only if Connected
A Only if Acyclic
E Euclidean Embedding

Graph serialization

  graph LR
    A --> B --> C --> D
    B --> D --> A --> C

G = (V, E), or directly E

Straightforward Vertices / Edges iteration, as the mathematical notation. The Vertices are not needed, they can be recovered in O(1) 
   E = ((A, B), (B, C), (C, D), 
        (B, D), (D, A), (A, C))

Adjacency Matrix

Good for dense graphs. Slow to remove vertices and edges, because it needs to find them, and to add or remove vertices and edges because the matrix must be resized, copied. 
   M = [[0, 1, 1, 0],
        [0, 0, 1, 1],
        [0, 0, 0, 1],
        [1, 0, 0, 0]]

Adjacency List

Fast access by indices, easy implementation, low memory requirement, efficient for dense small graphs. 
    L = [[A, B, C, D], [B, D, A, C]]

Tree serialization

  graph LR
    A --> B --> C --> D
    B --> E --> F
Tree DAG/Root properties provide alternatives, in addition to the universal Graph serialization schemes.

Nested

Represented recursively a mapping syntax, from branch IDs, to either leaves, or another level. For example, XML, JSON, YAML, etc. 
  A/ { B/ { C/ { D }, E/ { F }}}

Paths

Flat version of the Nested representation, where all keys list branch ID separated by a marker, to the leaves. Easier to process for some tasks, less efficient since there is repetition in each path. 
  A/B/C/D
  A/B/E/F