Ch. 12 Key Concepts - Contemporary Mathematics

Graphs and multigraphs represent objects as vertices and the relationships between the objects as edges.
The degree of a vertex is the number of edges that meet it and the degree can be zero.
An edge must have a vertex at each end.
Multigraphs may contain loops and double edges, but simple graphs may not.

The sum of the degrees of the vertices in a graph is twice the number of edges.
In a complete graph every pair of vertices is adjacent.
A subgraph is part of a larger graph.
Cycles are a sequence of connected vertices that begin and end at the same vertex but never visit any vertex twice.

Two graphs are isomorphic if they have the same structure.
When graphs are relatively small, we can use visual inspection to identify an isomorphism by transforming one graph into another without breaking connections or adding new ones.
An isomorphism between two graphs preserves adjacency.
If two graphs differ in number of vertices, number of edges, degrees of vertices, or types of subgraphs, they cannot be isomorphic.
When the complements of two graphs are isomorphic, so are the graphs themselves.

Walks, trails, and paths are ways to navigate through a graph using a sequence of connected vertices and edges.
Closed walks, circuits, and directed cycles are ways to navigate from a vertex on a graph and return to the same vertex.
Colorings are a way to organize the vertices of a graph into groups so that no two members of a group are adjacent.
Maps can be represented with planar graphs, which can always be colored using four colors or fewer.

A connected graph has only one component.
The Euler circuit theorem states that an Euler circuit exists in every connected graph in which all vertices have even degree, but not in disconnected graphs or any graph with one or more vertices of odd degree.
The Chinese postman problem asks how to find the shortest closed trail that visits all edges at least once.
If an Euler circuit exists, it is always the best solution to the Chinese postman problem.
Eulerization is the process of adding duplicate edges to a graph so that the new multigraph has an Euler circuit.
The minimum number of duplicated edges needed to eulerize a graph is half the number of odd vertices or more.

An Euler trail exists whenever a graph has exactly two vertices of odd degree.
When a bridge is removed from a graph, the number of components increases.
A bridge is never part of a circuit.
When a local bridge is removed from a graph, the distance between vertices increases.
An edge that is part of a triangle is never a local bridge.

A Hamilton cycle is a directed cycle, or circuit, that visits each vertex exactly once.
Some Hamilton cycles are also Euler circuits, but some are not.
Hamilton cycles that follow the same undirected cycle in the same direction are considered the same cycle even if they begin at a different vertex.
The number of unique Hamilton cycles in a complete graph with n vertices is the same as the number of ways to arrange $n - 1$ distinct objects.
Weighted graphs have a value assigned to each edge, which can represent distance, time, money and other quantities.

A brute force algorithm always finds the ideal solution but can be impractical whereas a greedy algorithm is efficient but usually does not lead to the ideal solution.
A Hamilton cycle of lowest weight is a solution to the traveling salesperson problem.
The brute force method finds a Hamilton cycle of lowest weight in a complete graph.
The nearest neighbor method is a greedy algorithm that finds a Hamilton cycle of relatively low weight in a complete graph.

A brute force algorithm always finds the ideal solution but can be impractical whereas a greedy algorithm is efficient but usually does not lead to the ideal solution.
A Hamilton cycle of lowest weight is a solution to the traveling salesperson problem.
The brute force method finds a Hamilton cycle of lowest weight in a complete graph.
The nearest neighbor method is a greedy algorithm that finds a Hamilton cycle of relatively low weight in a complete graph.