PROFILPELAJAR.COM

Um grafo orientado,^[1] grafo dirigido,^[2] grafo direcionado^[3] ou digrafo é um par $G=(V,A)$ (algumas vezes $G=(V,E)$ )^(edge) de:^[4]^[5]^[6]

Um conjunto V, cujos elementos são chamados vértices ou nodos,
um conjunto A de pares ordenados de vértices, chamados arcos, arestas direcionadas, ou setas (e às vezes simplesmente arestas com o conjunto correspondente chamado E ao invés de A).

Ele difere de um grafo não-direcionado comum, em que o último é definido em termos de pares não ordenados de vértices, que são normalmente chamados arestas.

Por exemplo, ser possível ir de um nó A para um nó B, mas não o contrário através desse arco.

Às vezes, um digrafo é chamado de um digrafo simples para distinguí-lo de um multigrafo direcionado (ou multidigrafo ou ainda quiver), em que os arcos constituem um multiconjunto, ao invés de um conjunto, de pares ordenados de vértices. Além disso, em um digrafo simples laços não são permitidos. Por outro lado, alguns textos permitem laços, arcos múltiplos, ou ambos em um digrafo.

Terminologia básica

Um arco $e=(x,y)$ é considerado ser 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 composto por um ou mais arcos sucessivos leva de $x$ para $y,$ então $y$ é dito ser um successor de $x,$ e $x$ é dito ser um predecessor de $y.$ O arco $(y,x)$ é chamado de arco $(x,y)$ invertido.

Um grafo direcionado G é chamado de simétrico se, para cada arco, que pertence à G, o arco invertido correspondente também pertence à G. Um grafo dirigido simétrico sem laços é equivalente a um grafo não orientado com os pares de arcos invertidos substituído por arestas, assim o número de arestas é igual ao número de arcos pela metade.

A orientação de um grafo grafo não-direcionado simples é obtida através da atribuição de um sentido para cada lado. Qualquer grafo direcionado construído desta forma é chamado de um grafo orientado. A distinção entre um grafo direcionado simples e um grafo orientado é que se $x$ e $y$ são vértices, um grafo direcionado simples permite tanto $(x,y)$ quanto $(y,x)$ como arestas, enquanto apenas uma é permitida em um grafo orientado.^[5]

Um digrafo ponderado é um digrafo com pesos atribuídos a seus arcos, à semelhança de um grafo ponderado.

A matriz de adjacência de um digrafo (com laços e arcos múltiplos) é uma matriz inteira com linhas e colunas correspondendo aos nodos do digrafo, onde uma entrada não-diagonal $a_{ij}$ é o número de arcos do nó i para o nó j, e a entrada diagonal $a_{ii}$ é o número de laços no nó i. A matriz de adjacência de um digrafo é única até as permutações de linhas e colunas.

Outra representação de matriz para um dígrafo é sua matriz de incidência.

Veja glossário para mais definições.

Graus de saída e graus de entrada

Um digrafo com vértices rotulados (saída ou entrada)

Para um nodo, o número de pontos de extremidade adjacente à cabeça de um nó é chamado de grau de entrada do nodo e o número de pontos de extremidade da cauda é o seu grau de saída.

O grau de entrada é denotado $\deg ^{-}(v)$ e o grau de saída como $\deg ^{+}(v)..$ Um vértice com $\deg ^{-}(v)=0$ é chamado de fonte, uma vez que é a origem de cada uma das suas arestas incidentes. Da mesma forma, um vértice com $\deg ^{+}(v)=0$ é chamado de sumidouro (ou poço).

A fórmula da soma dos graus afirma que, para um grafo direcionado

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

Se para cada nodo, v ∈ V, $\deg ^{+}(v)=\deg ^{-}(v),$ o grafo é chamado de digrafo balanceado.

Conectividade de digrafos

Um digrafo G é chamado de fracamente conectado (ou apenas conectado^[4]^p. 19) se o grafo subjacente não-direcionado obtido através da substituição de todas as arestas de G por arestas não direcionadas é um grafo conexo. Um digrafo é fortemente conectado ou forte se ele contém um caminho orientado de u a v e um caminho orientado de v a u para cada par de vértices u,v. Os componentes fortes são os subgrafos máximo fortemente conectados.

Classes de digrafos

Um digrafo acíclico é um grafo direcionado sem ciclos direcionados.

Uma árvore enraizada naturalmente se define como um digrafo acíclico, se todas as arestas da árvore subjacentes são dirigidas para longe da raiz.

Um torneio é um grafo orientado obtido ao se escolher uma direção para cada aresta em um grafo completo não-direcionado.

Na teoria dos grupos de Lie, um quiver Q é um grafo direcionado servindo como o domínio do e, portanto, caracterizando a forma de, uma representação V definida como um functor, mais especificamente um objeto da categoria functor FinVct_K^F(Q) onde F(Q) é a categoria livre em Q constituída por caminhos em Q e FinVct_K é a categoria de espaços vetoriais de dimensão finita sobre um campo K. Representações de um quiver rótulam seus vértices com espaços vetoriais e suas arestas (e, portanto, caminhos) de modo compatível com transformações lineares entre eles, e transformam através das transformações naturais.

Ver também

Quiver

Referências

↑ BOAVENTURA NETTO, Paulo Oswaldo (2001). Grafos. Teoria, Modelos Algoritmos. São Paulo: Edgard Blücher. p. 7-8. ISBN 85-212-0292-X .
↑ FURTADO, Antonio Luz (1973). Teoria dos Grafos. Algoritmos. Rio de Janeiro, Guanabara: LTC/Editora da USP. CDD 511.2076 .
↑ SZWARCFITER, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. p. 64. ISBN 85-7001-341-8
↑ ^a ^b BANG-JENSEN, Jørgen; GUTIN, Gregory (2000). Digraphs: Theory, Algorithms and Applications. [S.l.]: Springer. ISBN 1-85233-268-9
↑ ^a ^b DIESTEL, Reinhard (2005). Graph Theory 3ª ed. [S.l.]: Springer. ISBN 3-540-26182-6
↑ BONDY, John Adrian; MURTY, U. S. R. (1976). Graph Theory with Applications. [S.l.]: North-Holland. ISBN 0-444-19451-7. Consultado em 29 de setembro de 2010. Arquivado do original em 13 de abril de 2010 .