Math: Graph Theory

Trail

A walk in which no edge is repeated

Path

A walk in which no edge or vertex is repeated

Circuit

A trail that starts and finishes at the same vertex

Cycle

A circuit in which no vertex is repeated

Graph

A collection of vertices connected by edges, used to represent relationships in various structures.

Vertices

The fundamental units of a graph, representing points or nodes that can be connected by edges.

Edges

Connections between vertices in a graph, representing relationships or paths.

Walk

A sequence of vertices in a graph where each adjacent pair is connected by an edge. A walk can revisit vertices and edges.

Adjacency table

A data structure used to represent a graph, where each row and column corresponds to a vertex, indicating whether pairs of vertices are adjacent.

Connected graph

A graph in which there is a path between every pair of vertices, ensuring that all vertices are reachable from one another.

Subgraph

A graph formed from a subset of the vertices and edges of a larger graph, maintaining the connections between the chosen vertices.

Unconnected graph

A graph that consists of two or more components, meaning there are at least two vertices that are not connected by a path.

Direct

a graph where there is a directed edge between pairs of vertices, indicating a one-way relationship.

Connected

A type of graph in which there is a path between every pair of vertices, ensuring all vertices are reachable from one another.

Strongly connected

A directed graph where there is a directed path from every vertex to every other vertex. This means every pair of vertices is mutually reachable.

Degree

The number of edges incident to a vertex in a graph, indicating how many connections it has.

Even degree

A vertex in a graph has an even degree if it is connected to an even number of edges.

In degree

The number of edges directed into a vertex in a directed graph.

Out degree

The number of edges directed away from a vertex in a directed graph.

Loop

An edge from a vertex back to itself

Simple graph

One with no loops or multiple edges

Multigraph

Multiple edges between vertices

Tree

A connected graph with no cycles.

Eulerian circuit

A circuit which transverses every edge exactly once

Eulerian trail

A trail which transverses every edge exactly once, but does not start and end at the same vertex

A connected graph is Eulerian if…

there are no vertices of odd degree

A connected graph is semi-Eulerian if..

there are exactly two vertices of odd degree

Hamiltonian cycle

A cycle which visits each vertex exactly once

Hamiltonian path

A path which visits each vertex exactly once, but doesn’t start and end at the same vertex

Walk

A sequence of vertices such that each successive pair of vertices is adjacent