Graph theory provides a language for describing relationships between objects. This lesson introduces its basic elements, explains why graphs belong to discrete mathematics, and traces a few milestones in the field’s history.
A graph is a mathematical structure used to represent pairwise relationships. Its vertices (also called nodes or points) represent objects, while its edges (also called links, arcs, or lines) represent relationships between pairs of objects. The two vertices connected by an edge are its endpoints.
All flashcards
What is a graph?
A mathematical structure made of vertices and edges that models pairwise relationships between objects.
What is a vertex?
A vertex, also called a node or point, represents an object in a graph.
What is an edge?
An edge, also called a link or arc, represents a relationship between two vertices.
What did Euler contribute to graph theory?
In 1736 he analyzed the Seven Bridges of Königsberg problem by abstracting land areas as vertices and bridges as edges.
What does a graph drawing leave out?
The exact placement and appearance of vertices and edges; the abstract graph is determined by its connections.
Quiz questions
What distinguishes a directed edge from an undirected edge?Answer: A directed edge has a specified orientation from one endpoint to another.
Which property defines a simple graph?Answer: It has no loops and no multiple edges between the same pair of vertices.
What information does an adjacency list store for each vertex?Answer: The vertices adjacent to it.
What does it mean for a graph to be planar?Answer: It can be drawn in the plane without edge crossings.
What does the chromatic number of a graph measure?Answer: The minimum number of colors needed so adjacent vertices have different colors.
Based on the Wikipedia article Graph theory, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.