Chapter 2 - Graphs and Networks

What is a graph?

A set of points called vertices (or nodes) connected by lines called edges (or arcs).

What is a weighted graph?

A graph where each edge has a number (weight) associated with it.

What is a subgraph?

A graph whose vertices and edges all belong to the original graph.

What is the degree of a vertex?

The number of edges incident to the vertex.

What does it mean if a vertex has even degree?

Its degree is an even number.

What does it mean if a vertex has odd degree?

Its degree is an odd number.

What is a walk in a graph?

A route through a graph along edges from one vertex to the next.

What is a path?

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

What is a trail?

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

What is a cycle?

A walk where the start and end vertex are the same and no other vertex is visited more than once.

What is a Hamiltonian cycle?

A cycle that includes every vertex exactly once.

When are two vertices connected?

When there is a path between them.

When is a graph connected?

When all its vertices are connected.

What is a loop?

An edge that starts and finishes at the same vertex.

What is a simple graph?

A graph with no loops and at most one edge between any pair of vertices.

What is a directed graph (digraph)?

A graph whose edges have a direction.

What does Euler’s handshaking lemma state?

In an undirected graph, the sum of vertex degrees equals twice the number of edges, so the number of odd vertices is even.

What is a tree?

A connected graph with no cycles.

What is a spanning tree?

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

What is a complete graph?

A graph where every vertex is connected to every other vertex by exactly one edge.

What are isomorphic graphs?

Graphs that show the same information but are drawn differently.

What does an adjacency matrix show?

The number of arcs joining each pair of vertices.

What does a distance matrix show?

The weight of each arc between vertices.

What is a planar graph?

A graph that can be drawn so no edges cross except at vertices.

What is the planarity algorithm?

A method for redrawing a graph with a Hamiltonian cycle to check whether it is planar.