Weighted graphs
المؤلف:
Jean-Claude Fournier
المصدر:
Graph Theory and Applications
الجزء والصفحة:
41
6-8-2016
2274
In graph applications, in particular in optimization, weighted graphs are often considered, that is graphs with values, integer or real, positive or not, associated with the edges. Formally, we have a graph G =(X, Y )with a mapping v : E → R.
When a weighted graph is a simple graph, which is often the case, its computer model is generally a matrix, such as the adjacency matrix, but with entries being the values of the edges under consideration. We choose a special number, for example ∞, when there are no edges joining the vertices associated with this entry of the matrix. Specifically, using the a bovenotation, it is the matrix M =(v(xixj )), where 1 ≤ i, j ≤ n, with mapping v extended by stating: v(xixj )= ∞ when i ≠ j and xixj ∉ E, v(xixj )=0 when i = j. This matrix is symmetric.
It is also possible to use the list of edges to represent weighted graphs ,by adding for each edge xixj the data of its value v(xixj ). In practice, it is possible to define an array indexed on the “edge” type of the graph. This type is defined as an interval of integers by numbering the edges from 1 to m, and by associating with each edge a record containing three fields: two for the endvertices of the edge and one for its value.
The list of neighbors is a priori less adapted to represent weighted graphs .Nevertheless, it is possible in the case of simple weighted graphs to add for each neighbor the data of the value of the corresponding edge.
Graph Theory and Applications ,Jean-Claude Fournier, WILEY, page(41)
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
