Unit - 4

Graph terminology

Q1) What do you understand by graph theory?

A1)

Graph theory is intimately related to many branches of mathematics. It is widely applied in subjects like, Computer Technology, Communication Science, Electrical Engineering, Physics, Architecture, Operations Research, Economics, Sociology, Genetics, etc. In the earlier stages it was called slum Topology. It also has uses in social sciences, chemical sciences, information retrieval systems, linguistics even in economics also.

Graphs are discrete structures consisting of vertices and edges that connects these vertices. There are several different types of graphs that differ with respect to the kind and number of edges that can a connect a pair of vertices. Problems in almost every conceivable discipline can be solved using graph models.

Q2) Consider the graphs given below-

Check whether these graphs are same or not?

A2)

As we can see that these graphs are not same because here and are not same since but a does not belongs to .

These two graphs look same but not equal.

We can draw these graphs as below-

These types of graphs are known as isomorphic graph when they are same except for the name of vertices.

Q3) What are simple and compound graphs?

A3)

Simple graph: A graph which has no loops and parallel edges is known as simple graph.

Compound graph: A graph which contains loops or parallel edges is called compound or multi-graph.

Q4) Define sub-graph.

A4)

We can say that is a sub-graph of G = (V, E), and write provided .

We can say that is an induced sub-graph of G = (V, E), provided and every edge in E whose vertices are still in is also an edge in .

Q5) Define isomorphic graphs.

A5)

Let and be two graphs. The graph and are said to be isomorphic if there is a bijective function such that if u and v are end vertices of some edge e ∈ then end vertices of

Q6) What are Bipartite Graphs?

A6)

A graph G(V, E) is said to be bipartite, if the vertex set V can be partitioned in to two non-empty disjoint subset and such that each edge is G had end vertex is and other end vertex in

There is no edge between two vertices of as well as there is no edge between two vertices of .

Here bipartition of V.

Q7) What are the applications of graph theory in computer science?

A7)

In computer science graph theory is used for the study of algorithms like:

Dijkstra's Algorithm

Prims's Algorithm

Kruskal's Algorithm

1. Graphs are used to define the flow of computation.

2. Graphs are used to represent networks of communication.

3. Graphs are used to represent data organization.

4. Graph transformation systems work on rule-based in-memory manipulation of graphs. Graph databases ensure transaction-safe, persistent storing and querying of graph structured data.

5. Graph theory is used to find shortest path in road or a network.

6. In Google Maps, various locations are represented as vertices or nodes and the roads are represented as edges and graph theory is used to find the shortest path between two nodes.

Q8) What do you understand by the isomorphism of graphs?

A8)

Two graphs are said to be isomorphic it they have identical behaviour in terms of graph-theoretic properties. More precisely:

Let Let G1 (V1, E1) and G2 (V2, E2) be two simple undirected graphs. A function f: V1  V2 is called a graph isomorphism if i) f is one-one and onto, i.e there exists a one-to-one correspondence between their vertices as well as edges (both the graphs have equal number of vertices and edges, however, vertices may have different levels.)

Ii) for all u,vV1, {u,v} E1 if and only if {f(u), f(v)} E2

If such a function exists, then the graphs G1 and G2 are called isomorphic graphs.

Q9) Show that the graph displayed below are not isomorphic.

A9)

The graph G and H both have five vertices and six edges. However the graph H has a vertex of degree one namely v3. Where as G has no vertices of egree one. Hence G and H are not isomorphic.

Example: Show that the simple graphs with the following adjacency matrices are isomorphic.

Q10) Define path.

A10)

An open walk in which no vertex appears more than once is called a path. The number of edges in a path is called the length of the path.

An edge which is not a loop is s path of length one. A loop can be included in a walk but not in a path.

Q11) What is the adjacency matrix of a non-directed graph?

A11)

Let G be a graph with n vertices and no parallel edges. The adjacency matrix of G in a n × n. Symmetric binary matrix A (G) = [aij]nn 

Where

Where and are vertices of G.

The following is a example of the adjacency matrix of the simple graph G.

Adjacency matrix x; A (G)-

Q12) Find the adjacency matrix of the graph-

A12)

The adjacency matrix of the above graph will be-

Q13) What do you understand by the connectivity of graph?

A13)

Connectivity of a graph:

Edge connectivity: Each cut-set of a connected graph G consists of a certain number of edges. The number of edges in the smallest cut-set (i,e cut-set with fewest number of edges) is defined as the edge connectivity of G.

Equivalently the edge connectivity (G) of a connected graph can be defined as the minimum number of edges whose removal reduces the graph disconnected. If G is a tree, then (G) = 1, became removal of any one edges reduces the the tree disconnected.

(G) = 2

Vertex connectivity: The vertex connectivity K(G) of a connected graph G is defined as the minimum number of vertices whose removal from G leaves the graph disconnected. If G is a tree then K(G) = 1

Q14) What is Eulerian graph?

A14)

A undirected graph with no isolated vertices is said to have an Euler circuit if there is a circuit in G that traverses every edge of the graph exactly once. If there is an open trail from vertex u to v in G and this trail traverses each edge in G exactly once, the trail is called Euler trail. [A trail from a vertex u to v is a path that doesnot involve a repeated edge] An Eulerian tour is a closed walk that starts at some vertex, passes through each edge exactly once and returns to the starting vertex.

Since any closed walk in an undirected graph enters and leaves any vertex the same number of times, the subgraph composed of the edges in any closed walk is even. Thus, if the graph contains a closed walk passing through each edge exactly once, the graph must be even, conversely, if the graph is even, then it contains an Euler tour, A path that passes through each edge exactly once but vertices may be repeated is called Euler path. A graph that contains an Euler tour or Euler circuit is called an Eulerian graph.

Q15) What is Hamiltonian graph?

A15)

Let G be a connected graph with more than two vertices. If there is a path in G that uses each vertex of the graph exactly once, then such a path is called Hamiltonian path. If the path is a circuit that contains each vertex in G exactly once, except the initial vertex, then such a path is called a Hamiltonian circuit.

A graph that contains a Hamiltonian circuit is called a Hamiltonian graph.

Q16) What is the Euler’s formula for planar graph?

A16)

For any planar graph with v vertices, e edges and f faces, we have-

Example

Regions

Every planar graph divides the plane into connected areas called regions.

Q17) Let G be a connected planar graph with p vertices and q edges, where p ≥ 3. Then q ≥ 3p − 6.

A17)

Let r be the number of regions in a planar representation of G. By Euler’s formula, p − q + r = 2.

Now the sum of the degrees of the regions equals 2q

But each region has degree 3 or more;

Hence 2q ≥ 3r, Thus r ≥ 2q/3

Substituting this in Euler’s formula gives

Multiplying the inequality by 3 gives 6 ≤ 3p − q which gives us our result.