Vertex (graph theory)
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_𝛿_+(v),_from_the_indegree_(number_of_incoming_edges),_denoted_𝛿−(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_𝛿_+(v),_from_the_indegree_(number_of_incoming_edges),_denoted_𝛿−(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) ==
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 | edit source]
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 | edit source]
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 | edit source]
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 | edit source]
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[edit | edit source]
- Edge (graph theory)
- Graph (discrete mathematics)
- Path (graph theory)
- Cycle (graph theory)
- Connected graph
- Complete graph
- Subgraph
See Also[edit | edit source]
- Graph theory
- Edge (graph theory)
- Adjacency matrix
- Incidence matrix
- Tree (graph theory)
- Network theory
Navigation: Wellness - Encyclopedia - Health topics - Disease Index - Drugs - World Directory - Gray's Anatomy - Keto diet - Recipes
Search WikiMD
Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD
WikiMD is not a substitute for professional medical advice. See full disclaimer.
Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.Contributors: Prab R. Tumpati, MD