Fundamentos del Teorema BEST

El Teorema BEST (nombrado por de Bruijn, van Aardenne-Ehrenfest, Smith y Tutte) es un resultado fundamental en la teoría de grafos que proporciona un método eficiente para contar el número de circuitos eulerianos en un grafo dirigido.

Para un grafo dirigido euleriano, la cantidad de circuitos eulerianos distintos se calcula mediante la siguiente fórmula:

\[ \text{Circuitos} = t_w \cdot \deg^+(w)! \prod_{v \in V} (\deg^+(v) - 1)! \]

Donde:

• \(t_w\) es el número de árboles generadores dirigidos hacia la raíz \(w\), el cual puede determinarse utilizando el Teorema de la Matriz Árbol (Matrix Tree Theorem).
• \(\deg^+(v)\) representa el grado de salida del vértice \(v\).
• \(V\) es el conjunto de todos los vértices del grafo.

Esquema de la Demostración

La demostración se basa en la construcción de circuitos a partir de árboles generadores. Al fijar un vértice como raíz, se establece un orden para las aristas salientes de cada nodo. La última arista que abanodna cada vértice (excepto la raíz) debe pertenecer obligatoriamente al árbol generador. Las permutcaiones de las aristas restantes, combinadas con la selección del árbol generador, generan todos los circuitos eulerianos posibles sin incurrir en duplicaciones, garantizando que el grafo residual mantenga la conectividad débil y las propiedades de grados necesarias.

Aplicación 1: Conteo en Grafos Dirigidos

En el contexto de grafos dirigidos, el problema consiste en calcular el número de caminos eulerianos que comienzan y terminan en un vértice específico, utilizando todas las aristas exactamente una vez. El resultado debe modularse por \(10^6 + 3\).

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef long long ll;
const int MOD = 1000003;
const int MAXN = 105;
const int MAX_FACT = 500005;

ll fact[MAX_FACT];
int out_deg[MAXN], in_deg[MAXN];
int parent[MAXN];
ll kirchhoff[MAXN][MAXN];

int find_set(int x) {
    return parent[x] == x ? x : parent[x] = find_set(parent[x]);
}

ll gauss_elimination(int n) {
    ll det = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            while (kirchhoff[j][i]) {
                ll ratio = kirchhoff[i][i] / kirchhoff[j][i];
                for (int k = i; k < n; ++k) {
                    kirchhoff[i][k] = (kirchhoff[i][k] - ratio * kirchhoff[j][k]) % MOD;
                }
                swap(kirchhoff[i], kirchhoff[j]);
                det = (-det % MOD + MOD) % MOD;
            }
        }
        if (kirchhoff[i][i]) {
            det = (det * kirchhoff[i][i]) % MOD;
        }
    }
    return (det % MOD + MOD) % MOD;
}

void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAX_FACT; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
}

void solve() {
    int n;
    if (!(cin >> n)) return;
    
    memset(kirchhoff, 0, sizeof(kirchhoff));
    memset(out_deg, 0, sizeof(out_deg));
    memset(in_deg, 0, sizeof(in_deg));
    for (int i = 1; i <= n; ++i) parent[i] = i;

    for (int u = 1; u <= n; ++u) {
        int edges_count;
        cin >> edges_count;
        out_deg[u] = edges_count;
        for (int j = 0; j < edges_count; ++j) {
            int v;
            cin >> v;
            in_deg[v]++;
            kirchhoff[v][v]++;
            kirchhoff[u][v]--;
            if (find_set(u) != find_set(v)) {
                parent[find_set(u)] = find_set(v);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (in_deg[i] != out_deg[i]) {
            cout << 0 << "\n";
            return;
        }
        if (find_set(i) != find_set(1) && out_deg[i] > 0) {
            cout << 0 << "\n";
            return;
        }
    }

    ll trees = gauss_elimination(n);
    ll ans = (trees * out_deg[1]) % MOD;
    
    for (int i = 1; i <= n; ++i) {
        if (out_deg[i] > 0) {
            ans = (ans * fact[out_deg[i] - 1]) % MOD;
        }
    }
    
    for (int i = 2; i <= n; ++i) {
        if (find_set(i) == find_set(1) && out_deg[i] > 0) {
            cout << ans << "\n";
            return;
        }
    }
    
    cout << fact[out_deg[1]] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute_factorials();
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

Aplicación 2: Transformación de Grafos No Dirigidos

El Teorema BEST está diseñado exclusivamente para grafos dirigidos. Para resolvre problemas en grafos no dirigidos, como calcular caminos en un ciclo de 4 vértices con restricciones de traversía exacta por arista, es necesario convertir el grafo no dirigido en uno dirigido.

Cada arista no dirigida entre \(U\) y \(V\) con \(k\) traversías se divide en \(x\) aristas dirigidas de \(U \to V\) y \(k-x\) aristas de \(V \to U\). Dado que el camino resultante debe ser un circuito euleriano, el grado de entrada debe igualar al grado de salida en cada vértice. Esta condición impone restricciones lineales sobre las variables de dirección, permitiendo expresar todas las orientaciones en función de una sola variable.

Finalmente, se aplica el Teorema BEST y se divide por el factorial de las aristas paralelas para evitar contar duplicados, ya que las aristas originales no son distinguibles entre sí.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int MAXN = 600005;

ll fact[MAXN], inv_fact[MAXN];
ll a, b, c, d;

ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

void precompute() {
    fact[0] = inv_fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    inv_fact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 1; --i) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
}

ll get_comb(ll n, ll k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();

    if (!(cin >> a >> b >> c >> d)) return 0;

    if ((a % 2) != (b % 2) || (b % 2) != (c % 2) || (c % 2) != (d % 2)) {
        cout << 0 << "\n";
        return 0;
    }

    ll total_paths = 0;

    for (ll x_a = 0; x_a <= a; ++x_a) {
        ll x_b = x_a + (b - a) / 2;
        ll x_c = x_b + (c - b) / 2;
        ll x_d = x_c + (d - c) / 2;

        if (x_b < 0 || x_b > b || x_c < 0 || x_c > c || x_d < 0 || x_d > d) {
            continue;
        }

        ll deg_s = d + x_a - x_d;
        ll deg_t = a + x_b - x_a;
        ll deg_u = b + x_c - x_b;
        ll deg_v = c + x_d - x_c;

        ll tree_ways = (fact[deg_s - 1] * fact[deg_t - 1]) % MOD * 
                       (fact[deg_u - 1] * fact[deg_v - 1]) % MOD;
        
        ll dir_ways = get_comb(a, x_a) * get_comb(b, x_b) % MOD * 
                      get_comb(c, x_c) * get_comb(d, x_d) % MOD;

        ll struct_mult = (x_a * x_b % MOD * x_c % MOD + 
                          (d - x_d) * x_a % MOD * x_b % MOD + 
                          (d - x_d) * (c - x_c) % MOD * (b - x_b) % MOD + 
                          (d - x_d) * (c - x_c) % MOD * x_a % MOD) % MOD;

        ll current_ways = struct_mult * deg_s % MOD * tree_ways % MOD * dir_ways % MOD;
        total_paths = (total_paths + current_ways) % MOD;
    }

    cout << total_paths << "\n";
    return 0;
}