Ask Your Question

Revision history [back]

Here is some pattern to find what you are looking for in Sage.

First, create the graph you are working on (let me take a classical example):

sage: G = graphs.PetersenGraph()

Now that you have it, you can look for all available methods by using the TAB-completion ([TAB] is the keyboard key with 2 arrows):

sage: G.[TAB]

You will see:

sage: G.matching

To be sure that it is what you are looking for, you can have a look to its documentation with a question mark ?:

sage: G.matching?

Then, you can call the method on the graph G:

sage: G.matching()

If you want the number of edges, you can do:

sage: len(G.matching())
5

or, as you could see in the previous doc:

sage: G.matching(value_only=True)
5

Here is some pattern a suggestion using mixed integer linear programming, see this tutorial for explicit Sage implementation :

  • variables : for each edge $e$ of the graph $G$, we associate a boolean variables $m_e$ (telling whether $e$ belongs to find what the matching you are looking for
  • constaints :
    • for in Sage.

      each vertex $v$ of $G$, you want $\sum_{e \in N(v)} m_e \leq 1$ where $N(v)$ denotes the set of edges that are adjacent to the vertex $v$
    • for each edge $e$ of $G$, you want $\sum_{f \in N(e)} m_f \leq 1$ where $N(e)$ denotes the set of edges that are adjacent to the edge $e$
    • First, create

  • objective : you want to maximize the graph you are working on (let me take a classical example):

    sum $\sum_{e\in G} m_e$
  • sage: G = graphs.PetersenGraph()
    

    Now that you have it, you can look for all available methods by using the TAB-completion ([TAB] is the keyboard key with 2 arrows):

    sage: G.[TAB]
    

    You will see:

    sage: G.matching

    To be sure that it is what you are looking for, you can have a look to its documentation with a question mark ?:

    sage: G.matching?

    Then, you can call the method on the graph G:

    sage: G.matching()
    

If you want the number of edges, you can do:have any problem in writing this down into Sage code, do not hesitate to ask for details.

sage: len(G.matching())
5

or, as you could see in the previous doc:

sage: G.matching(value_only=True)
5

Here is a suggestion using mixed integer linear programming, see this tutorial for explicit Sage implementation :implementation:

  • variables : for variables: to each edge $e$ of the graph $G$, we associate a boolean variables $m_e$ (telling whether $e$ belongs to the matching you we are looking forfor)
  • constaints : constraints:
    • for each vertex $v$ of $G$, you we want $\sum_{e \in N(v)} m_e \leq 1$ where $N(v)$ denotes the set of edges that are adjacent to the vertex $v$
    • for each edge $e$ of $G$, you we want $\sum_{f \in N(e)} m_f \leq 1$ where $N(e)$ denotes the set of edges that are adjacent to the edge $e$
  • objective : you objective: we want to maximize the sum $\sum_{e\in G} m_e$

If you have any problem in writing this down into Sage code, do not hesitate to ask for details.