Month: August 2015

Proof 9: Given G = (V, E), such that G is r-regular and bi-partite, then |U| = |W|, where U, W are the 2-partite sets of G

jssandh2Leave a comment

This proof requires, as a pre-requisite, the understanding of the concepts of Regular Graphs. I will introduce Regular Graphs and a Theorem concerning Regular Graphs in this section before I actually prove the statement.

Definitions:
1) G = (V,E) is said to be r-regular, iff, \forall v \in V(G) , deg(v) = r.
A r-regular graph G is denoted as H_{r, n}
2) As before, a Graph G = (V, E) is 2-partite, iff, \exists U, W \subset V(G) , \ni , U \cap W = \phi and U \cup W = V , where, e \in E(G) iff e = (u_{i}w_{j})

Proof:
We are given that G = (V, E) = H_{r, n} , so, \forall u , w \in U and W , deg (u) = deg(w) = r
The number of edges in this graph is |E| = r(n)/2
We shall simply assume that U and W have an arbitrary number of nodes each.
Let |U| = k and |W| = n - k
We have that, in a partite graph, the number of edges from the vertices in U are equal to the number of edges from the vertices in W. If this is not the case, then, \exists e \in E(G), \ni , e = (u_{i}, v) for some vertex v \notin V(G). This clearly is a contradiction to the basic structure of G.
Therefore, given our assumption that |U| = k and |W| = (n - k) and that the sum of the edges in both sets must be equal, we have that:
\sum deg(u) = \sum deg(w) where u \in U and w \in W
Now, as this is a regular graph, all vertices have the same degree.
Given that |U| = k, |W| = (n – k) , we have that:
\sum_{u \in U} deg(u) = r(k) and that,
\sum_{w \in W} deg(w) = r(n - k).
Therefore,
rk = r(n - k) = rn - rk
2rk = rn
k = n/2
Therefore, we have that |U| = k = n/2 and |W| = (n - k) = n - n/2 = n/2
This implies that  |U| = |W| = n/2
QED

Reference: Problem 2.27, Page-43, A First Course in Graph Theory, Gary Chartrand & Ping Zhang, Dover Books.

Algorithm 1 : Create the 2-partite sets for a graph G = (V, E) , such that, for all u, v in G, |P(u -> v)| = Odd, or |P(u -> v) | = Even

jssandh2Leave a comment

To design this Algorithm, we will do 2 things:

1) State all our assumptions borrowing from Proof 8, and make clear the notation.
2) Give a proof of correctness, and examine the Computational Complexity of our Algorithm.

Assumptions:
1) That we have access to standard Data Structures (Graph, Queue) with optimal implementation.
2) Edges in the Graph carry a uniform weight.
3) G is 2-partite, as shown from Proof 8 previously.
4) Djikstra’s Algorithm, modified, such that, at every node, it’s path from the start node is stored, and Djikstra returns an Array which contains a path from the start node to the current node, and whether it is odd or even.
5) Each node v of the Graph G is marked with a label. The nodes are visited in serial order from the BFS Tree that is inherited from the BFS Traversal. We can assume that the adjacency list of the Graph respects this ordering. Basically, we go from v_{1} \dashrightarrow v_{2} \dashrightarrow v_{3} and so on during a Traversal.

Algorithm:

def constructUandW:
–      Pick v \in V(G)
–      v \dashrightarrow visited
–      pathsArray[] = Djikstra (G, v)
–      U = []
–      W = []
–      U.add(v)
–     while |U| + |W| < |V(G)|:
–          \hspace{16 mm} \forall p = (v, v_{1}, ... , v_{i}) \in pathsArray[]:
–          if |p| = odd:
–                \hspace{16 mm} W.add(v_{i})
–          else:
–                \hspace{8 mm} U.add(v_{i})

Computational Complexity : O(m + n(logn)) -> Run-Time of Djikstra’s Algorithm. BFS is Linear-Time, i.e., O(m + n. Therefore, our Algorithm runs in ~ O(m + n(logn)) time.

Proof of Correctness:
In a graph G = (V, E), where we have assumed that \kappa (G) =1 . (Adding a disconnected component doesn’t matter, because as long as every component is bi=partite, the whole graph is bi-partite).
So, now, we see that, \forall v_{i} , v_{j} \in V(G) , \exists p(u - v) . We must understand that the minimum number of edges in the graph are |E(G)| = |V(G) - 1| . Therefore, we have that, every vertex v is adjacent to atleast some other vertex v’ in the Graph G. So, we see that if we remove one edge from all Even cycles (if our Graph has cycles), then we get a Linked List, which can be made into a Bi-Partite Graph easily. So, now, all we need to prove is that no edge removed from an Even Cycle is between two vertices in the same subset of V.
Let us assume that \exists u_{i} , u_{j} \in U , \ni , u_{i}u_{j} \in E(G) . This would imply that during our BFS-like traversal we put two nodes in the queue on the same level, with the same distance to their parent (such that), they have one edge between them. This would imply the existence of a 3-cycle. That is, during the BFS traversal, on the same level, we have a cross edge. So, this implies, \exists C_{3} \subset G. Clearly, as we know that G is 2-partite, this is not possible.
Therefore, no 2 vertices in the same set in U or W are adjacent to each other.
QED.

Proof 8 : If we have G = (V, E), such that, for all u, v in V(G), |p(u->v)| = Even or |p(u->v)| = Odd, then, G is 2-Partite

jssandh2Leave a comment

We need to understand exactly what is going on. Really, all we need to show that the Graph is 2-partite is show that there exists no Odd Cycle in the graph G. This can be shown rather simply.

Given : G = (V,E) , \ni , \forall u,v \in V(G) , \forall p(u-v) , |p(u-v)| = Even \vee |p(u-v)| = Odd

To Prove: G = (V, E) is 2-partite. That is, \exists U, W \subset V ,  \ni , ( U \cup W = V ) \wedge ( U \cap W = \phi )

Proof : Let us use Proof By Contradiction. Assume that:
\exists C_{odd} \in G . Now, by definition, \forall v \in C_{odd} ,\exists v_{i} , v_{j} \in C_{odd} , \ni , ( v_{i}v_{j} \in E(G) ) \wedge ( p( v_{i} - v_{j} ) exists .
The specified path does not construct of the edge that joins v_{i} and v_{j} , but rather the cycle around it. Now, as we have an Odd Cycle, we know that |V_{cycle}| = Odd . Therefore, as v_{i} v_{j} are adjacent, for the second path, the number of remaining vertices to traverse are V(C_{odd}) - \{v_{i} , v_{j} \} . This is an odd number of vertices. Therefore, the number of edges between this acyclic path is | V(C_{odd}) - \{ v_{i} , v_{j} \} | - 1 Clearly, this is an even number, as 1 subtracted from any odd number yields an even number.
Therefore, we see that :  , \exists P_{1}(v_{i} - v_{j}) \wedge P_{2}( v_{i} - v_{j} ) , where:
|P_{1}(v_{i} - v_{j})| = |v_{i}v_{j}| = 1 and |P_{2}(v_{i} - v_{j})| = | V(C_{odd}) - \{ v_{i} , v_{j} \} | - 1 = Even
Clearly, this is a violation, as no two nodes with paths between them can have both even and odd paths. Therefore, our assumption stands invalidated.
Therefore, if we have G = (V,E) , \ni , \forall u,v \in V(G) , \forall p(u-v) , |p(u-v)| = Even \vee |p(u-v)| = Odd , G = (V, E) is 2-partite.

We can even go a bit further for this problem and even imagine what the sets U and W would be.
Now, as 1 is an odd number, we can see that all adjacent vertices would have only odd paths between them. Therefore, we put all pairs of vertices with odd paths between them in opposite sets. We do the exact opposite for all pairs of vertices with even paths between them. As all pairs of vertices with odd paths are in cross sets, and no pairs of vertices with odd paths can have even paths, we will see that none of the vertices will allow for adjacency in between the sets. One can formalize this proof quite easily, but I’ll just give a rough, intuitive formulation of what U and W would look like.

So, U \subset V , \ni , \forall u_{i} , u_{j} \in U , |p(u_{i} - u_{j})| = Even
Similarly, W \subset V , \ni , \forall v_{i} , v_{j} \in W , |p(v_{i} - v_{j})| = Even
So, all vertices that have paths that are odd in length are placed across each other, such that one of them is in U and the other in W. Now, all we need to show is that none of the vertices in the same set are adjacent, and that all odd paths can be reconstructed. Clearly, by definition, 1 \in \mathbb{Z}_{odd} , therefore, all adjacent vertices are in cross-sets. For all paths between two vertices of length > 1, and length = Odd, we will see that we will hop between sets, until we eventually end up on a node in a cross set.
One can verify the correctness of this solution by simply enumerating all paths in the Graph using Djikstras on all nodes.
The run time for that Algorithm would be : O(nm + (nm)log(m)) ~ O(nmlog(m))
Therefore, this partition allows an easy construction of non-overlapping sets for 2-partitioning G.