Graph Theory Concepts

Front

Adjacency matrix

Back

An adjacency matrix for a graph with n vertices is an n x n matrix where the entry in row i and column j is the number of edges joining the vertices i and j. A loop is counted as 1 edge.

Front

Characteristics of a bipartite graph

Back

In a bipartite graph, vertices are divided into two groups with edges only between groups.

Front

Cycle

Back

A cycle is a closed path which begins and ends at the same vertex and has no repeated edges or vertices except the first.

Front

Bridge in a graph

Back

An edge in a connected graph that, if removed, leaves the graph disconnected.

Front

Path

Back

A sequence of edges that connect a sequence of vertices.

Front

Walk

Back

A sequence of vertices and edges in a graph.

Front

Euler's formula for a connected planar graph

Back

Euler's rule states that v + f - e = 2, where v is the number of vertices, e is the number of edges, and f is the number of faces.

Front

Definition of a semi-Eulerian graph

Back

A connected graph is semi-Eulerian if there is an open trail that includes every edge once only.

Front

Number of faces in the given planar graph

Back

The planar graph shown has four faces.

Front

Definition of a loop in a graph

Back

A loop is an edge in a graph that joins a vertex to itself.