CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download
Views: 17361
Tweet
Share
Share

Math 152 - Intro to Mathematical Software

2017-02-24

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

** Lecture 19: Combinatorics (part 2): Graphs **

Announcement: next week, my office hours will take place Monday 3-4; Zonglin's office hours will take place Tuesday 10-12.

Also, to answer a question from last time: there is indeed support for integer linear programming in Sage (i.e., finding integer solutions of linear equations which optimize other linear constraints). See http://doc.sagemath.org/html/en/reference/numerical/sage/numerical/mip.html.

In combinatorics, a graph is not the plot of a function; it is a mathematical abstraction of a network. It consists of a (usually finite) set of vertices, together with a collection of unordered pairs of vertices called edges.

How does this concept arise naturally? https://en.wikipedia.org/wiki/Graph_theory

There are many ways to construct a graph in Sage. Perhaps the easiest one is to specify a list of pairs of vertices (letting Sage guess what the vertices are).



G = Graph([(0,2), (1,3), (2,4), (1,4), (2,5)])
G.plot()

Another way to specify a graph is via an adjacency matrix. This is a symmetric matrix of 0s and 1s that tells you which pairs of vertices are edges.

G.adjacency_matrix()
[0 0 1 0 0 0] [0 0 0 1 1 0] [1 0 0 0 1 1] [0 1 0 0 0 0] [0 1 1 0 0 0] [0 0 1 0 0 0] 
M = Matrix([[0,0,1,1],[0,0,1,1],[1,1,0,1],[1,1,1,0]])
G = Graph(M)
show(G)
G.adjacency_matrix() == M
d3-based renderer not yet implemented
True

You can also find some standard examples using the networkx package...

import networkx

G = Graph(networkx.heawood_graph())
plot(G)


G = Graph(networkx.petersen_graph())
show(G)
d3-based renderer not yet implemented

... or the graphs object.

show(graphs.BuckyBall())
d3-based renderer not yet implemented
graphs.PetersenGraph()
Petersen graph: Graph on 10 vertices

This includes various types of random graphs.

show(graphs.RandomGNP(20, 0.1))
d3-based renderer not yet implemented
show(graphs.RandomGNP(20, 0.2))
d3-based renderer not yet implemented
graphs.RandomBipartite(5, 2, 0.5).plot()



G = graphs.RandomGNP(20, 0.1)
show(G)
d3-based renderer not yet implemented
# Count connected components
G.connected_components()
[[0, 1, 2, 3, 4, 5, 7, 9, 11, 13, 14, 15, 16, 17, 19], [6], [8], [10], [12], [18]] 
G = graphs.RandomTree(20)
plot(G, vertex_size=200, vertex_colors={'#FF0000': [2], '#00FF00': [3]})

# Compute distance
G.distance(2, 3)

File: /projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
Signature : G.distance(self, u, v, by_weight=False)
Docstring :
Returns the (directed) distance from u to v in the (di)graph, i.e.
the length of the shortest path from u to v.

This method simply calls "shortest_path_length()", with default
arguments. For more information, and for more option, we refer to
that method.

INPUT:

* "by_weight" - if "False", the graph is considered unweighted,
  and the distance is the number of edges in a shortest path. If
  "True", the distance is the sum of edge labels (which are assumed
  to be numbers).

EXAMPLES:

   sage: G = graphs.CycleGraph(9)
   sage: G.distance(0,1)
   1
   sage: G.distance(0,4)
   4
   sage: G.distance(0,5)
   4
   sage: G = Graph({0:[], 1:[]})
   sage: G.distance(0,1)
   +Infinity
   sage: G = Graph({ 0: {1: 1}, 1: {2: 1}, 2: {3: 1}, 3: {4: 2}, 4: {0: 2}}, sparse = True)
   sage: G.plot(edge_labels=True).show() # long time
   sage: G.distance(0, 3)
   2
   sage: G.distance(0, 3, by_weight=True)
   3
3 
G = graphs.RandomGNP(25, 0.4)
plot(G)

# Compute minimum cut (as in maxflow-mincut)
G.edge_cut(2, 18, algorithm="FF", vertices=True)
[4, [(2, 6, None), (2, 12, None), (2, 13, None), (2, 22, None)], [[2], [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]]] 
# Compute minimum spanning tree for a particular weight function
G.min_spanning_tree(weight_function = lambda e: e[0]+e[1])
[(0, 2, None), (0, 4, None), (0, 8, None), (0, 11, None), (0, 13, None), (0, 14, None), (0, 15, None), (0, 16, None), (0, 17, None), (0, 19, None), (0, 21, None), (0, 22, None), (1, 2, None), (1, 12, None), (1, 24, None), (2, 5, None), (2, 9, None), (2, 10, None), (2, 18, None), (3, 4, None), (3, 23, None), (5, 7, None), (6, 9, None), (6, 20, None)] 
# Compute chromatic number
G.chromatic_number()
6 
# Compute automorphism group
G = graphs.PetersenGraph()
H = G.automorphism_group()
print H.order()
120 
S5 = SymmetricGroup(5)
H.is_isomorphic(S5)
True