Vertex (graph theory): Difference between revisions

Latest revision as of 12:05, 19 November 2024

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[edit]

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[edit]

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[edit]

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[edit]

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.

@@ Line 1: / Line 1: @@
-[[File:6n-graf.svg|thumb|6n-graf]] [[file:Small_Network.png|right|thumb|Small_Network]] [[file:Small_Network]];_example_image_of_a_network_with_8_vertices_and_10_edges</ref>_A_'''leaf_vertex'''_(also_'''pendant_vertex''')_is_a_vertex_with_degree_one._In_a_directed_graph,_one_can_distinguish_the_outdegree_(number_of_outgoing_edges),_denoted_𝛿<sup>_+</sup>(v),_from_the_indegree_(number_of_incoming_edges),_denoted_𝛿<sup>−</sup>(v);_a_'''source_vertex'''_is_a_vertex_with_indegree_zero,_while_a_'''sink_vertex'''_is_a_vertex_with_outdegree_zero._A_'''simplicial_vertex'''_is_one_whose_neighbors_form_a_|right|thumb|Small_Network]];_example_image_of_a_network_with_8_vertices_and_10_edges</ref>_A_'''leaf_vertex'''_(also_'''pendant_vertex''')_is_a_vertex_with_degree_one._In_a_directed_graph,_one_can_distinguish_the_outdegree_(number_of_outgoing_edges),_denoted_𝛿<sup>_+</sup>(v),_from_the_indegree_(number_of_incoming_edges),_denoted_𝛿<sup>−</sup>(v);_a_'''source_vertex'''_is_a_vertex_with_indegree_zero,_while_a_'''sink_vertex'''_is_a_vertex_with_outdegree_zero._A_'''simplicial_vertex'''_is_one_whose_neighbors_form_a_]]   == Vertex (graph theory) ==
+[[File:6n-graf.svg|thumb|6n-graf]] [[file:Small_Network.png|right|thumb|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]].
@@ Line 41: / Line 40: @@
 * [[Tree (graph theory)]]
 * [[Network theory]]
 [[Category:Graph theory]]
 [[Category:Discrete mathematics]]
 [[Category:Mathematics]]
 {{Graph theory}}
 {{math-stub}}