Metodo computazionale per i sottografi con $i$ spigoli e $j$ vertici di un grafo bipartito

[uomotorta]

Sia $G$ un grafo bipartito, con $m$ vertici e $n$ spigoli.
Vogliamo calcolare usando un metodo computazionale i sottografi con $i$ spigoli e $j$ vertici di $G$ ($j\leq m$ e $i\leq n$).

Input: grafo $G$, una coppia $(i,j)$;
Output: sottografi con $i$ spigoli e $j$ vertici di $G$

Il Macaulay2 lavora sui grafi, ma non esiste alcuna funzione che permetta di rispondere alla mia domanda. Ho fatto alcune ricerche su Google ma non ho trovato nulla. Vi volevo chiedere gentilmente se qualcuno conosce qualche software che fa questo lavoro?

[feddy]

Hai provato a chiedere su Stack Exchange? Non sono a conoscenza di utenti del forum che si occupano di questo, onestamente.

[uomotorta]

Si si, ho provato ma nessuna risposta. Sembra un mistero poter calcolare ciò, però dal punto di vista pratico non sembra impossibile. Mi sembra strano che qualcuno esperto di teoria dei grafi non si sia mai posto questo problema e di conseguenza creare delle particolari routine per calcolarli con certi software

[feddy]

Potresti andare sulla GitHub repo di qualche libreria famosa per quello che ti serve e aprire un issue oppure chidedere sulla mailing list. Puo' essere che sia effettivamente semplice e molti lo facciano a mano, ma visto che non so nemmeno di cosa stai parlando potrei ovviamente sbagliarmi

[apatriarca]

Quanto è grande il tuo grafo? Sei interessato a valori specifici d'i e j o a un approccio generico? Immagino che un algoritmo brute-force non sia troppo difficile da implementare come punto di partenza. Forse anche un approccio di programmazione dinamica.

Ma per cosa ti serve? Forse esiste un algoritmo per fare quello che stai cercando di fare senza doverti calcolare tutti i sottografi.

[uomotorta]

Il grafo ha vertici $V(G)=\{1,2,3\}\cup\{4,5,6,7,8\}$ e insieme di spigoli $E(G)=\{ \{1,4},\{1,5\},\{1,6\},\{1,7\},\{1,8\},\{2,5\},\{2,6\},\{3,7\},\{3,8\}\}$. A mano è noioso ma non impossibile. Più che altro mi serviva un programma che calcolasse tutti i sottografi di $i$ spigoli e $j$ vertici per tutti i valori di $i$ e $j$ ammissibili, per avere la certezza in un certo senso di non aver commesso errori.

[apatriarca]

Di fatto vuoi calcolare tutti i sottografi del tuo grafo. Una volta trovati tutti i sottografi non è infatti difficile raggrupparli in base al loro numero di vertici e spigoli. Ho tuttavia ancora qualche domanda:
1. In che modo vuoi controllare di non aver commesso errori? Il numero di questi sottografi non è piccolissimo per cui mi chiedo come tu abbia l'intenzione di usarli.
2. Vuoi che questi sottografi abbiamo qualche proprietà? Devono per esempio essere connessi? Se non devono essere connessi, allora tutti i sottoinsiemi dei vertici sono sottografi. Siccome ci sono otto vertici hai già 256 sottografi senza aver considerato neanche uno spigolo. Dato un insieme di vertici, vuoi considerare tutti i sottografi con tali vertici o solo quelli che hanno il massimo numero di spigoli? Per esempio dato $\{1, 2, 5, 6\}$, vuoi considerare solo quello con spigoli $\{\{1, 5\}, \{1, 6\}, \{2, 5\}, \{2, 6\}\}$ o anche quelli con meno spigoli?

[uomotorta]

No no, la richiesta è proprio quella di trovare il numero (e come sono fatti) i sottografi di $i$ spigoli e $j$ vertici di $G$.
Indico con $n(i,j)$ il numero di sottografi di $G$ di $i$ spigoli e $j$ vertici. Allora $i\in\{0,1,...,9\}$ e $j\in\{1,...,8\}$. Bisogna mettersi qua a calcolare tutti gli $n(i,j)$
Ad esempio, posso fissare di volta in volta $j$ e poi far variare $i$.
Calcolo $n(i,1)$ per $i\in\{0,1,...,9\}$. Poi fisso $j=2$ e calcolo $n(i,2)$ per $i\in\{0,1,...,9\}$ e così via. Giustamente è abbastanza noioso fare questo lavoro, inoltre è anche abbastanza semplice commettere degli errori qua e là. Alla fine l'obbiettivo è quello di costruire il polinomio dei sottografi associato a $G$.

[apatriarca]

Per calcolare i sottografi $(i, j)$ devi calcolarti in pratica quelli $(i-1, j)$ o $(i, j-1)$. Quindi non ha senso calcolare i sottografi separatamente a meno di ripetere un sacco di lavoro. Infatti io personalmente calcolerei tutti i sottografi e poi li ordinerei nel vari gruppi perché potenzialmente più facile.