Grafo orientado

Un gráfico orientado sinxelo

En matemáticas, e máis concretamente na teoría de grafos, un grafo orientado (ou grafo dirixido ou dígrafo) é un grafo que está formado por un conxunto de vértices conectados por arestas orientadas, que son arestas onde se distingue un orixe dun final normalmente representado por unha frecha.

Definición

En termos formais, un grafo orientado é un par ordenado G = (V, A) onde

• V é un conxunto cuxos elementos se chaman vértices, nós ou puntos;
• A é un conxunto de pares ordenados de vértices, chamados arestas, arestas orientadas (ás veces chamado E en vez de A), frechas ou liñas ou ligazóns dirixidas.

Diferénciase dun grafo ordinario ou non orientado, en que este último defínese en termos de pares de vértices non ordenados, que normalmente se denominan arestas, ligazóns ou liñas.

Tipos de grafos orientados

Subclases

Un grafo acíclico orientado sinxelo

Un torneo en 4 vértices

• Os Grafos orientados simétricos son grafos orientados onde todosas arestas aparecen dúas veces, un en cada dirección (é dicir, para cada frecha que pertence ao dígrafo, tamén lle pertence a frecha inversa correspondente).
• Os Grafos orientados sinxelos son grafos orientados que non teñen bucles (frechas que ligan directamente os vértices consigo mesmos) e sen múltiples frechas cos mesmos nodos orixe e destino.
  • Os Grafos orientados completos son grafos orientados simples onde cada par de vértices está unido por un par simétrico de arcos orientados (é equivalente a un grafo completo non orientado coas arestas substituídas por pares de arestas inversas).
  • Os Digrafos semicompletos son digrafos simples onde hai un arco entre cada par de vértices. .
  • Os Digrafos cuasi-transitivos son digrafos simples onde para cada tripla x, y, z de distintos vértices con arcos de x a y e de y a z, hai un arco entre x e z. Pode haber só un arco entre x e z ou dous arcos en direccións opostas.
  • Os Grafos orientados simples son grafos orientados que non teñen pares opostos de arestas orientadas (é dicir, como máximo un de (x, y) ou (y, x) poden ser frechas do grafo). Dedúcese que un grafo orientado é un grafo orientado puro se e só se non ten 2 ciclos. Este grafo pódese obter aplicando unha única orientación a un grafo non orientado.
    • Torneos son grafos orientados obtidos escollendo unha dirección para cada aresta en grafos completos non orientados. Un torneo é un digrafo semicompleto.
    • Un grafo orientado é acíclico se non ten ciclos orientados. O nome habitual deste digrafo é grafo acíclico orientado (DAG polas súas siglas en inglés).
      • As multiárbores son DAG nos que non hai dous camiños orientados distintos desde o mesmo vértice inicial ata o mesmo vértice final.
      • As árbores orientadas ou poliárbores son DAG formadas ao orientar as arestas das árbores (grafos conexos, acíclicos non orientados).
        • As árbores con raíz son árbores orientadas nas que todas as arestas da árbore subxacente non orientadas están dirixidas cara a fóra ou todas cara á raíz. (chámanse, respectivamente, arborescencias ou árbores cara adentro).

Terminoloxía básica

Grafo orientado coa matriz de incidencia correspondente

Considérase que unha aresta (x, y) está orientado de x a y; y chámase cabeza (ou orixe) e x cola (ou destino) da aresta. Dise que y é un sucesor directo de x e x dise que é un predecesor directo de y. Se un camiño leva de x a y, entón dise que y é sucesor de x e accesíbel desde x, e que x é un predecesor de y. A aresta ou arco (y, x) chámase arco invertido de (x, y).

Unha representación matricial para un grafo orientado é a súa matriz de incidencia.

Grao de entrada e grao de saída

Un grafo orientado con vértices etiquetados (grao de entrada, grao de saída)

Para un vértice, o número de extremos de cabeza adxacentes a un vértice chámase grao de entrada do vértice e o número de extremos de cola adxacentes a un vértice é o seu grao de saída (chamado factor de ramificación nas árbores).

Sexan G = (V, E) e v ∈ V. O grao de entrada de v desígnase deg^- (v) e o seu grao de saída denótase deg⁺ (v).

Un vértice con deg⁻(v) = 0 chámase fonte, xa que é a orixe de cada un dos seus arcos de saída. Do mesmo xeito, un vértice con deg⁺(v) = 0 chámase sumidoiro, xa que é o final de cada un dos seus arcos entrantes.

A fórmula da suma de graos indica que, para un grafo orientado,

$\sum _{v\in V}\deg ^{-}(v)=\sum _{v\in V}\deg ^{+}(v)=|E|.$

Se para cada vértice v ∈ V, deg⁺(v) = deg⁻(v), o grafo chámase grafo orientado equilibrado.

Secuencia de graos

A secuencia de graos dun grafo dirixido é a lista dos seus pares de graos de entrada e de saída; para o exemplo anterior temos a secuencia de graos ((2, 0), (2, 2), (0, 2), (1, 1)). A secuencia de graos é unha invariante do grafo orientado polo que os grafos orientados isomorfos teñen a mesma secuencia de graos. Porén, a secuencia de graos, en xeral, non identifica de forma única un grafo orientado; nalgúns casos, os dígrafos non isomorfos teñen a mesma secuencia de graos.

O problema de realización dun grafo dirixido é un problema de decisión na teoría de grafos. Dados os pares de números enteiros non negativos $((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))$, o problema pregúntase se existe un grafo dirixido simple tal que todo vértice $v_{i}$ ten grao de entrada $a_{i}$ e grao de saída $b_{i}$.

Conectividade dos grafos orientados

Un grafo orientado é conexo (ou debilmente conexo ) se o grafo subxacente non orientado que se obtén substituíndo todas as arestas orientadas do grafo por arestas non orientadas é un grafo conexo.

Un grafoo orientado é fortemente conexo se contén un camiño orientado de x a y (e de y a x) para todo par de vértices (x, y). Os compoñentes fortes son os máximos subgrafos fortemente conexos.

Un grafo con raíz conexo (ou grafo de fluxo) é aquel no que existe un camiño orientado a cada vértice desde un vértice raíz distinguido.

Véxase tamén

Bibliografía

• Bang-Jensen, Jørgen; Gutin, Gregory (2000). Digraphs: Theory, Algorithms and Applications. Springer. ISBN 1-85233-268-9. (the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 ISBN 1-84800-997-6).
• Bang-Jensen, Jørgen; Gutin, Gregory (2018). Classes of Directed Graphs. Springer. ISBN 978-3319718408. .
• Bondy, John Adrian; Murty, U. S. R. (1976). Graph Theory with Applications. North-Holland. ISBN 0-444-19451-7. .
• Diestel, Reinhard (2005). Graph Theory (3rd ed.). Springer. ISBN 3-540-26182-6.  (the electronic 3rd edition is freely available on author's site).
• Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965). Structural Models: An Introduction to the Theory of Directed Graphs. New York: Wiley. .
• Number of directed graphs (or directed graphs) with n nodes from On-Line Encyclopedia of Integer Sequences

Outros artigos

• Relación binaria
• Diagrama de fluxo
• Globular set
• Glosario de teoría de grafos
• Teoría de grafos
• Teoría de redes
• Orientación
• Preorde
• Ordenamento topolóxico
• Grafo transposto
• Problema do ciclo de peso cero

Ligazóns externas

• Chapter 6: Directed graphs