Explicar la frase "para cada par de elementos distintos" en referencia a un gráfico.

Question

En uno de mis algoritmo de cursos, es este:

Un subconjunto $S$ de vértices en un grafo dirigido $G$ es estrechamente relacionada si para cada par de distinta vértices ($v_i$, $v_j$) en $S$, $v_i$ está conectado a $v_j$ y $v_j$ está conectado a $v_i$.

Y, a continuación, en el ejemplo siguiente gráfico se da para esta proposición:

Tal vez yo no entiendo lo que significa esa frase. Lo que yo pienso: Un nodo, decir $E$ nunca puede volver a ser un par ordenado $(v_i, v_j)$, es decir. si $(E, A)$,$\lnot (E, [someOtherNode]) $, ya que es un par ordenado (creo). Pero vemos claramente que hay aquí $(E,A)$$(E,D)$.

¿Cómo debo interpretar correctamente esta frase. ¿Qué significa exactamente? Gracias.

Answer 1

También, "conectado" no significa un borde dirigido, pero dirigido camino.

Answer 2

Creo que "para cada par de vértices distintos $(v_i, v_j)$ $S \times S$" significa

"para cada % de $(v_i, v_j) \in S \times S$, $v_i \neq v_j$."

Answer 3

Desde su subconjunto $S$ de los vértices en los que se puede construir un conjunto de pares $P$ donde $(v,w) \in P$ si hay una trayectoria de $v$ $w$(no se limitan necesariamente a $S$). El conjunto está fuertemente conectado si $$ \forall v,w\S, ( v\neq w \Rightarrow (v,w) \P \cuña (w,v) \P) $$ Deje $S=G$ en el ejemplo de la gráfica. Observe que $(A,B)$, $(B,C)$, $(C,D)$, $(D,E)$, $(E,A)$ están todos en $P$. Así que por transitividad, cada par de los distintos vértices es en $P$.

La palabra distinct en la definición de las reglas de la exigencia de que $(v,v) \in P$. Sin embargo, parece que $(v,w) \in P \wedge (w,v) \in P$ implicaría que $(v,v)\in P$, de todos modos.

No estoy seguro de lo que quieres decir por "válida" de par. Cualquier pareja puede ser en $P$; la condición es sólo que ciertos pares debe ser en $P$.