With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

Description of Graphs

Graphs are composed of two types of elements: vertices and edges. Vertices represent objects, and edges establish relationships or connections between the objects. In many problems, values, or weights, are associated with a graph’s edges; however, such problems will not be considered further until Chapter 16.

Graphs may be either directed or undirected . In a directed graph, edges go from one vertex to another in a specific direction. Pictorially, a directed graph is drawn with circles for its vertices and arrows for its edges (see Figure 11.1a). Sometimes the edges of a directed graph are referred to as arcs . In an undirected graph, edges have no direction; thus, its edges are depicted using lines instead of arrows (see Figure 11.1b). Figure 11.1. Two graphs: (a) a directed graph and (b) an undirected graph

Formally, a graph is a pair G = (V, E ), where V is a set of vertices and E is a binary relation on V. In a directed graph, if an edge goes from vertex u to vertex v, E contains the ordered pair (u, v). For example, in Figure 11.1a, V = {1, 2, 3, 4} and E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 2), (3, 4)}. By convention, parentheses are used instead of braces for sets that represent edges in a graph. In an undirected graph, because an edge (u, v) is the same as (v, u), either edge is listed in E, but not both. Thus, in Figure 11.1b, V = {1, 2, 3, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required