[EPIJ 10/17 edition]
I’m having trouble understanding the problem statement. I think what it’s saying is to decide if it’s possible to divide the pins into 2 groups, such that no 2 pins from the same group are adjacent in the PCB i.e. no 2 pins from the same group are connected by a wire.
Is this correct?
Thanks.
Look up a bipartite graph. I think the problem just asks to determine if the graph created by pins and wires is bipartite.
Yeah, i actually posted a thread about it, with different solution, i think it’s dated Oct. 15.
From what I’ve seen online, a bipartite split doesn’t place a constraint on the relationship of number of vertices in each set. In other words, bipartite doesn’t mean half of vertices in one set and the other half in the other - it can be any number of vertices in either set. Is this correct?
Yeah that’s correct. But the problem just says to divide between 2 sets, it doesn’t constrain what the size of each set should be.