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] 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.
