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(x_ix_j )), where 1 ≤ i, j ≤ n, with mapping v extended by stating: v(x_ix_j )= ∞ when i ≠ j and x_ix_j ∉ E, v(x_ix_j )=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 x_ix_j the data of its value v(x_ix_j ). 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)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength