On Sun, Mar 7, 2010 at 10:30 AM, David Joyner <[email protected]> wrote: > On Sun, Mar 7, 2010 at 10:24 AM, m_p_v_13 <[email protected]> wrote: >> David, >> >> Yes, the graph is simple. >> >> The problem is to find a coloring, or colorings, of a given simple >> connected graph using three colors. >> >> For example for this sample graph with verticies 1,2,3,4 and edge >> colors a,b,c >> >> 1--b--2 >> | | >> c b >> | | >> 4--c--3 >> >> >> Below is the Adjacency Matrix with a sample coloring using colors >> a,b,c >> and a table showing the color code for each vertice. >> >> Adj. Mat. color code >> 1 2 3 4 v abc >> ------- - ---- >> 1 | 0 b 0 c 1 | 011 e.g. 0-a, 1-2, 1-c >> 2 | b 0 b 0 2 | 020 >> 3 | 0 b 0 c 3 | 011 >> 4 | c 0 c 0 4 | 002 >> > > You mean this? > > sage: A = matrix([[0,2,0,3],[0,0,2,0],[0,0,0,3],[0,0,0,0]]) > sage: G = Graph(A, format = "adjacency_matrix", weighted = True) > sage: G.weighted_adjacency_matrix() > [0 2 0 3] > [2 0 2 0] > [0 2 0 3] > [3 0 3 0] >
Also, did you know you can type G.[hit tab key] and get all the commands for the graph G? > > What else are you trying to do? Enumerate all colorings? > I think the wikipedia links explain more about that. > > >> >> This coloring works because no adjacent vertices have the same color >> code. >> >> On Mar 7, 7:13 am, David Joyner <[email protected]> wrote: >>> On Sun, Mar 7, 2010 at 5:32 AM, m_p_v_13 <[email protected]> wrote: >>> > Hello, >>> >>> > The student is my daughter who is doing a graph theory investigation >>> > for a high school class independent study. >>> >>> > It is an detectable type edge coloring problem. >>> > Edges must be colored so that adjacent vertices do not have the same >>> > number of each color of edges. >>> >>> Can you please rephrase? Do you have a simple graph? >>> Do you want the chromatic index (http://en.wikipedia.org/wiki/Edge_coloring) >>> or the chromatic number (http://en.wikipedia.org/wiki/Graph_coloring)? >>> >>> >>> >>> >>> >>> > She is investigating a limited case for three colors and 6 or seven >>> > vertices, primarily theoretically by partitioning the problem. >>> >>> > She asked if I could help her with a program to generate some >>> > solutions as an investigative tool. >>> > I thought I could, but I'm stuck. >>> >>> > I was able to generate and print adj. matrices for the appropriate >>> > graphs using the graphs() function and figured out how to set the edge >>> > labels. >>> >>> > I tried to understand and modify the edge_coloring() function in >>> > sage.graphs.graph_coloring package but it is way to complex for me and >>> > the time I have left. This has been my first exposure to Sage or >>> > python. I have programmed a lot of C, C++, and Java. >>> >>> > Is there anyone out there who can either (within the next 10 hours) >>> >>> > - modify the Sage edge_coloring function for this case, or >>> >>> > - point me to anything else, simpler, that can be used or modified to >>> > generate some solutions (greedy, monte carlo, brute force, slow, etc.) >>> > on any platform (in Sage, Java, Matlib, etc.) that we have a chance >>> > to understand. (e.g. like the "The greedy coloring algorithm in 6 >>> > lines" described by Nathann.Cohen). >>> >>> > Thanks for any help or suggestions. >>> >>> > Michael Vogt >>> >>> > -- >>> > You received this message because you are subscribed to the Google Groups >>> > "sage-edu" group. >>> > To post to this group, send email to [email protected]. >>> > To unsubscribe from this group, send email to >>> > [email protected]. >>> > For more options, visit this group >>> > athttp://groups.google.com/group/sage-edu?hl=en. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sage-edu" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/sage-edu?hl=en. >> >> > -- You received this message because you are subscribed to the Google Groups "sage-edu" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sage-edu?hl=en.
