Whiteflags,
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:
Code:
$ ./a.exe
4
1 2 3
2 1
3 1
<Ctrl-D>
The same is true if I supply 2n-1 (an odd number) as the number of ambassadors, and ceiling((2n-1)/2) - 1 enemies:
Code:
$ ./a.exe
3
1 2
<Ctrl-D>
So I've added a function to validate that the degree of any given vertex in the constraint list is within the boundaries:
Code:
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
