patternMinor
Could a directed graph be bipartite?
Viewed 0 times
bipartitedirectedcouldgraph
Problem
I check for the symmetric directed graph and it's impossible to be bipartite , because we can't divide the vertices into two sets since all will have in - and out arrow
but in general it could be right ?
if I draw a graph with one direction
but in general it could be right ?
if I draw a graph with one direction
Solution
The monograph Digraphs: Theory, Algorithms and Applications by Bang-Jensen and Gutin defines a bipartite digraph as a digraph whose vertices can be partitioned into two sets $A,B$ such that every directed edge connects a vertex in $A$ to a vertex in $B$ or vice versa. Alternatively, a bipartite digraph is a digraph which can be obtained from a bipartite graph by replacing each undirected edge by a directed edge or by a pair of directed edges.
In some situations we might want to add the condition that there are no parallel edges, that is, that it if $(x,y)$ is an edge then $(y,x)$ is not an edge.
In some situations we might want to add the condition that there are no parallel edges, that is, that it if $(x,y)$ is an edge then $(y,x)$ is not an edge.
Context
StackExchange Computer Science Q#91519, answer score: 9
Revisions (0)
No revisions yet.