Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Install
Faster access than browser!
 

Distance (graph theory)

Index Distance (graph theory)

In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. [1]

21 relations: Øystein Ore, Betweenness centrality, Centrality, Connected component (graph theory), Connectivity (graph theory), Degree (graph theory), Degree diameter problem, Directed graph, Distance matrix, Graph (discrete mathematics), Graph theory, Level structure, Mathematics, Metric space, Partition of a set, Quantum graph, Resistance distance, Shortest path problem, Sparse matrix, Tree (graph theory), Vertex (graph theory).

Øystein Ore

Øystein Ore (7 October 1899 – 13 August 1968) was a Norwegian mathematician known for his work in ring theory, Galois connections, graph theory, and the history of mathematics.

New!!: Distance (graph theory) and Øystein Ore · See more »

Betweenness centrality

In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths.

New!!: Distance (graph theory) and Betweenness centrality · See more »

Centrality

In graph theory and network analysis, indicators of centrality identify the most important vertices within a graph.

New!!: Distance (graph theory) and Centrality · See more »

Connected component (graph theory)

In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.

New!!: Distance (graph theory) and Connected component (graph theory) · See more »

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to disconnect the remaining nodes from each other.

New!!: Distance (graph theory) and Connectivity (graph theory) · See more »

Degree (graph theory)

In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.

New!!: Distance (graph theory) and Degree (graph theory) · See more »

Degree diameter problem

In graph theory, the degree diameter problem is the problem of finding the largest possible graph G (in terms of the size of its vertex set V) of diameter k such that the largest degree of any of the vertices in G is at most d. The size of G is bounded above by the Moore bound; for 1 n_ be the maximum possible number of vertices for a graph with degree at most d and diameter k. Then n_\leq M_, where M_ is the Moore bound: This bound is attained for very few graphs, thus the study moves to how close there exist graphs to the Moore bound.

New!!: Distance (graph theory) and Degree diameter problem · See more »

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them.

New!!: Distance (graph theory) and Directed graph · See more »

Distance matrix

In mathematics, computer science and especially graph theory, a distance matrix is a square matrix (two-dimensional array) containing the distances, taken pairwise, between the elements of a set.

New!!: Distance (graph theory) and Distance matrix · See more »

Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

New!!: Distance (graph theory) and Graph (discrete mathematics) · See more »

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

New!!: Distance (graph theory) and Graph theory · See more »

Level structure

In the mathematical subfield of graph theory a level structure of an undirected graph is a partition of the vertices into subsets that have the same distance from a given root vertex.

New!!: Distance (graph theory) and Level structure · See more »

Mathematics

Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

New!!: Distance (graph theory) and Mathematics · See more »

Metric space

In mathematics, a metric space is a set for which distances between all members of the set are defined.

New!!: Distance (graph theory) and Metric space · See more »

Partition of a set

In mathematics, a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets.

New!!: Distance (graph theory) and Partition of a set · See more »

Quantum graph

In mathematics and physics, a quantum graph is a linear, network-shaped structure of vertices connected by bonds (or edges) with a differential or pseudo-differential operator acting on functions defined on the bonds.

New!!: Distance (graph theory) and Quantum graph · See more »

Resistance distance

In graph theory, the resistance distance between two vertices of a simple connected graph, G, is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to G, with each edge being replaced by a 1 ohm resistance.

New!!: Distance (graph theory) and Resistance distance · See more »

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

New!!: Distance (graph theory) and Shortest path problem · See more »

Sparse matrix

In numerical analysis and computer science, a sparse matrix or sparse array is a matrix in which most of the elements are zero.

New!!: Distance (graph theory) and Sparse matrix · See more »

Tree (graph theory)

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.

New!!: Distance (graph theory) and Tree (graph theory) · See more »

Vertex (graph theory)

In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).

New!!: Distance (graph theory) and Vertex (graph theory) · See more »

Redirects here:

Diameter (graph theory), Diameter (graph), Eccentricity (graph theory), Geodesic distance, Graph diameter, Graph distance, Graph metric, Pseudo-peripheral vertex, Radius (graph theory).

References

[1] https://en.wikipedia.org/wiki/Distance_(graph_theory)

OutgoingIncoming
Hey! We are on Facebook now! »