Chapter 6: Graphs and Trees
Section 6.1 Graphs and Their Representations
Graph and Their Representations
Graphs are formal mathematical representations of networks, collections of objects, events, or set elements that lead naturally from one to another.Graph (Informal Definition)
A graph is a nonempty set of nodes(vertices) and a set of arcs(edges) such that each arc connects two nodes.Our graphs will always have a finite number of nodes and arcs.
Example 1:
In the graph below, the vertices represents the cities, and the edges are the distance between them.
The set of nodes in the airline map of Figure 1 is {Singapore, Tokyo, Hong Kong, Detroit, Austin, Washington, Seattle, San Francisco}. There are 12 arcs; Singapore-Tokyo is an arc (here we are naming an arc by the nodes it connects), Detroit-Austin is an arc, and so on.
The informal definition of a graph works quite well if we have the visual representation of the graph before us to show which arcs connect which nodes. Without the picture, however, we need a concise way to convey this information. Hence our second definition of a graph.
Graph (Formal Definition)
A graph G is an ordered pair G=(V,E) where• V is a nonempty set of nodes(vertices)
• E is a set of arcs(edges)
• Each edge is a pair of vertices.
In other words, each element of E is a pair of elements of V.
Example 2:
In the graph below, the vertices represents the circles, and the edges are the lines between them.
For the graph of Figure 2 represents the following graph:
• V = {1,2,3,4,5,6}
• E = {{1,2}, {1,5}, {2,3}, {2,5} {3,4}, {4,5}, {4,6}}
• G = (V,E)
Undirected and Directed
Undirected graph: The edges of a graph are assumed to be unordered pairs of nodes. Sometimes we say undirected graph to emphasize this point. In an undirected graph, we write edges using curly braces to denote unordered paris. For example, an undirected edge {2,3} from vertex 2 to vertex 3 is the same thing as an undirected edge {3,2} from vertex 3 to vertex 2.Direct graph: In a directed graph, the two directions are counted as being distinct direted edges. In an directed graph, we write edges using parentheses to denote ordered pairs. For example, edge (2,3) is directed from 2 to 3, which is different than the directed edge (3,2) from 3 to 2. Directed graphs are drawn with arrowheads on the links, as shown below:
In this class, the term "graph" will mean an undirected graph. To refer to a directed graph, we will always say "directed graph".
Labeled Graph and Weighted Graph
Besides imposing direction on the arcs of a graph, we may want to modify the basic definiton of a graph in other ways. We often want the nodes of a graph to carry identifying information, like the names of the cities in the map of airline routes. This map would be a labeled graph . We may want to use a weighted graph , where each arc has some numerical value, or weight, associated with it. For example, we might want to indicate the price of the various routes in the airline map.
Figure 4 represents a labeled and weighted graph, where each edge has a numerical value indicating the price.
Applications of Graphs
(1) The Internet, for example, is a vast, virtual graph. Every vertex is an individual webpage, and every edge means that there is a hyperlink between two pages.
