Worksheets related to Applied Discrete Structures
g=Graph({1:[3,5],2:[4,5],3:[4,5],4:[5],6:[2,4,7]})
g

Graph on 7 vertices
g.plot()

g.degree_sequence()

[4, 4, 3, 3, 3, 2, 1]
g.diameter()

4
g.chromatic_number()

3
g.adjacency_matrix()


[0 0 1 0 1 0 0] [0 0 0 1 1 1 0] [1 0 0 1 1 0 0] [0 1 1 0 1 1 0] [1 1 1 1 0 0 0] [0 1 0 1 0 0 1] [0 0 0 0 0 1 0]
h=graphs.CubeGraph(3)
h.plot(layout="spring")


There are two basic search algorithms for graphs, the breadth-first and depth-first searches. Here, we demonstrate the use of both of them. We start with a small, relatively sparse graph after seeding the random number generator.

set_random_seed(1000)
r=graphs.RandomGNP(20,0.2)
r

RandomGNP(20,0.200000000000000): Graph on 20 vertices
bfs=r.breadth_first_search(0,report_distance="True")
list(bfs)

[(0, 0), (2, 1), (13, 1), (7, 2), (15, 2), (3, 3), (19, 3), (8, 3), (14, 3), (5, 3), (11, 3), (6, 4), (9, 4), (1, 4), (16, 4), (4, 4), (10, 4), (18, 4), (12, 5), (17, 5)]

The maximum depth in a breadth-first search will be a lower bound on the diameter of the graph, which is the length of the longest "shortest path" between all vertices.

r.diameter()

5
r.depth_first_search?

File: /projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : r.depth_first_search(self, start, ignore_direction=False, distance=None, neighbors=None)
Docstring :
Return an iterator over the vertices in a depth-first ordering.

INPUT:

* "start" - vertex or list of vertices from which to start the
traversal

* "ignore_direction" - (default False) only applies to directed
graphs. If True, searches across edges in either direction.

* "distance" - Deprecated. Broken, do not use.

* "neighbors" - a function giving the neighbors of a vertex. The
function should take a vertex and return a list of vertices.  For
a graph, "neighbors" is by default the "neighbors()" function of
the graph.  For a digraph, the "neighbors" function defaults to
the "neighbor_out_iterator()" function of the graph.

compiled graphs.

* "depth_first_search" -- depth-first search for fast compiled
graphs.

EXAMPLES:

sage: G = Graph( { 0: [1], 1: [2], 2: [3], 3: [4], 4: [0]} )
sage: list(G.depth_first_search(0))
[0, 4, 3, 2, 1]

By default, the edge direction of a digraph is respected, but this
can be overridden by the "ignore_direction" parameter:

sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]})
sage: list(D.depth_first_search(0))
[0, 3, 6, 7, 2, 5, 1, 4]
sage: list(D.depth_first_search(0, ignore_direction=True))
[0, 7, 6, 3, 5, 2, 1, 4]

Multiple starting vertices can be specified in a list:

sage: D = DiGraph( { 0: [1,2,3], 1: [4,5], 2: [5], 3: [6], 5: [7], 6: [7], 7: [0]})
sage: list(D.depth_first_search([0]))
[0, 3, 6, 7, 2, 5, 1, 4]
sage: list(D.depth_first_search([0,6]))
[0, 3, 6, 7, 2, 5, 1, 4]

More generally, you can specify a "neighbors" function.  For
example, you can traverse the graph backwards by setting
"neighbors" to be the "neighbors_in()" function of the graph:

sage: D = digraphs.Path(10)
sage: list(D.depth_first_search(5, neighbors=D.neighbors_in))
[5, 4, 3, 2, 1, 0, 24, 23, 22]
[5, 24, 4, 23, 3, 22, 2, 1, 0]
sage: list(D.depth_first_search(5, neighbors=D.neighbors_out))
[5, 6, 7, 8, 9, 33, 34, 35]
[5, 33, 6, 34, 7, 35, 8, 9]



dfs=r.depth_first_search(start=0)



for v in dfs:
print v

0 13 7 14 11 15 5 6 12 4 8 10 18 1 9 3 19 16 17 2
r.plot()




How many sequences of n nonnegative integers are graphic?

How many different degree sequences are there for an n vertex undirected graph? Does a degree sequence uniquely determine an undirected graph. For example, is there one graph with four vertices and degree sequence (3,1,1,1)?

rg=graphs.RandomGNP(10,0.5)
rg.degree_sequence()

[5, 5, 5, 4, 4, 3, 3, 2, 2, 1]
 rg.is_eulerian()

False
set_random_seed(33)
rg=graphs.RandomGNP(35,0.2)
rg.is_connected()

True
rg.plot()

rg.is_hamiltonian()

True

A spanning subgraph is one for which V(H)=V(G)


g=Graph({1:[3,4,5],2:[4,5],3:[4,5],6:[2,4]})
g.plot(save_pos=True)

posit=g.get_pos()
posit

{1: [1.1398183902683194, 0.6323995278931902], 2: [0.7856541282386849, -0.60184354419796], 3: [0.6563870407458304, 0.7114396135611625], 4: [1.2180603090400683, -0.04241945033695333], 5: [0.4220724685685111, 0.16082730175516477], 6: [1.4559346510382543, -0.8604034486746043]}
posit_r={1: [1.1398183902683194, 0.6323995278931902], 2: [0.7856541282386849, -0.60184354419796], 3: [0.6563870407458304, 0.7114396135611625], 4: [1.2180603090400683, -0.04241945033695333],  6: [1.4559346510382543, -0.8604034486746043]}

h1=Graph({1:[3],2:[4],3:[4],6:[2,4]})
p2=h1.show(pos=posit)

h2=Graph({1:[3,5],2:[4,5],3:[4],6:[2]})
h2.plot()


h3=g.spanning_trees()[9]
h3.show(pos=posit)


g.spanning_trees()

[Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices]
g=Graph({1:[3,4,5],2:[4,5],3:[4,5],6:[2,4]})
p1=g.plot(save_pos=True)
posit=g.get_pos()
p1a=g.plot(pos=posit)
posit_r=posit
posit_r.pop(5)
print posit_r
h1=Graph({1:[3],2:[4],3:[4],6:[2,4]})
p2=h1.plot(pos=posit_r)
h2=Graph({1:[3,5],2:[4,5],3:[4],6:[2]})
p3=h2.plot(pos=posit)
h3=g.spanning_trees()[9]
p4=h3.plot(pos=posit)
fig=graphics_array(((p1a,p2),(p3,p4)))
fig

[2.036750636271431, -0.4416564025709533] {1: [2.2499028811170922, 0.4446082077560374], 2: [1.2046076653900806, -0.3894460982436145], 3: [2.4397923296347277, -0.017138018767639592], 4: [1.541880540145284, 0.2585074549460352], 6: [0.7072907912653226, 0.14512485688013455]}


File: /usr/local/sage/sage-6.5/local/lib/python2.7/site-packages/sage/combinat/posets/lattices.py
Signature : LatticePoset(*args, **kwds)
Docstring :
Construct a lattice from various forms of input data.

INPUT:

* "data", "*args", "**options" -- data and options that will be
passed down to "Poset()" to construct a poset that is also a
lattice.

OUTPUT:

FiniteLatticePoset -- an instance of "FiniteLatticePoset"

"MeetSemiLattice()"

EXAMPLES:

Using data that defines a poset:

sage: LatticePoset([[1,2],[3],[3]])
Finite lattice containing 4 elements

sage: LatticePoset([[1,2],[3],[3]], cover_relations = True)
Finite lattice containing 4 elements

Using a previously constructed poset:

sage: P = Poset([[1,2],[3],[3]])
sage: L = LatticePoset(P); L
Finite lattice containing 4 elements
sage: type(L)
<class 'sage.combinat.posets.lattices.FiniteLatticePoset_with_category'>

If the data is not a lattice, then an error is raised:

sage: elms = [1,2,3,4,5,6,7]
sage: rels = [[1,2],[3,4],[4,5],[2,5]]
sage: LatticePoset((elms, rels))
Traceback (most recent call last):
...
ValueError: Not a lattice.

sage: L = LatticePoset([[1,2],[3],[3]], facade = True)
sage: L.category()
Join of Category of finite lattice posets and Category of finite enumerated sets and Category of facade sets
sage: parent(L[0])
Integer Ring
sage: TestSuite(L).run(skip = ['_test_an_element']) # is_parent_of is not yet implemented

save?

File: /projects/sage/sage-7.3/src/sage/structure/sage_object.pyx
Signature : save(obj, filename=None, compress=True, **kwds)
Docstring :
Save "obj" to the file with name "filename", which will have an
".sobj" extension added if it doesn't have one and if "obj" doesn't
have its own "save()" method, like e.g. Python tuples.

For image objects and the like (which have their own "save()"
method), you may have to specify a specific extension, e.g. ".png",
if you don't want the object to be saved as a Sage object (or
likewise, if "filename" could be interpreted as already having some
extension).

Warning: This will *replace* the contents of the file if it

EXAMPLES:

sage: a = matrix(2, [1,2,3,-5/2])
sage: objfile = os.path.join(SAGE_TMP, 'test.sobj')
sage: objfile_short = os.path.join(SAGE_TMP, 'test')
sage: save(a, objfile)
[   1    2]
[   3 -5/2]
sage: E = EllipticCurve([-1,0])
sage: P = plot(E)
sage: save(P, objfile_short)   # saves the plot to "test.sobj"
sage: save(P, filename=os.path.join(SAGE_TMP, "sage.png"), xmin=-2)
sage: save(P, os.path.join(SAGE_TMP, "filename.with.some.wrong.ext"))
Traceback (most recent call last):
...
ValueError: allowed file extensions for images are '.eps', '.pdf', '.pgf', '.png', '.ps', '.sobj', '.svg'!
Graphics object consisting of 2 graphics primitives
sage: save("A python string", os.path.join(SAGE_TMP, 'test'))
'A python string'
'A python string'


H=matrix(ZZ,[[1,0,0,0,1,0,0,0],[0,1,0,0,0,1,0,0],
[0,0,1,0,0,0,1,0],[0,0,0,1,0,0,0,1]])
T=matrix(ZZ,[[0,0,1,1],[0,1,1,0],[1,1,0,0],[1,0,0,1]])
L=matrix(ZZ,[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1],
[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]])
L*(T.transpose())*H

[]

Traceback (most recent call last): File "/projects/sage/sage-7.3/local/lib/python2.7/site-packages/smc_sagews/sage_parsing.py", line 423, in introspect O = eval(obj if not preparse else preparse_code(obj), namespace) File "<string>", line 1, in <module> NameError: name 'export' is not defined
[0 0 1 1 0 0 1 1] [0 1 1 0 0 1 1 0] [1 1 0 0 1 1 0 0] [1 0 0 1 1 0 0 1] [0 0 1 1 0 0 1 1] [0 1 1 0 0 1 1 0] [1 1 0 0 1 1 0 0] [1 0 0 1 1 0 0 1]
H=matrix(ZZ,[[1,0,0,0,1,0,0,0],[0,1,0,0,0,1,0,0],
[0,0,1,0,0,0,1,0],[0,0,0,1,0,0,0,1]])

H

[1 0 0 0 1 0 0 0] [0 1 0 0 0 1 0 0] [0 0 1 0 0 0 1 0] [0 0 0 1 0 0 0 1]
L

[1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1] [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1]
T

[0 0 1 1] [0 1 1 0] [1 0 0 1]
L*(T.transpose())

[0 0 1] [0 1 0] [1 1 0] [1 0 1] [0 0 1] [0 1 0] [1 1 0] [1 0 1]
T.transpose()*H

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 947, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "sage/structure/element.pyx", line 2900, in sage.structure.element.Matrix.__mul__ (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/element.c:22510) return coercion_model.bin_op(left, right, mul) File "sage/structure/coerce.pyx", line 1069, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/coerce.c:9736) raise TypeError(arith_error_message(x,y,op)) TypeError: unsupported operand parent(s) for '*': 'Full MatrixSpace of 4 by 3 dense matrices over Integer Ring' and 'Full MatrixSpace of 4 by 8 dense matrices over Integer Ring'
C = Matrix(RR,[[5,1,2,1,2],[3,1,-2,0,5],[1,1,3,-1,-1]])
C.echelon_form()

[ 1.00000000000000 0.000000000000000 0.000000000000000 0.500000000000000 0.500000000000000] [ 0.000000000000000 1.00000000000000 0.000000000000000 -1.50000000000000 1.50000000000000] [ 0.000000000000000 0.000000000000000 1.00000000000000 4.93432455388958e-17 -1.00000000000000]
seq=[5,5,4,3,2,1]



graphs.DegreeSequence([5,3,2,2,2,2]).show()


graphs.CubeGraph(3).show(layout="spring",vertex_size=0)

g=graphs.CubeGraph(3)

g.show?

File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : g.show(self, method='matplotlib', **kwds)
Docstring :
Shows the (di)graph.

INPUT:

* "method" -- set to ""matplotlib"" (default) to display the
graph using matplotlib, or to ""js"" to visualize it in a browser
using d3.js.

* Any other argument supported by the drawing functions:

* ""matplotlib"" -- see "GenericGraph.plot" and
"sage.plot.graphics.Graphics.show()".

* ""js"" -- see "gen_html_code()".

EXAMPLES:

sage: C = graphs.CubeGraph(8)
sage: P = C.plot(vertex_labels=False, vertex_size=0, graph_border=True)
sage: P.show()  # long time (3s on sage.math, 2011)