Grafo orientado

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  onde . , Chapter 1., Section 1.10. , Section 10.

 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 
dereita|miniatura| Un grafo acíclico orientado sinxelo
dereita|miniatura| 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)., capítulo 7 de Yeo.
 Os Digrafos semicompletos son digrafos simples onde hai un arco entre cada par de vértices. , capítulo 2 de Bang-Jensen e Havet..
 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. , capítulo 8 de Galeana-Sanchez e Hernández-Cruz.
 Os Grafos orientados simples son grafos orientados que non teñen pares opostos de arestas orientadas (é dicir, como máximo un de  ou  poden ser frechas do grafo). Dedúcese que un grafo orientado é un grafo orientado puro se e só se non ten 2 ciclos., Sección 1.10. 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)., capítulo 3 de Gutin.
 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 
miniatura| Grafo orientado coa matriz de incidencia correspondente
Considérase que unha aresta  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  chámase arco invertido de .

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

 Grao  de entrada e grao de saída 
miniatura| 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  e . 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  chámase fonte, xa que é a orixe de cada un dos seus arcos de saída. Do mesmo xeito, un vértice con  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,



Se para cada vértice , , 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 , o problema pregúntase se existe un grafo dirixido simple tal que todo vértice  ten grao de entrada  e grao de saída .

 Conectividade dos grafos orientados 
Un grafo orientado é conexo (ou debilmente conexo  p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).) 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 . 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.

 Notas 


 Véxase tamén 

 Bibliografía 
 (the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 ).
 .
 .
  (the electronic 3rd edition is freely available on author's site).
 .
 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

Categoría:Teoría de grafos