Vertex (graph theory)

6n-graf

Small_Network

In graph theory, a vertex (plural: vertices) or node is one of the fundamental units of which graphs are formed. A graph is a collection of vertices connected by edges. Vertices are often used to represent entities in various applications, such as computer networks, social networks, and transportation systems.

Definition

A vertex is an element of a set \( V \) in a graph \( G = (V, E) \), where \( V \) is the set of vertices and \( E \) is the set of edges. Each edge in \( E \) is a pair of vertices, indicating a connection between them.

Types of Vertices

Vertices can be classified based on their properties and the structure of the graph:

• Isolated Vertex: A vertex with no incident edges.
• Pendant Vertex: A vertex with exactly one incident edge.
• Adjacent Vertices: Two vertices connected by an edge.
• Degree of a Vertex: The number of edges incident to a vertex. In a directed graph, the degree is divided into in-degree and out-degree.

Applications

Vertices are used in various fields to model and solve problems:

• In computer science, vertices can represent data points in data structures like trees and linked lists.
• In social network analysis, vertices represent individuals or entities, and edges represent relationships or interactions.
• In transportation networks, vertices can represent locations such as cities or intersections, with edges representing routes or connections.

Graph Representations

Graphs can be represented in multiple ways, with vertices being a key component:

• Adjacency List: Each vertex has a list of adjacent vertices.
• Adjacency Matrix: A matrix where rows and columns represent vertices, and entries indicate the presence or absence of edges.
• Incidence Matrix: A matrix where rows represent vertices and columns represent edges, with entries indicating the incidence relationship.

Related Concepts

• Edge (graph theory)
• Graph (discrete mathematics)
• Path (graph theory)
• Cycle (graph theory)
• Connected graph
• Complete graph
• Subgraph

See Also

• Graph theory
• Edge (graph theory)
• Adjacency matrix
• Incidence matrix
• Tree (graph theory)
• Network theory