Thread: i need help with this question:

  1. #16
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    United States
    If there were an odd number of ambassadors, I don't think it is deterministically possible (in the worst case). Would anyone care to debate that point?
    Maybe there is also an ambassador that doesn't hate anyone in that case, as long as we are changing the problem statement. Then, it should be possible.

  2. #17
    Registered User
    Join Date
    Jul 2010

    I think that you're on to something with that. Since, according to Dossey, et. al. Theorem 3.9: "The chromatic number of a graph G cannot exceed one more than the maximum of the degrees of the vertices of G." So for any graph, in the questions' proposition, of ambassadors the chromatic number is n. Meaning that it would take at most n ambassadors, to "color" the seats without sitting next to an ambassador of a different color (?). Obviously, 2n - (n-1) = n+1. One extra for the round table, because the end points are adjacent.

    I was concerned about the behavior of the matching algorithm for the "garbage-in garbage-out" principle. If I specify an even number, but exceed the maximum no. of enemies the loop runs indefinitely.

    Using these inputs for example:

    $ ./a.exe
    1	2	3
    2	1
    3	1
    The same is true if I supply 2n-1 (an odd number) as the number of ambassadors, and ceiling((2n-1)/2) - 1 enemies:

    $ ./a.exe
    1	2
    So I've added a function to validate that the degree of any given vertex in the constraint list is within the boundaries:

    int validateAdjacency( int **mat, int rows, int columns, int max_degree );
    If the validation fails, one could add another (how many) ambassador(s) to the table. Like sentinels that aren't actually representatives and have no enemies. It would change the size of the seating chart, but leave the enemy graph unchanged.... I was less concerned with changing the problem statement, than with adapting the solution to the possible inputs.

    Does that sound right? The proof seems a little stilted, any tips?

    Best Regards,

    New Ink -- Henry

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question bout my work
    By SirTalksAlots in forum C Programming
    Replies: 4
    Last Post: 07-18-2010, 03:23 PM
  2. A question about a question
    By hausburn in forum C++ Programming
    Replies: 3
    Last Post: 04-25-2010, 05:24 AM
  3. Alice....
    By Lurker in forum A Brief History of
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  4. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  5. Question...
    By TechWins in forum A Brief History of
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM