Recitation 7

Recitation notes for the week of October 9, 2017.

Announcement

Next week's recitations will be held like group office hours in preparation for the midterm. If you plan on coming to recitation, come with questions.

Cycles

Talk about valid cycles in the graph below. (Recall that one must have at least 3 nodes to be a cycle.)

For the above graph, the following would all be valid outputs for Q1 on HW 5: \[[3,2,5]\] \[[1,2,3]\] \[[5,3,1,2]\]

Testing Bipartiteness in Graphs

We start off with the definition of a bi-partite graph from Kleinberg-Tardos:

Bipartite Graph

Given a graph $G=(V,E)$, the node set $V$ can be partitioned into sets $X$ and $Y$ in such a way that every edge has one end in $X$ and one end in $Y$.

We can think of this by coloring each node either red (if it is in $X$) or blue (if it is in $Y$) and all edges are "non-monochromatic," i.e. either side have different colors.

Exercise 1

Can a triangle cycle be bipartite? Why or why not?

Ans: No.

Exercise 2

Can any odd cycle be bipartite?

Ans: No.

Designing an algorithm to test bipartiteness

Algorithm Idea

Choose any node $s$ and color it blue
Color all of $s$' neighbors red
Color the red node's neighbors blue
And so on.

At the end of the algorithm above, if every edge has different color nodes on either side, we have a valid bipartite graph.

Consider the run of the algorithm on the following example:

The graph is not bipartite since we have 2 red nodes on either side of an edge and 2 blue nodes on either side of an edge.

HW 5, Question 3

We not going to write out the actual algorithm in the notes, as that would be free points on the homework. Here is a hint:

Hint

For something to be a triangle, need to check that for nodes $u,w,v$ there exists the edges $(u, w), (w, v)$ and $(u, v)$. If we can do this check on every node in the tree, then we have listed all of the possible triangles.