# Define a graph

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 close merge delete

Sort by ยป oldest newest most voted

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.set_pos(pos)
T.plot().show(figsize=8)
T.plot().save('petersen_tree_out.png', figsize=8)


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.set_pos(pos)
T.plot().show(figsize=8)
T.plot().save('petersen_tree_down.png', figsize=8)


more

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

( 2020-04-16 14:34:35 +0100 )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()

( 2020-04-16 17:38:30 +0100 )edit