Basic Concepts of Graph Theory In this chapter we introduce some fundamental concepts of graph theory that are essential for structure analysis and structure synthesis of mechanisms. Readers are encouraged to refer to Gibsons [1] and Harary [2] for more detailed descriptions of the theory. | Chapter 2 Basic Concepts of Graph Theory In this chapter we introduce some fundamental concepts of graph theory that are essential for structure analysis and structure synthesis of mechanisms. Readers are encouraged to refer to Gibsons 1 and Harary 2 for more detailed descriptions of the theory. Definitions A graph consists of a set of vertices points together with a set of edges or lines. The set of vertices is connected by the set of edges. Let the graph be denoted by the symbol G the vertex by set V and the edge by set E. We call a graph with v vertices and e edges a v e graph. Edges and vertices in a graph should be labeled or colored otherwise they are indistinguishable. Each edge of a graph connects two vertices called the end points. We specify an edge by its end points that is eij denotes the edge connecting vertices i and j. An edge is said to be incident with a vertex if the vertex is an end point of that edge. The two end points of an edge are said to be adjacent. Two edges are adjacent if they are incident to a common vertex. For the 11 10 graph shown in Figure e23 is incident at vertices 2 and 3. Edges e12 e23 and e25 are adjacent. Degree of a Vertex The degree of a vertex is defined as the number of edges incident with that vertex. A vertex of zero degree is called an isolated vertex. We call a vertex of degree two a binary vertex a vertex of degree three a ternary vertex and so on. For the graph shown in Figure the degree of vertex 2 is three the degree of vertex 10 is one and vertex 11 is an isolated vertex. 2001 by CRC Press LLC FIGURE Graph subgraph component and tree. Walks and Circuits A sequence of alternating vertices and edges beginning and ending with a vertex is call a walk. A walk is called a trail if all the edges are distinct and a path if all the vertices and therefore the edges are distinct. In a path no edge may be traversed more than once. The length of a path is defined as the number of edges between .
