50 views

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?
| 50 views

+1 vote

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

by Veteran (65.9k points)
selected
0
@Shaik Masthan,Superb Bhai. Can you please elaborate on the chromatic number?
+1

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.

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

A big Thanks to you. :)

brother, No need to add this

0
@Shaik Masthan,I'll remember. :)

+1 vote