Graph on 7 vertices
[4, 4, 3, 3, 3, 2, 1]
4
3
[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]
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.
RandomGNP(20,0.200000000000000): Graph on 20 vertices
[(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.
5
0
13
7
14
11
15
5
6
12
4
8
10
18
1
9
3
19
16
17
2
How many sequences of nonnegative integers are
How many different degree sequences are there for an vertex undirected graph? Does a degree sequence uniquely determine an undirected graph. For example, is there one graph with four vertices and degree sequence ?
[5, 5, 5, 4, 4, 3, 3, 2, 2, 1]
False
True
True
A spanning subgraph is one for which V(H)=V(G)
{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]}
[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]
[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]}
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]
[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]
[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]
[0 0 1 1]
[0 1 1 0]
[1 0 0 1]
[0 0 1]
[0 1 0]
[1 1 0]
[1 0 1]
[0 0 1]
[0 1 0]
[1 1 0]
[1 0 1]
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'
[ 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]