Gráfico direcionado - Directed graph
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
- 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
- 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 .
- Os torneios são gráficos orientados obtidos escolhendo uma direção para cada borda em gráficos completos não
-
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.
Digrafos com propriedades suplementares
-
Os gráficos direcionados ponderados (também conhecidos como redes direcionadas ) são (simples) gráficos direcionados com pesos atribuídos às suas setas, de forma semelhante aos gráficos ponderados (que também são conhecidos como redes não direcionadas ou redes ponderadas ).
- Redes de fluxo são grafos direcionados ponderados onde dois nós são distinguidos, uma fonte e um sumidouro .
-
Grafos direcionados enraizados (também conhecidos como gráficos de fluxo ) são dígrafos nos quais um vértice foi distinguido como a raiz.
- Os gráficos de fluxo de controle são dígrafos enraizados usados na ciência da computação como uma representação dos caminhos que podem ser percorridos por um programa durante sua execução.
- Os gráficos de fluxo de sinal são gráficos direcionados nos quais os nós representam as variáveis do sistema e os ramos (arestas, arcos ou setas) representam as conexões funcionais entre pares de nós.
- Os gráficos de fluxo são dígrafos associados a um conjunto de equações lineares algébricas ou diferenciais.
- Os diagramas de estado são multigrafos direcionados que representam máquinas de estados finitos .
- Os diagramas comutativos são dígrafos usados na teoria das categorias , onde os vértices representam objetos (matemáticos) e as setas representam morfismos, com a propriedade de que todos os caminhos direcionados com os mesmos pontos inicial e final levam ao mesmo resultado por composição.
- Na teoria dos grupos de Lie , um quiver Q é um grafo direcionado servindo como o domínio de, e assim caracterizando a forma de, uma representação V definida como um functor , especificamente um objeto da categoria de functor FinVct K F ( Q ) onde F ( Q ) é a categoria livre em Q que consiste de caminhos em Q e FinVct K é a categoria de finitos-dimensional espaço vectorial mais de um campo K . As representações de uma aljava rotulam seus vértices com espaços vetoriais e suas arestas (e, portanto, caminhos) compatíveis com transformações lineares entre eles e se transformam por meio de transformações naturais .
Terminologia Básica
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
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 v ∈ V . 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 v ∈ V , 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
- Relação binária
- Gráfico de Coates
- Fluxograma DRAKON
- Fluxograma
- Glossário de teoria dos grafos
- Teoria dos grafos
- Gráfico (tipo de dados abstratos)
- Teoria da rede
- Orientação
- Pedido antecipado
- Classificação topológica
- Gráfico de transposição
- Gráfico de restrição vertical
- Conjunto globular
Notas
Referências
-
Bang-Jensen, Jørgen; Gutin, Gregory (2000), Digraphs: Theory, Algorithms and Applications , Springer , ISBN 1-85233-268-9
(a 1ª edição corrigida de 2007 está agora disponível gratuitamente no site dos autores; a 2ª edição apareceu em 2009, ISBN 1-84800-997-6 ). - Bang-Jensen, Jørgen; Gutin, Gregory (2018), Classes of Directed Graphs , Springer , ISBN 3319718401.
- Bondy, John Adrian ; Murty, USR (1976), Graph Theory with Applications , North-Holland, ISBN 0-444-19451-7.
- Diestel, Reinhard (2005), Graph Theory (3ª ed.), Springer , ISBN 3-540-26182-6 (a 3ª edição eletrônica está disponível gratuitamente no site do autor).
- Harary, Frank ; Norman, Robert Z .; Cartwright, Dorwin (1965), Modelos Estruturais: Uma Introdução à Teoria dos Gráficos Direcionados , Nova York: Wiley.
- Número de gráficos direcionados (ou gráficos direcionados) com n nós da Enciclopédia On-Line de Sequências Inteiras