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