Bipartiteness

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/14

encourage image

There's no tags or description

Looks like no tags are added yet.

15 Terms

1
New cards

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)

2
New cards

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

3
New cards

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

4
New cards

Bipartiteness is similar to

BFS

5
New cards

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

6
New cards

Running time of 2-colouring a graph

Same as BFS: O(m + n)
- Modifications make no difference asymptotically

7
New cards

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)

8
New cards

Directed Acyclic Graph (DAG)

A graph that does not have any cycles

9
New cards

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

10
New cards

If a graph has a topological ordering

It is a DAG

11
New cards

Every DAG has a topological ordering. True or False?

True

12
New cards

Source node

A node in a DAG that has no incoming edges

13
New cards

Every DAG has at least one source node. True or False?

True

14
New cards

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

15
New cards

Running time of finding a source in a DAG

O(m +n) - with the fast algorithm