¿Se gráfico dual se define para un grafo dirigido?

Question

La definición que yo sepa para el grafo dual es para un grafo no dirigido.

Me pregunto si el grafo dual pueden ser definidos para un grafo dirigido? Si sí, ¿cómo es la orientación del grafo dual determinado?

La motivación de mi pregunta es que en el grafo planar s-t de la red, la mínima s-t corte de problema en la red, y el más corto s-t ruta problema en su "doble" de la red se puede convertir de uno a otro. Por favor, consulte a mi pregunta anterior. Entonces me pregunto ¿qué acerca de la red está dirigida?

Gracias!

Answer 1

Deje $D$ ser un avión de grafo dirigido con grafo no dirigido subyacente $G$. Supongamos que la dirigida a los bordes de $D$$\{\vec{e}_1,\dots, \vec{e}_n\}$, y que el grafo bordes de $G$$\{e_1,\dots,e_n\}$. Definir $G^*$ a ser el grafo dual de $G$. A continuación, $G^*$ tiene bordes $\{e_1^\perp,\dots, e_n^\perp\}$ donde $e_i^\perp$ es dual a $e_i$. Con el fin de construir el doble de la de grafo dirigido $D$, asignar las orientaciones de los bordes, de modo que cada par $(e_i,e_i^\perp)$ formas positivamente orientada a base de $\mathbb{R}^2$ (cuando los gráficos $D$ $D^*$ se unen en el plano de tal manera que las caras de $D$ son los vértices de $D^*$, y viceversa).

Orientado matroids puede ser visto como generalizaciones de gráficos, y tienen una compatible con la noción de la dualidad. Específicamente, deje $M(D)$ ser orientado matroid asociados a $D$, y deje $M(D)^*$ ser el doble orientada matroid. A continuación,$M(D)^*=M(D^*)$.

Answer 2

Si un gráfico debe satisfacer las siguientes condiciones entonces de u cn decir tht existe la dualidad de un grafo dirigido... *. G == G . 1) región => vértices... 2) bordes bordes... 3) pendiente borde lazo... 4) paralelo borde borde de serie... 5) número de aristas que forma un límite de región deg de vértice...**