Ask Your Question
1

Define a graph

asked 2020-04-14 21:01:45 +0200

salam gravatar image

updated 2020-04-14 23:05:10 +0200

I would like to define a graph G as follows:

Assume T is a graph with t leaves. Add t copies of Petersen graph to T and identify a vertex from the outer cycle of each Petersen graph with a leaf such that t added Petersen graphs are disjoint.

I would appreciate it if you tell how I can define this graph.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2020-04-16 07:45:14 +0200

slelievre gravatar image

To provide inspiration, here are two examples layouts for a tree decorated with extra "Petersen graph leaves".

Note the use of get_pos to get the predefined positions of vertices in Sage's Petersen Graph, and of set_pos to position the vertices of our graph.

Outward layout

n = 5
tau_over_n = 2*RDF.pi()/n
c = cos(tau_over_n)
s = sin(tau_over_n)
Rn = matrix(RDF, 2, [[c, -s], [s, c]])
R4 = matrix(RDF, 2, [[0, -1], [1, 0]])
T = Graph({'z': ['a', 'b', 'c', 'd', 'e']})
pos = {'z': (0, 0)}
pos.update({u: (Rn^k).column(0) for k, u in enumerate(['a', 'b', 'c', 'd', 'e'])})
for k, u in enumerate(['a', 'b', 'c', 'd', 'e']):
    P = graphs.PetersenGraph()
    P.relabel(lambda x: '{}{}'.format(u, x))
    pos.update({v: Rn^k*R4*(vector(p) - vector((0, 3))) for v, p in P.get_pos().items()})
    T.add_edges(P.edges())
    T.add_edge((u, '{}0'.format(u)))
T.set_pos(pos)
T.plot().show(figsize=8)
T.plot().save('petersen_tree_out.png', figsize=8)

Outward Petersen tree

Downward layout

T = Graph({'z': ['a', 'b', 'c', 'd', 'e']})
pos = {'z': (5, 3)}
pos.update({u: (2.5*k, 2) for k, u in enumerate(['a', 'b', 'c', 'd', 'e'])})
for k, u in enumerate(['a', 'b', 'c', 'd', 'e']):
    P = graphs.PetersenGraph()
    P.relabel(lambda x: '{}{}'.format(u, x))
    shift = lambda p: vector(p) + vector((2.5*k, 0))
    pos.update({v: shift(p) for v, p in P.get_pos().items()})
    T.add_edges(P.edges())
    T.add_edge((u, '{}0'.format(u)))
T.set_pos(pos)
T.plot().show(figsize=8)
T.plot().save('petersen_tree_down.png', figsize=8)

Downward Petersen tree

edit flag offensive delete link more

Comments

@slelievre, Thank you. If I want to contract edges between the tree and Petersen graphs, what codes should be inserted?

salam gravatar imagesalam ( 2020-04-16 14:34:35 +0200 )edit

Once T is defined you can do T.contr<TAB> where <TAB> denotes hitting the TAB key. This will display all methods of T that start in contr, including contract_edge and contract_edges. Then you can do T.contract_edge? or T.contract_edge?? (and the same with T.contract_edges) to display the documentation and the source code. Or just try some examples.

sage: T.contract_edge(('z', 'a'))
sage: T.plot()

sage: T.contract_edges([('z', 'c'), ('z', 'd')])
sage: T.plot()
slelievre gravatar imageslelievre ( 2020-04-16 17:38:30 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-04-14 21:01:45 +0200

Seen: 517 times

Last updated: Apr 16 '20