page_title: Graph (discrete mathematics)
section_title: Weighted graph
hierarchical_section_title: Graph (discrete mathematics) / Definitions / Weighted graph
caption_attribution_description: English: An example of a weighted network.
context_page_description: 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". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.
  The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person A can shake hands with a person B only if B also shakes hands with A. In contrast, if any edge from a person A to a person B corresponds to A owes money to B, then this graph is directed, because owing money is not necessarily reciprocated. The former type of graph is called an undirected graph while the latter type of graph is called a directed graph.
  Graphs are the basic subject studied by graph theory.
context_section_description: A weighted graph or a network is a graph in which a number (the weight) is assigned to each edge. Such weights might represent for example costs, lengths or capacities, depending on the problem at hand. Such graphs arise in many contexts, for example in shortest path problems such as the traveling salesman problem.
caption: A weighted graph with ten vertices and twelve edges.
exif: {}