graph

Graph

A graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$ between them. An edge $e_{ij}$ connects vertex $v_i$ with vertex $v_j$.

Terminology

An edge is incident to a vertex if it is directly connected.
Two (distinct) edges are adjacent if they share a vertex.
An induced subgraph is a subset of a graph that includes all the vertices of a given subset, along with every edge that exists between them in the original graph.
The dual of a graph is a graph where the vertices and edges are swapped. The dual contains the same information, represented differently.
In a complete graph, every pair of distinct vertices is connected by a unique edge, i.e. it’s fully connected.
A graph is homogenous if all vertices are of the same type.
If all vertices in a graph have the same degree, the graph is regular.
A cycle is a connected subgraph where every vertex has exactly two neighbours.
A k-partite graph is a graph where the vertices can be partitioned into k disjoint sets such that no two vertices in the same set are adjacent.
$a_0:=|V|$ is sometimes used as a notation for the number of vertices in a graph.
$a_1:=|E|$ is sometimes used as a notation for the number of edges in a graph.
$ϵ(G)=\frac{|E|}{|V|}$ is the density or average degree of a graph.
Simple graphs are graphs without loops or multiple edges between the same vertices.
Adjacency means two vertices are connected by an edge.
Incidence means a vertex is connected to an edge.

Transclude of reachable

Transclude of connected

Transclude of strongly-connected#^d42a8d

https://www.dmg.tuwien.ac.at/gittenberger/Folien/GrTh_u_NW.pdf

Graphs are Matrices

Graph paper reading list

Nice visualization tool: https://csacademy.com/app/graph_editor/

multigraph, hierarchical graph:

---

Some basic graph notes:

Transclude of neighbourhood#^0b3de9

Transclude of triplet

Transclude of triangle#^9c96d8

clustering coefficient