Introduction to Graphs
A graph \( G = (V (G), E (G)) \) or \( G = (V, E) \) consists of two finite sets. \( V (G) \) or \( V, \) the vertex set of the graph, which is a non-empty set of elements called vertices and \( E (G) \) or \( E, \) the edge set of the graph, which is pos
- PDF / 328,978 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 179 Views
Introduction to Graphs
1.1 Definitions of Graphs A graph G ¼ ðVðGÞ; EðGÞÞ or G ¼ ðV; EÞ consists of two finite sets. VðGÞ or V; the vertex set of the graph, which is a non-empty set of elements called vertices and EðGÞ or E; the edge set of the graph, which is a possibly empty set of elements called edges, such that each edge e in E is assigned as an unordered pair of vertices ðu; vÞ; called the end vertices of e. Order and size: We define jVj ¼ n to be the order of G and jEj ¼ m to be the size of G: Self-loop and parallel edges: The definition of a graph allows the possibility of the edge e having identical end vertices. Such an edge having the same vertex as both of its end vertices is called a self-loop (or simply a loop). Edge e1 in Fig. 1.1b is a self-loop. Also, note that the definition of graph allows that more than one edge is associated with a given pair of vertices, for example, edges e4 and e5 in Fig. 1.1b. Such edges are referred to as parallel edges. Simple graph: A graph, that has neither self-loops nor parallel edges, is called a simple graph. An example of a simple graph is given in Fig. 1.1a. Multigraph: A multigraph G is an ordered pair G ¼ ðV; EÞ with V a set of vertices or nodes and E a multiset of unordered pairs of vertices called edges. An example of a multigraph is given in Fig. 1.1b. Finite and Infinite graph: A graph with a finite number of vertices as well as finite number of edges is called a finite graph; otherwise it is an infinite graph as shown in Fig. 1.1c.
S. Saha Ray, Graph Theory with Algorithms and its Applications, DOI: 10.1007/978-81-322-0750-4_1, Springer India 2013
1
2 Fig. 1.1 a Simple graph, b multigraph, and c infinite graph
1 Introduction to Graphs
(a)
(b)
e1 v1
e3
v2
e2
e5 e4
v5 e7
v3
e6
v4
(c)
1.2 Some Applications of Graphs Graph theory has a very wide range of applications in engineering, in physical, and biological sciences, and in numerous other areas. 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 Euler in 1736 by means of a graph. Euler wrote the first research paper in graph theory and then became the originator of the theory of graphs. The problem is depicted in Fig. 1.2. The islands C and D formed by the river in Königsberg were connected to each other and to the banks A and B with seven bridges, as shown in Fig. 1.2. The problem was to start at any of the four land areas of the city A, B, C, and D walk over each of the seven bridges exactly once and return to the starting point. Euler represented this situation by means of a graph in Fig. 1.3. The vertices represent the land areas and the edges represent the bridges. Graph theory was born in 1736 with Euler’s famous graph in which he solved the Königsberg Bridge Problem. If some closed walk in a graph contains all the edges of the graph exactly once then (the walk is called an Euler line and) the graph is an Euler graph. Remarks A given connected graph G is an Euler graph if and onl
Data Loading...
