 GRAPH THEORY

WHAT IS A GRAPH?

A linear† graph (or simply a graph) G = (V, E) consists of a set of objects V = {v1 v2, . . .} called vertices, and another set E = {e1’ e2,. . .}, whose elements are called edges, such that each edge ek is identified with an unordered pair (vi, vj) of vertices. The vertices vi vj associated with edge ek are called the end vertices of ek.Graph Theory

The most common representation of a graph is by means of a diagram, in which the vertices are represented as points and each edge as a line segment joining its end vertices. Often this diagram itself is referred to as the graph. The object shown in Fig. 1-1, for instance, is a graph. Observe that this definition permits an edge to be associated with a vertex pair (vi, vi). Graph Theory

Such an edge having the same vertex as both its end vertices is called a self-loop (or simply a loop. The word loop, however, has a different meaning in electrical network theory; we shall therefore use the term self-loop to avoid confusion). Edge e1 in Fig. 1-1 is a self-loop. Also note that the definition allows more than one edge associated with a given pair of vertices, for example, edges e4 and e5 in Fig. 1-1. Such edges are referred to as parallel edges.Graph Theory MATERIALS SCIENCE AND ENGINEERING

A graph that has neither self-loops nor parallel edges is called a simple graph. In some graph-theory literature, a graph is defined to be only a simple graph, but in most engineering applications it is necessary that parallel edges and self-loops be allowed; this is why our definition includes graphs with self-loops and/or parallel edges. Graph Theory

Some authors use the term general graph to emphasize that parallel edges and self-loops are allowed. It should also be noted that, in drawing a graph, it is immaterial whether the lines are drawn straight or curved, long or short: what is important is the incidence between the edges and vertices. For example, the two graphs drawn in Figs. 1-2(a) and (b) are the same, because incidence between edges and vertices is the same in both cases.

In a diagram of a graph, sometimes two edges may seem to intersect at a point that does not represent a vertex, for example, edges e and f in Fig. 1-3. Such edges should be thought of as being in different planes and thus having no common point. (Some authors break one of the two edges at such a crossing to emphasize this fact.) Graph Theory

A graph is also called a linear complex, a 1-complex, or a onedimensional complex. A vertex is also referred to as a node, a junction, a point, 0-cell, or an 0-simplex. Other terms used for an edge are a branch, a line, an element, a 1-cell, an arc, and a 1-simplex. In this book we shall generally use the terms graph, vertex, and edge. Graph TheorySIGNAL AND SYSTEM ANALYSIS USING MATLAB

APPLICATIONS OF GRAPHS :

Because of its inherent simplicity, graph theory has a very wide range of applications in engineering, in physical, social, and biological sciences, in linguistics, and in numerous other areas. A graph can be used to represent almost any physical situation involving discrete objects and a relationship among them. The following are four examples from among hundreds of such applications. Graph Theory

Königsberg Bridge Problem: The Königsberg bridge problem is perhaps the best-known example in graph theory. It was a long-standing problem until solved by Leonhard Euler (1707-1783) in 1736, by means of a graph. Euler wrote the first paper ever in graph theory and thus became the originator of the theory of graphs as well as of the rest of topology. The problem is depicted in Fig. 1-4. SEMICONDUCTOR

Two islands, C and D, formed by the Pregel River in Königsberg (then the capital of East Prussia but now renamed Kaliningrad and in West Soviet Russia) were connected to each other and to the banks A and B with seven bridges, as shown in Fig. 1-4. ROBOT DYNAMICS AND CONTROL

The problem was to start at any of the four land areas of the city, A, B, C, or D, walk over each of the seven bridges exactly once, and return to the starting point (without swimming across the river, of course).Euler represented this situation by means of a graph, as shown in Fig. 15. The vertices represent the land areas and the edges represent the bridges. As we shall see in Chapter 2, Euler proved that a solution for this problem does not exist. ELECTRIC POWER GENERATION

The Königsberg bridge problem is the same as the problem of drawing figures without lifting the pen from the paper and without retracing a line (Problems 2-1 and 2-2). We all have been confronted with such problems at one time or another.ELECTRONIC CIRCUIT ANALYSIS

Utilities Problem: There are three houses (Fig. 1-6) H1, H2, and H3, each to be connected to each of the three utilities—water (W), gas (G), and electricity (E)—by means of conduits. Is it possible to make such connections without any crossovers of the conduits?

Figure 1-7 shows how this problem can be represented by a graph—the conduits are shown as edges while the houses and utility supply centers are vertices. As we shall see in Chapter 5, the graph in Fig. 1-7 cannot be drawn in the plane without edges crossing over. Thus the answer to the problem is no.FLUID DYNAMICS

Electrical Network Problems: Properties (such as transfer function and input impedance) of an electrical network are functions of only two factors: The nature and value of the elements forming the network, such as resistors, inductors, transistors, and so forth. The way these elements are connected together, that is, the topology of the network.

Since there are only a few different types of electrical elements, the variations in networks are chiefly due to the variations in topology. Thus electrical network analysis and synthesis are mainly the study of network topology. In the topological study of electrical networks, factor 2 is separated from 1 and is studied independently. The advantage of this approach will be clearer in Chapter 13, a chapter devoted solely to applying graph theory to electrical networks.DATA STRUCTURES WITH JAVA

The topology of a network is studied by means of its graph. In drawing a graph of an electrical network the junctions are represented by vertices, and branches (which consist of electrical elements) are represented by edges, regardless of the nature and size of the electrical elements. An electrical network and its graph are shown in Fig. 1-8.

Seating Problem: Nine members of a new club meet each day for lunch at a round table. They decide to sit such that every member has different neighbors at each lunch. How many days can this arrangement last?

This situation can be represented by a graph with nine vertices such that each vertex represents a member, and an edge joining two vertices represents the relationship of sitting next to each other. Figure 1-9 shows two possible seating arrangements—these are 1 2 3 4 5 6 7 8 91 (solid lines), and 1 3 5 2 7 4 9 6 8 1 (dashed lines). It can be shown by graphtheoretic considerations that there are only two more arrangements possible.