Graph (discrete mathematics)

A graph consists of vertices and edges connecting pairs of vertices. It models relationships, with variants differing in whether edges have direction, weights, or other structure.

Vertex (graph theory): A vertex is an element of a graph’s vertex set, representing an object or state. Vertices are the objects whose pairwise relationships the graph encodes.
Path (graph theory): A path is a sequence of vertices connected by successive edges. Paths capture indirect relationships formed by chaining edges.
Network theory: Network theory studies systems represented by entities and the connections between them. Graphs provide the basic mathematical representation for networks of interacting entities.
Directed graph: A directed graph has edges with orientations from one vertex to another. Orientation distinguishes one-way relationships from ordinary undirected edges.
Edge (graph theory): An edge is a connection between vertices in a graph. Edges encode the relationships that distinguish one graph from another.
Connected graph: A connected graph has a path between every pair of vertices. Connectivity asks whether edge chains link all vertices into one component.
Shortest path problem: The shortest path problem seeks a minimum-cost route between vertices in a weighted graph. Routing is a direct use of paths and edge weights.
Multigraph: A multigraph permits multiple edges between the same pair of vertices. Parallel edges let a model represent several distinct relationships between two vertices.
Degree (graph theory): The degree of a vertex is the number of edges incident to it, with conventions varying for loops and directed edges. Degree summarizes how many connections meet at each vertex.
Cycle (graph theory): A cycle is a closed path that returns to its starting vertex without repeating other vertices. Cycles reveal relationships that loop back rather than ending at a new vertex.

Linked from 29 pages