Adjacent

Definition

In graph theory, two vertices are adjacent if they are connected by an edge. Adjacent vertices can also be referred to as neighboring vertices.

5 Must Know Facts For Your Next Test

1. Two vertices are considered adjacent if there is a direct edge connecting them.
2. In an adjacency matrix, a '1' indicates that two vertices are adjacent, while a '0' means they are not.
3. The degree of a vertex is the number of edges connected to it, which includes all adjacent vertices.
4. An adjacency list for a graph represents each vertex and lists its adjacent vertices.
5. Adjacency is fundamental in algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS).

Review Questions

• What does it mean for two vertices to be adjacent in a graph?
• How is adjacency represented in an adjacency matrix?
• Why is understanding adjacency important for graph traversal algorithms?

Related terms

vertex: A fundamental unit of which graphs are formed, representing nodes or points.

edge: A connection between two vertices in a graph.

adjacency matrix: A square matrix used to represent a finite graph, indicating which pairs of vertices are adjacent.