Matrices for binary relations? Fwd: TOPIC:Sequences

[Roland Bacher]

Here a reformulation,

interpret the objects as vertices of a simple (no loops or multiple
edges) graph with an edge between two vertices a and b if a,b are 
NOT related. Your problem transforms now into a coloring problem:
colour the vertices of your graph with colors given by the slots.

The number of proper colourings (adjacent vertices
have distinct colours) yields the solution to your problem
since adjacent (unrelated) vertices are forced to have
distinct colours. You can now use standard techniques in graph
theory (Tutte polynomials, etc, there is a huge literature on
chromatic properties of graphs but there is unfortunately no
really good algorithm (say polynomial) for doing the job) to
attack your problem.

Best whishes,   Roland Bacher 
 


> 
> Hi Antti,
> 
> I am working on my M.Sc. thesis in electrical engineering at DTU in Denmark
> and I got stuck in a combinatorial problem. I need to generate a number of
> alternative solutions that will later be examined for feasibility. Since I
> saw your name on the Encyclopedia of Integer Sequences, I thought you might
> have a hint for me. The problem formulation I am facing is the following:
> 
> Given are n objects x1?xn and binary relational matrix FRij. The objects are
> to be assigned to slots where each slot can contain one or more objects. Two
> objects xi and xj can only exist in the same slot if their relation is given
> with FRij = 1. FRij = 1 does not force the objects into the same slot. How
> many alternative assignments are possible?
> 
> Moreover: Which algorithm can be used to *efficiently* find all alternative
> assignments?
> 
> Do you have a hint on how to approach a solution, where to find www
> resources or other hints?
> 
> Best regards,
> 
> --------------------------------
> 
> Kristján Haukur Flosason
> 
> stud.nr. s040321
> 
> 
> 
> Ørsted-DTU, Automation
> 
>  - byg. 326, rum 117 -
> 
> DK 2800, Kgs. Lyngby
> 
> Mobile: 2964 3674
> 
> E-mail: s040321 at student.dtu.dk
> 
> --------------------------------