Graph theory IB AIHL

Degree of vertex

Number of edges at a vertex

Simple graph

a graph with no loops or multiple edges

connected graph

a graph such that there is a path going from any vertex to any other vertex

complete graph

A graph in which each of the n vertices is connected to every other vertex.

strongly connected

A directed graph is strongly connected if every two vertices are reachable from each other.

Adjacent edges

edges that share a common vertex

Adjacent vertices

Two vertices that are connected by an edge

Walk

Any sequence of adjacent edges

Trail

A walk with no repeated edges

Path

A walk with no repeated vertices

Cycle

A walk starting and ending at the same vertex (closed path)

Circuit

Like a cycle but no repeated edges (closed trail)

Tree

A connected undirected graph with no cycles.

Adjacency matrix

A matrix which records the number of direct links between vertices. From row to column

Eulerian graph

A graph with no odd vertices

Eulerian circuit

A circuit that contains every edge of a graph

Hamiltonian path

A path that visits every vertex of the graph exactly once

Weighted graph

A graph with numbers assigned to its edges.