The Gateway to Computer Science Excellence
0 votes
53 views
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?
in Graph Theory by Boss (13.8k points) | 53 views

1 Answer

+1 vote
Best answer

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 (67.5k points)
selected by
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.

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

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. :)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,688 answers
199,305 comments
107,324 users