1/14
Looks like no tags are added yet.
A graph G = (V,E) is bipartite if and only if
it can be partitioned into sets A and B such that each edge has one endpoint in A and one in B : G = (A U B, E)
Alternative definitions of bipartiteness/ Characterisations of bipartiteness
its nodes can be coloured with 2 colours such that every vertex has one red endpoint and one green endpoint
it does not contain any cycles of odd length
Ways of asking to decide if a graph is bipartite: Given a graph G = (V, E)
- Decide if it is bipartite or not
- Decide if it is 2-colourable or not
- Decide if it contains cycles of odd length or not
Bipartiteness is similar to
BFS
How to modify BFS to 2-colouring nodes
- Add a check for odd/even layer
- Assign a colour accordingly (Layer 1 = red, Layer 2 green, so on)
- At the end check all edges to see if they have endpoints in the same colour
Running time of 2-colouring a graph
Same as BFS: O(m + n)
- Modifications make no difference asymptotically
DFS and BFS on directed graphs
-When we are at a node, we only consider neighbours that can be reached with a directed edge
- No change to running time O(m + n)
Directed Acyclic Graph (DAG)
A graph that does not have any cycles
Topological orderings
'All edges point forward'
- Given a directed graph G, it is the ordering of nodes u1, u2 ... un such that for every edge e = (ui, uj), i < j
If a graph has a topological ordering
It is a DAG
Every DAG has a topological ordering. True or False?
True
Source node
A node in a DAG that has no incoming edges
Every DAG has at least one source node. True or False?
True
If we remove a node u and all the incident edges from a DAG g, is the resulting graph still a DAG?
Yes, and if the resulting graph had a cycle, the same cycle would have been present in G
Running time of finding a source in a DAG
O(m +n) - with the fast algorithm