Section1Graphs

Graphs play an important role in discrete mathematics. They can be created and plotted using Sage. Here we are using the Sage Cell Server. Each cell contains Sage expressions that can be evaluated by clicking on the "Evaluate" button below it. You can edit the contents of the cell to experiment - the orginal expressions will return when the page reloads.

The simplest way to create a graph is to build a dictionary(or hash function). If you wrap Graph() around a dictionary you get a graph and the plot method can be used to view an embedding of the graph on the plane.

There are many families of graphs included in the graphs package. One standard family is the set of complete bipartite graphs, \(K_{m,n}\), where \(m\) and \(n\) are positive.

Another family is of random graphs. Here is how to generate and display a random graph with a certain number of vertices and each edge determined by a fixed probability. The default is 25 vertices with a 0.15 probability of any edge being present.

The graphs package also contains a variety of functions that can be applied to a graphs. For example here we generate a graph and ask for a hamiltonian cycle in the graph.

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - No Derivative Works 3.0 United States License.