Cierre transitivo de multigrafos

Question

El cierre transitivo de un grafo dirigido es otro grafo dirigido que codifica la accesibilidad de los nodos desde otros nodos. Si $G$ es un grafo, la arista $(v_1,v_2)$ está en su cierre transitivo $G^{tc}$ si existe un camino dirigido desde $v_1$ à $v_2$ en $G$ .

A multigráfica puede tener múltiples aristas entre nodos. La pregunta es: ¿cuáles serían las definiciones naturales del cierre transitivo de un multigrafo?

Una respuesta obvia sería el cierre transitivo del grafo inducido (el mismo grafo con múltiples aristas entre vértices sustituidas por una única arista).

¿Existen ya grafos interesantes derivados de un multigrafo que puedan ganarse el título de "cierre transitivo"?

Answer 1

Obsérvese que el término cierre transitivo proviene de la teoría de conjuntos. Todo grafo dirigido (simple) $G$ define de forma natural una relación $R(G)$ en $V(G)$ . El cierre transitivo $G'$ de $G$ es el grafo dirigido (simple) $G'$ en $V(G)$ tal que $R(G')$ es el cierre transitivo de $R(G)$ . Ciertamente no soy un experto, pero supongo que necesitamos generalizar la noción de relación, donde un elemento puede estar relacionado con otro elemento con multiplicidad.

En fin, después de toda esta divagación otra posible respuesta es que cada uno $u, v \in V(G)$ , poner $n(u,v)$ aristas dirigidas desde $u$ à $v$ donde $n(u,v)$ es el número máximo de caminos dirigidos internamente disjuntos desde $u$ à $v$ .

Answer 2

Si consideramos un multigrafo como conjunto de nodos y conjunto de relaciones, donde cada número de aristas entre dos nodos tienen relación correlativa (es decir. $(a,b) \in R_N$ significa que "a y b están conectados por N aristas" ), podemos hacer un cierre transitivo para cada relación y, por lo tanto, para el "multigrafo completo".

Si, por definición, $(a,b) \in R_N \Rightarrow (a,b) \in R_{N-1}$ (es decir $(a,b) \in R_N$ significa que a y b están conectados por N o más aristas ), entonces el cierre transitivo del grafo inducido debe ser el mismo que el grafo inducido del cierre transitivo.

Lo siento por mi inglés :-(

Answer 3

Voy a sugerir un enfoque de los cierres transitivos que dará lugar a la definición habitual, en el caso especial de un dígrafo "simple" que tiene una matriz de adyacencia con entradas en {0,1}. A saber: el cierre transitivo puede considerarse como un valor máximo sobre los pesos de los recorridos, donde consideramos los arcos múltiples como arcos con mayor peso. Podemos entonces formular dos definiciones diferentes según cómo se quiera definir el peso de un paseo.

Por todas partes, A(D) denota la matriz de adyacencia de un (multi)digrafo D .

A. Enfoque "Max-min

Si se desea que el peso de un paseo sea el peso mínimo de cualquier arista (según el principio de que una cadena es tan fuerte como el eslabón más débil), se definiría entonces

$\begin{align} A(T)\_{a,b} \;\;=\quad \max_{\ell \in \mathbb N} \; \max_{\substack{v \in V(D)^{\ell+1} \\\\ (v_0, v_{\ell+1}) = (a,b)}} \min_{0 \le j \le \ell}\; \;\Bigl[ A(D)\_{v_j,v_{j+1}} \Bigr]\;, \end{align}$

bastante sencillo.

B. Enfoque "combinatorio

Si prefiere concebir los pesos de los recorridos como un producto de los pesos de los arcos constituyentes, como ocurre en las descripciones de suma sobre recorridos de los procesos probabilísticos, debería definir más bien $\begin{align} A(T)\_{a,b} \;\;=\quad \sup_{\ell \in \mathbb N} \; \max_{\substack{v \in V(D)^{\ell+1} \\\\ (v_0, v_{\ell+1}) = (a,b)}} \;\; \prod_{j=0}^\ell \Bigl[ A(D)\_{v_j,v_{j+1}} \Bigr] \;, \end{align}$

donde el supremum puede sustituirse por un máximo en el caso de que (como con la mezcla probabilística) todos los pesos de arco estén entre -1 y 1, si la red no contiene ningún ciclo dirigido, o condiciones similares.

(Si su dígrafo no es acíclico, y algunos pares de vértices en algún componente fuertemente conectado contiene múltiples arcos entre ellos, y no le gusta la idea de dígrafos con infinitos arcos entre vértices, puede que desee reemplazar el máximo sobre tuplas con un máximo sobre secuencias no repetitivas, en cuyo caso el supremum también se convierte en un máximo. Esto corresponde a tomar wieghts máximos de caminos, en lugar de paseos).