David, Thanks so much for your interest.
I want the program to calculate the edge labels/colors/weight for a given unlabeled graph under the constraint that no adjacent vertices have the same number of each label. Maybe "weights" can be used instead of the edge label data structure in Sage. I want to start with the straight adj. matrix, only 1 for values, and compute the labels for edges, however they are represented. Michael --- On Sun, 3/7/10, David Joyner <[email protected]> wrote: > From: David Joyner <[email protected]> > Subject: Re: [sage-edu] Re: I need a modified edge coloring function to help > student with graph theory project > To: [email protected] > Date: Sunday, March 7, 2010, 10:30 AM > 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. > > -- 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.
