Glossary of graph theory

Graph theory is a fun part of math that looks at how things are connected. It studies objects, called vertices, and how they are linked by edges. Edges are like lines or paths that connect the vertices.

Graphs help us solve many real-world problems. For example, they can show the quickest route on a map or help design strong networks for computers and phones. Using simple pictures with dots and lines, graph theory can solve tricky puzzles about connections and relationships.

This glossary explains important words and ideas in graph theory. Whether you are curious about how networks work or just love puzzles, graph theory offers fun and useful ways to think about the world.

Symbols

Square brackets [ ] are used to show a smaller part of a bigger graph, called an induced subgraph. For example, _G__S_ means a piece of a larger graph.

The prime symbol ' helps us talk about different parts of graphs. For example, _α_(G_) tells us about one part of a graph, while _α_′(G_) tells us about a related part of its line graph.

Simple Words

In graph theory, an absorbing set is a group of points in a directed graph. Every other point has a connection leading to this set.

An acyclic graph has no cycles. For undirected graphs, this means it is a type of forest. In directed graphs, it is known as a directed acyclic graph.

The adjacency matrix shows connections between points in a graph. A 1 means there is a connection. A 0 means there is no connection.

Fun Shapes

A bipartite graph is a graph where you can split the points into two groups. Points in one group only connect to points in the other group, not to others in their own group.

A cactus graph is a connected graph where each edge is part of at most one cycle.

A caterpillar tree is a tree where the middle nodes form a line.

The center of a graph is the set of vertices that are closest to all other vertices, based on eccentricity.