Graphs and Networks

Comprehensive fill-in-the-blank practice flashcards covering graph theory definitions, network modeling, degrees, walks, trails, paths, cycles, matrices, isomorphism, and the planarity algorithm.

A graph consists of points called nodes or vertices connected by lines called arcs or __________.

edges

A graph that has a number associated with each edge, known as its weight, is called a weighted graph or __________.

network

In the road network shown, the route that provides the shortest travel time of $84\,\text{mins}$ from town A to town F is __________.

ACDF

A __________ is defined as a graph each of whose vertices belongs to the original graph and each of whose edges belongs to the original graph.

subgraph

The degree, valency, or order of a vertex is defined as the number of __________.

edges incident to it

A vertex and an edge are described as __________ if the vertex is at either end of the edge.

incident

In any graph, the sum of the degrees of the vertices is equal to __________ times the number of edges.

$$2$$

A __________ is a route through the graph along edges from one vertex to the next, where vertices may be visited more than once.

walk

A walk in which no vertex is visited more than once is called a __________.

path

A walk in which no edge is visited more than once is called a __________.

trail

A __________ (or circuit) is a closed path where the end vertex is the same as the start vertex and no vertex is visited more than once.

cycle

A cycle that visits every vertex in the graph exactly once and starts and finishes at the same vertex is called a __________.

Hamiltonian cycle

An edge that starts and finishes at the same vertex is defined as a __________.

loop

A graph is a __________ graph if it does not contain a loop and no pair of vertices is connected by more than one edge.

simple

Based on the given collection of graphs, the three graphs that are not simple are __________.

T, Q, V

If the edges of a graph have directions associated with them, the edges are called directed edges and the graph is known as a __________.

digraph

According to Euler's handshaking lemma, the number of vertices with an odd degree in any undirected graph must be __________.

even, including possibly zero

A __________ is defined as a connected graph with no cycles.

tree

A subgraph that includes all the vertices of the original graph and is also a tree is called a __________.

spanning tree

Two graphs are __________ if they have the same number of vertices of the same degree connected in the same way.

isomorphic

From the options below, the graphs that are isomorphic to the top graph are __________.

(i) and (ii)

A matrix that records the number of direct links between vertices in a graph is called an __________ matrix.

adjacency

A distance matrix records the weights on edges, and where there is no direct link between vertices, it is indicated by __________.

'-'

A graph that can be drawn in a plane such that no two edges meet except at a vertex is a __________ graph.

planar

The planarity algorithm can only be applied to graphs that contain a __________.

Hamiltonian cycle

In Step 6 of the planarity algorithm, unlabelled edges crossing the currently labelled inside edge that do not cross each other are labelled with __________.

O (for outside)