Re: Math480 questions...
William Stein
<del...@u.washington.edu> wrote:
>
>
>
> Prof Stein,
> I'm working on the graph theory worksheet/hw and i have a few questions...
> I'm trying to make a graph st each vertex is adjacent to its 'neighbors'
> using a for loop. the sage code looks like this:
>
> g= Graph({i:[(i+1),(i-1)]for i in [1..9], 10:[(0)]})
>
> I didn't get this to work, but even if the for loop worked I think it would
> create a multigraph instead of a graph (not what i want).
> What about:
>
> g= Graph({i:[(i+1)]for i in [0..9], 10; [(0)]})
>
> I just can't get a for loop to work on this.
List comprehension doesn't work or make any sense for creating a dictionary.
However, you can make a list of pairs, then turn it into a dictionary
as follows:
sage: dict( [(1,2), (3,[8,10])] )
{1: 2, 3: [8, 10]}
Here's an example like yours:
sage: dict( [(i,[i+1]) for i in [0..9]] + [(10,[0])] )
{0: [1], 1: [2], 2: [3], 3: [4], 4: [5], 5: [6], 6: [7], 7: [8], 8:
[9], 9: [10], 10: [0]}
> On another subject, is there anyway to tell if a graph is bipartite?
sage: g.is_bipartite()
Who would have thought?
> That
> would make problem #4 easy... I guess I could just make an interact for any
> ngraph and show that it's clique#=2 right? I know that a graph's chromatic
> number at least the size of the largest complete subgraph... but the
> chromatic number could be more than that right? How do i get around that?
>
> Is there a way to tell if a graph has a/an hamilton/eularian cycle/path?
g.eulerian_circuit()
Sage has no code for detecting hamiltonian paths.
William
>
>
> Thank you,
> Daniel Delamare
>
>
>
>
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
William Stein
<del...@u.washington.edu> wrote:
>
> Prof Stein,
> Is there an easy way to turn the an nxn matrix into an adjacency matrix? Or
> do I need to get each entry in the random matrix and define a graph from
> that?
Yes. Make a graph from a matrix A by typing "Graph(A)":
sage: A = matrix(ZZ,2,[[0,1],[1,0]]); A
[0 1]
[1 0]
sage: g = Graph(A); g
Graph on 2 vertices
sage: g.adjacency_matrix() == A
True
You could discover the above by typing Graph?.
> Is there a way to just get the upper diagonal of a matrix to have entries (0
> or 1) and have the lower diagonal just zeros? It seems that a graph with 1's
> random everywhere would make the graph a general graph or multigraph.
I don't understand the question. You can set any entry of a matrix to
whatever you want, e.g., to set the i,j entry of A to 1, type A[i,j] =
1.
William
>
> Thank you,
> Daniel Delamare
>