Graph Theory

Question

Please help with the following:-

1)How to determine if a graph is bipartite or not?

2)What is meant by ordered pair in case of a directed graph and unordered pair in case of an undirected graph?

Answer 1

How to determine if a graph is bipartite or not?

Method 1:-

Chromatic no.of graph = atmost 2

 

Method 2:-

There is no odd-length cycle in the graph.

---

---

What is meant by ordered pair in case of a directed graph and unordered pair in case of an undirected graph?

 

This is undirected graph, How you represent an edge? 

(A,B) = (B,A) ===> un-ordered pair.

 

it is directed graph, (A,B) means edge from A to B,

(B,A) means edge from B to A

those are not equal i.e., (A,B) ≠ (B,A) ===> edge representation is a ordered pair

Comments

@Shaik Masthan,Superb Bhai. Can you please elaborate on the chromatic number?

---

chromatic number means, minimum no.of colors needed to color every vertex where two adjacent vertices can't be get same color.

in the above graph, color A with C1, then you can't color B and C with C1, therefore choose C2 for B and Choose C3 for C, Choose either C1 or C2 to D ( but you can't choose C3 due to C is adjacent to C, let say C1 for D ), Now for coloring E, you have the choice of C2 and C3 but not C1 due to D is adjacent to E.

so, totally we use 3 colors to color the graph.

But note that Finding chromatic number of a graph is NP-Complete Problem.

For more clarity should read all comments and answers of  https://gateoverflow.in/219836/self-doubt-regarding-graph-coloring

---

@Shaik Masthan, You are so thorough with concepts Brother. :). Just awesome. A big Thanks to you. :)

---

A big Thanks to you. :)

brother, No need to add this

---

@Shaik Masthan,I'll remember. :)