|< Day Day Up >|
Graphs are natural models that are used to represent arbitrary relationships among data objects. We often need to represent such arbitrary relationships among the data objects while dealing with problems in computer science, engineering, and many other disciplines. Therefore, the study of graphs as one of the basic data structures is important.
A graph is a structure made of two
Figure 22.1: Graphs.
Incident edge: (v i ,v j ) is an edge, then edge(v i ,v j ) is said to be incident to vertices v i and v j . For example, in graph G 1 shown in Figure 22.1, the edges incident on vertex 1 are (1,2), (1,4), and (1,3), whereas in G 2 , the edges incident on vertex 1 are (1,2).
Degree of vertex: The number of edges incident onto the vertex. For example, in graph G 1 , the degree of vertex 1 is 3, because 3 edges are incident onto it. For a directed graph, we need to define indegree and outdegree. Indegree of a vertex vi is the number of edges incident onto vi, with vi as the head. Outdegree of vertex vi is the number of edges incident onto vi, with vi as the tail. For graph G 2 , the indegree of vertex 2 is 1, whereas the outdegree of vertex 2 is 2.
Directed edge: A directed edge between the vertices vi and vj is an ordered pair. It is denoted by <vi,vj>.
Undirected edge: An undirected edge between the vertices v i and v j is an unordered pair. It is denoted by (v i ,v j ).
Simple path: A simple path is a path given by a sequence of vertices in which all vertices are distinct except the first and the last vertices. If the first and the last vertices are same, the path will be a cycle.
Maximum number of edges: The maximum number of edges in an undirected graph with n vertices is n ( n − 1)/2. In a directed graph, it is n ( n − 1).
If E(G) consists of all edges (v1,v2) in E(G), such that both v1 and v2 are in V(G), then G is called an induced subgraph of G. For example, the graph shown in Figure 22.2 is a subgraph of the graph G2.
Figure 22.2: The subgraph of graph G2.
For the graph shown in Figure 22.3, one of the induced subgraphs is shown in Figure 22.4.
Figure 22.3: Graph G.
Figure 22.4: Induced subgraph of Graph G of Figure 22.3.
In the undirected graph G, the two vertices v 1 and v 2 are said to be connected if there exists a path in G from v 1 to v 2 (being an undirected graph, there exists a path from v 2 to v 1 also).
Connected graph: A graph G is said to be connected if for every pair of distinct vertices (v i ,v j ), there is a path from v i to v j . A connected graph is shown in Figure 22.5.
Figure 22.5: A connected graph.
Completely connected graph: A graph G is completely connected if, for every pair of distinct vertices (v i ,v j ), there exists an edge. A completely connected graph is shown in Figure 22.6.
Figure 22.6: A completely connected graph.
|< Day Day Up >|