Multigraphs and Weighted Graphs

The definition of a graph can be extended in several ways. Let G = (V, E), where V is a set and E is a multiset of ordered pairs from V × V. G is called a directed multigraphs. Geometrically, a directed multigraph can be represented as a set of marked points V with a set of arrows E between the points where there is no restriction on the number of arrows from one point to another point. (Indeed, the multiplicity of an ordered pair of vertices in the multiset E is the number of arrows between the corresponding marked points.) Also, consider a graphical representation of a highway between the cities. Since there are often multilane highways between pairs of cities, this representation yields multigraphs. The notion of undirected multigraphs can be defined in a similar manner. From now on, when it is clear from the context, we shall use the term graph to mean either “graph” or “multigraphs” or both. On the other hand, when it is necessary to emphasize that we are referring to a graph (instead of to multigraphs), we shall use the term linear graph.

In modeling a physical situation as an abstract graph, there are many occasions in which we wish to attach additional information to the vertices and/or the edges of the graph. For example, in a graph that represents the highway connection among cities, we might wish to assign a number to each edge to indicate the distance between two cities connected by the edge. We might also wish to assign a number to each vertex to indicate the population of the city. In a graph that represents the outcomes of the matches in a tennis tournament we might wish to label each edge with the score and the date of the match between the players connected by the edge. In a formal and general way we define a weighted graph as either an ordered quadruple (V, E, ƒ, g), or an ordered triple (V, E, ƒ), or an ordered triple (V, E, g), where V is the set of vertices, E is the set of edges, ƒ is a function whose domain is V, and g is a function whose domain is E. The function ƒ is an assignment of weights to the vertices, and the function g is an assignment of weighs to the edges. The weights can be numbers, symbols, or whatever quantities that we wish to assign to the vertices and edges.

Services: - Multigraphs and Weighted Graphs Homework | Multigraphs and Weighted Graphs Homework Help | Multigraphs and Weighted Graphs Homework Help Services | Live Multigraphs and Weighted Graphs Homework Help | Multigraphs and Weighted Graphs Homework Tutors | Online Multigraphs and Weighted Graphs Homework Help | Multigraphs and Weighted Graphs Tutors | Online Multigraphs and Weighted Graphs Tutors | Multigraphs and Weighted Graphs Homework Services | Multigraphs and Weighted Graphs