Mathematics of Graphs Flashcards

Flashcards based on lecture notes about graph theory, including constructing graphs, terminology, Eulerian and Hamiltonian circuits, weighted graphs, planar graphs, and graph coloring.

Graph

A set of points called vertices and line segments or curves called edges that connects vertices.

Multiple Edges

Two or more edges that connect the same vertices.

Loop

An edge that begins and ends at the same vertex.

Connected Graph

A graph where any vertex can be reached from any other vertex by tracing along edges.

Complete Graph

A connected graph in which every possible edge is drawn between vertices.

Path

An alternating sequence of vertices and edges representing a trip from one vertex to another.

Closed Path (Circuit or Cycle)

A path that begins and ends with the same vertex.

Adjacent Vertices

Two vertices are adjacent if there is an edge joining them.

Complete Graph (Kn)

A graph where every pair of vertices is adjacent, denoted by Kn, where n is the number of vertices.

Degree of a Vertex

The number of edges attached to a vertex.

Simple Graph

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

Equivalent Graphs

Two or more graphs are equivalent if the edges form the same connections of vertices in each graph.

Eulerian Graph Theorem

A connected graph is Eulerian if and only if each vertex of the graph is of even degree.

Euler Circuit

A circuit that uses every edge of a graph, but never uses the same edge twice.

Euler Path

A path that uses every edge of a graph exactly once, starting and ending at different vertices.

Euler Circuit

A closed path that uses every edge of a graph exactly once, starting and ending at the same vertex.

Euler Path Theorem

A connected graph contains an Euler path if and only if the graph has two vertices of odd degree with all other vertices of even degree. The Euler path must start at one of the vertices of odd degree and end at the other.

Hamiltonian Path

A path that visits every vertex exactly once, but does not have to end at the same vertex it started.

Hamiltonian Circuit

A path that uses each vertex of a graph exactly once and starts and ends at the same vertex.

Dirac's Theorem

If every vertex in a connected graph with at least three vertices and no multiple edges has a degree of at least n/2 (where n is the number of vertices), then the graph is Hamiltonian.

Weighted Graph

A graph in which each edge is associated with a value, called a weight.

Traveling Salesman Problem (TSP)

Given a list of cities and the distances between each pair, find the shortest possible route that visits each city exactly once and returns to the origin city.

Greedy Algorithm

A method for finding a Hamiltonian circuit in a complete weighted graph by choosing the edge with the smallest weight at each step.

Edge-Picking Algorithm

A method for finding a Hamiltonian circuit in a complete weighted graph by marking edges of smallest weight without completing a circuit or adding a third edge to a single vertex until a Hamiltonian circuit is formed.

Planar Graph

A graph that can be drawn so that no edges intersect each other (except at vertices).

Plane Graph

A planar graph that has been drawn in the plane without any edge crossing, dividing the plane into regions.

Euler's Formula

In a connected planar graph, v + f - e = 2, where v is the number of vertices, e is the number of edges, and f is the number of faces/regions.

Graph Coloring

Assigning a color to each vertex of a graph such that no two adjacent vertices have the same color.

Chromatic Number

The minimum number of colors needed to color a graph so that no edge connects vertices of the same color.

Four-Color Theorem

Every planar graph/map is 4-colourable.