What does $x_e$ usually denote in graph theory?

85 Views Asked by At

I found it in a script, but it doesn't say what $x_e$ actually means. In this case, I think $x$ is supposed to be a vertex, whereas $e \in E$ is an edge of a Graph $G = (V,E)$.

I'm sure that I saw this notation in the past, but I can't remember what it was supposed to describe.

More context:

The perfect matching polytope of a bipartite graph $G = (V_1, V_2, E)$ is given by the set

$\{x \in \Bbb R^E | x_e \ge 0 \ \forall e \in E$, and $\sum_{e \in \delta(v) }x_e = 1 \ \forall v\in V\}$

2

There are 2 best solutions below

3
On BEST ANSWER

$x_e$ appears to be a coordinate of a vector $x$ that lives in a Euclidean space of dimension the number of edges in your graph.

It is therefore not specific to graph theory. What is going on here is that a geometric object (a polytope) is being built from graph-theoretical information.

2
On

Here $x_{e}$ is a 0-1 variable where $x_{e}=1$ if edge $e$ is in a perfect matching and $0$ if it is not in the matching.

You can solve the problem with integer linear programming. However, since the constraint matrix happens to be totally unimodular, you only need to find an optimal basic feasible solution using the simplex method to obtain a solution.