12.1 MATHEMATICAL BACKGROUND 12.1.1 Definitions and Examples A graph G consists of a set V , whose members are called the vertices of G , together 454 with a set E of pairs of … vertices from V . These pairs are called the edges of G .If eÉ Ñv;wÖ is an edge with vertices v and w , then v and w are said to lie on e , and e is said to be incident with v and w . If the pairs are unordered, then Gis called an undirected graph ; if the pairs are ordered, then G is calleda directed graphs and …
THIS CHAPTER introduces important mathematical structures called graphs that have applications in subjects as diverse as sociology, chemistry, geography, and electrical engineering. We shall study methods to represent graphs with the data structures available to us and shall construct several important algorithms for processing graphs. Finally, we look at the possibility of using graphs themselves as data structures…… Several kinds of undirected graphs are shown in Figure 12.2. Two vertices in an undirected graph are called adjacent if there is an edge from one to the other. 454 Hence, in the undirected graph of part (a), vertices 1 and 2 are adjacent, as are 3 and4, but 1and 4 are not adjacent. A path is a sequence of distinct vertices, each adjacent to the next. Part (b) shows a path. A cycle is a path containing at least paths, cycles, connected three vertices such that the last vertex on the path is adjacent to the first. Part (c) shows a cycle. A graph is called connected if there is a path from any vertex to any other vertex; parts (a), (b), and (c) show connected graphs, and part (d) showsa disconnected graph. If a graph is disconnected, we shall refer to a maximal subset of connected vertices asa component . For example, the disconnected graph in part (c) has two components: The first consists of vertices 1,2, and 4, and the second has just the vertex 3. Part (e) of Figure 12.2 shows a connected graph with no cycles. You will notice that this graph is, in fact, a tree, and we take this property as the definition: A free tree is defined as a connected undirected graph with no cycles. free tree…
http://www.pdfee.com/data-structures-and-program-design-in-c.html
Tags: Programming