I need help solving a graph theory problem that has a strict set of unique rules
-
I would ask to rewrite the question because it's difficult to read.
-
The bounty is low for the level of the question and the time one needs to spend to write a good solution.
-
A few clarifications: Must the edge between pairs exist in the underlying graph? Do we ignore the remainder that cannot be partitioned into a subgraph of 4? Finally, and you can ignore this if you'd like, but what's the inspiration for this problem? Knowing that can help motivate a model.
-
Thank you for the feedback Mathe and Daniel90. Larrybo, here are the answers to your questions: 1. Yes an edge must exist between nodes for them to be a pair per rule 1. 2. Yes you may ignore all nodes left over after the maximum number of sets are in the result as defined in rule 3 3. I will unfortunately refrain from answering the inspiration for the problem statement
-
I have added pictures to this problem to help with visualizing it. File 1 is an example graph with n = 9. File 2 is an example of a correct solution for the graph. We know this is a correct solution because the result weight is 0, which is as small as possible. That's not to say for some graphs the smallest result weight may be above 0 or there may be other results with a result weight of 0. File 3 is a duplicate of file 2, my mistake. File 4 is an example of an incorrect solution for the graph.
- answered
- 310 views
- $30.00