Gráfico direcionado - Directed graph

Um gráfico direcionado simples. Aqui, a seta de duas pontas representa duas arestas distintas, uma para cada direção.

Em matemática , e mais especificamente na teoria dos grafos , um gráfico direcionado (ou dígrafo ) é um gráfico que é composto de um conjunto de vértices conectados por arestas direcionadas, freqüentemente chamadas de arcos .

Definição

Em termos formais, um gráfico direcionado é um par ordenado G = ( V , A ), onde

  • V é um conjunto cujos elementos são chamados de vértices , nós ou pontos ;
  • A é um conjunto de pares ordenados de vértices, chamados arcos , arestas direcionadas (às vezes simplesmente arestas com o conjunto correspondente denominado E em vez de A ), setas ou linhas direcionadas .

Ele difere de um gráfico comum ou não direcionado , pois este último é definido em termos de pares não ordenados de vértices, que geralmente são chamados de arestas , links ou linhas .

A definição acima mencionada não permite que um gráfico direcionado tenha várias setas com os mesmos nós de origem e destino, mas alguns autores consideram uma definição mais ampla que permite que os gráficos direcionados tenham tais arcos múltiplos (ou seja, eles permitem que o conjunto de arco seja um multiset ) . Mais especificamente, essas entidades são tratadas como multigrafos direcionados (ou multidigrafos ).
Por outro lado, a definição acima mencionada permite que um grafo direcionado tenha loops (isto é, arcos que conectam nós diretamente a si mesmos), mas alguns autores consideram uma definição mais restrita que não permite que grafos direcionados tenham loops. Mais especificamente, os gráficos direcionados sem loops são tratados como gráficos direcionados simples , enquanto os gráficos direcionados com loops são tratados como dígrafos de loop (consulte a seção Tipos de gráficos direcionados ).

Tipos de gráficos direcionados

Subclasses

Um gráfico acíclico direcionado simples
Um torneio em 4 vértices
  • Os gráficos direcionados simétricos são gráficos direcionados onde todas as arestas são bidirecionadas (ou seja, para cada seta que pertence ao dígrafo, a seta invertida correspondente também pertence a ele).
  • Os gráficos direcionados simples são gráficos direcionados que não possuem loops (setas que conectam diretamente os vértices a si mesmos) e nenhuma seta múltipla com os mesmos nós de origem e destino. Conforme já apresentado, no caso de setas múltiplas, a entidade é geralmente tratada como multigrafo direcionado . Alguns autores descrevem dígrafos com loops como dígrafos de loop .
    • Grafos direcionados completos são
    grafos direcionados simples onde cada par de vértices é unido por um par simétrico de arcos direcionados (é equivalente a um gráfico completo não direcionado com as arestas substituídas por pares de arcos inversos). Segue-se que um dígrafo completo é simétrico.
  • Digrafos multipartidos semiplena são digrafos simples em que o conjunto de vértice é partição em conjuntos partite tal que, para cada par de vértices x e y em diferentes conjuntos partite, há um arco entre x e y . Note-se que pode haver um arco entre x e y ou dois arcos em direcções opostas.
  • Os dígrafos semicompletos são dígrafos simples onde há um arco entre cada par de vértices. Cada dígrafo semicompleto é um dígrafo multipartido semicompleto, onde o número de vértices é igual ao número de conjuntos de partitos.
  • Os dígrafos quase transitivos são dígrafos simples onde para cada triplo x , y , z de vértices distintos com arcos de x a y e de y a z , há um arco entre x e z . Observe que pode haver apenas um arco entre x e z ou dois arcos em direções opostas. Um dígrafo semicompleto é um dígrafo quase transitivo. Existem extensões de dígrafos quase transitivos chamados dígrafos k -quase transitivos.
  • Os gráficos orientados são gráficos direcionados sem arestas bidirecionadas (ou seja, no máximo um de ( x , y ) e ( y , x ) podem ser setas do gráfico). Segue-se que um gráfico direcionado é um gráfico orientado se e somente se não tiver nenhum 2-ciclo . direcionados . Observe que um torneio é um dígrafo semicompleto.
  • Os gráficos acíclicos direcionados (DAGs) são gráficos direcionados sem ciclos direcionados .
    • Múltiplas árvores são DAGs em que dois caminhos distintos direcionados de um único vértice inicial não se encontram no mesmo vértice final.
    • Árvores orientadas ou polytrees são DAGs formados orientando as bordas de gráficos acíclicos não direcionados.
    árvores orientadas nas quais todas as arestas da árvore não direcionada subjacente são direcionadas para longe ou em direção à raiz (elas são chamadas de árvores externas e internas , respectivamente.

Digrafos com propriedades suplementares

Terminologia Básica

Gráfico orientado com matriz de incidência correspondente

Um arco ( x , y ) é considerado direcionado de x para y ; y é chamado de cabeça e x é chamado de cauda do arco; y é dito ser um sucessor direto de x e x é dito ser um predecessor direto de y . Se um caminho conduz a partir de x para y , então Y é dito ser um sucessor de x e acessível a partir de X , e X é dito ser um antecessor de y . O arco ( y , x ) é chamado de arco reverso de ( x , y ) .

A matriz de adjacência de uma multidigraph com laçadas é o valor de número inteiro de matriz com linhas e colunas correspondentes aos vértices, onde uma entrada nondiagonal um ij é o número de arcos de vértice i ao vértice j , e a entrada diagonal um II é o número de loops no vértice i . A matriz de adjacência de um grafo direcionado é única até a permutação idêntica de linhas e colunas.

Outra representação de matriz para um gráfico direcionado é sua matriz de incidência .

Veja a direção para mais definições.

Indegree e outdegree

Um gráfico direcionado com vértices rotulados (indegree, outdegree)

Para um vértice, o número de extremidades da cauda adjacentes a um vértice é chamado de indegree do vértice e o número de extremidades da cauda adjacentes a um vértice é seu grau externo (chamado de fator de ramificação nas árvores).

Deixe G = ( V , A ) e vV . O indegree de v é denotado deg - ( v ) e seu outdegree é denotado deg + ( v ).

Um vértice com deg - ( v ) = 0 é chamado de fonte , pois é a origem de cada um de seus arcos de saída. Da mesma forma, um vértice com deg + ( v ) = 0 é chamado de sumidouro , pois é o final de cada um de seus arcos de entrada.

A fórmula de soma de graus afirma que, para um gráfico direcionado,

Se para cada vértice vV , deg + ( v ) = deg - ( v ) , o gráfico é chamado de gráfico direcionado balanceado .

Sequência de graus

A seqüência de graus de um gráfico direcionado é a lista de seus pares indegree e outdegree; para o exemplo acima, temos a sequência de graus ((2, 0), (2, 2), (0, 2), (1, 1)). A sequência de graus é um gráfico invariante direcionado, portanto, os gráficos direcionados isomórficos têm a mesma sequência de graus. No entanto, a sequência de graus não identifica, em geral, exclusivamente um gráfico direcionado; em alguns casos, dígrafos não isomórficos têm a mesma sequência de graus.

O problema de realização de gráfico direcionado é o problema de encontrar um gráfico direcionado com a sequência de graus de uma dada sequência de pares inteiros positivos . (Os pares finais de zeros podem ser ignorados, uma vez que são trivialmente realizados adicionando um número apropriado de vértices isolados ao gráfico direcionado.) Uma sequência que é a sequência de graus de algum gráfico direcionado, ou seja, para a qual o problema de realização de gráfico direcionado tem uma solução , é chamado de gráfico direcionado ou sequência gráfica direcionada. Este problema pode ser resolvido pelo algoritmo de Kleitman – Wang ou pelo teorema de Fulkerson – Chen – Anstee .

Conectividade de gráfico direcionado

Um gráfico direcionado é fracamente conectado (ou apenas conectado ) se o gráfico subjacente não direcionado obtido pela substituição de todas as arestas direcionadas do gráfico por arestas não direcionadas for um grafo conectado .

Um gráfico direcionado é fortemente conectado ou forte se contém um caminho direcionado de x para y (e de y para x ) para cada par de vértices ( x , y ) . Os componentes fortes são os subgráficos máximos fortemente conectados.

Um gráfico de raiz conectada (ou gráfico de fluxo ) é aquele em que existe um caminho direcionado para cada vértice a partir de um vértice de raiz distinto .

Veja também

Notas

Referências