Gráfico (matemática discreta) - Graph (discrete mathematics)

Um gráfico com seis vértices e sete arestas.

Em matemática , e mais especificamente na teoria dos grafos , um gráfico é uma estrutura que corresponde a um conjunto de objetos em que alguns pares de objetos estão em algum sentido "relacionados". Os objetos correspondem a abstrações matemáticas chamadas vértices (também chamados de nós ou pontos ) e cada um dos pares de vértices relacionados é chamado de aresta (também chamado de link ou linha ). Normalmente, um gráfico é representado em forma de diagrama como um conjunto de pontos ou círculos para os vértices, unidos por linhas ou curvas para as arestas. Os gráficos são um dos objetos de estudo da matemática discreta .

As bordas podem ser direcionadas ou não direcionadas. Por exemplo, se os vértices representam as pessoas em uma festa, e existe uma aresta entre duas pessoas, se eles apertam as mãos, então este gráfico é não dirigida, porque qualquer pessoa A pode agitar as mãos com uma pessoa B somente se B também agita as mãos com um . Em contraste, se qualquer vantagem de uma pessoa A para uma pessoa B corresponde a A deve dinheiro a B , então este gráfico é direcionado, porque devido dinheiro não é necessariamente retribuído. O primeiro tipo de gráfico é chamado de gráfico não direcionado, enquanto o último tipo de gráfico é chamado de gráfico direcionado .

Os gráficos são o assunto básico estudado pela teoria dos grafos . A palavra "gráfico" foi usada pela primeira vez neste sentido por JJ Sylvester em 1878 em uma relação direta entre matemática e estrutura química (o que ele chamou de imagem gráfico-químico).

Definições

As definições da teoria dos grafos variam. A seguir estão algumas das maneiras mais básicas de definir gráficos e estruturas matemáticas relacionadas .

Gráfico

Um gráfico com três vértices e três arestas.

Um gráfico (às vezes chamado de gráfico não direcionado para distinguir de um gráfico direcionado ou gráfico simples para distinguir de um multigrafo ) é um par G = ( V , E ) , onde V é um conjunto cujos elementos são chamados de vértices (singular: vértice), e E é um conjunto de vértices emparelhados, cujos elementos são chamados de arestas (às vezes links ou linhas ).

O vértices x e y de um bordo { x , y } são chamados os pontos de extremidade do bordo. Diz- se que a aresta une x e y e incide em x e y . Um vértice pode não pertencer a nenhuma aresta, caso em que não está unido a nenhum outro vértice.

Um multigrafo é uma generalização que permite que várias arestas tenham o mesmo par de pontos finais. Em alguns textos, os multigrafos são simplesmente chamados de gráficos.

Às vezes, os gráficos podem conter loops , que são arestas que unem um vértice a si mesmo. Para permitir loops, a definição acima deve ser alterada definindo as arestas como multiconjuntos de dois vértices em vez de dois conjuntos. Esses gráficos generalizados são chamados de gráficos com loops ou simplesmente gráficos quando fica claro a partir do contexto que os loops são permitidos.

Geralmente, o conjunto de vértices V é considerado finito; isso implica que o conjunto de arestas também é finito. Grafos infinitos às vezes são considerados, mas são mais frequentemente vistos como um tipo especial de relação binária , já que a maioria dos resultados em gráficos finitos não se estendem ao caso infinito, ou precisam de uma prova bastante diferente.

Um gráfico vazio é um gráfico que possui um conjunto vazio de vértices (e, portanto, um conjunto vazio de arestas). A ordem de um gráfico é o seu número de vértices | V | . O tamanho de um gráfico é o seu número de arestas | E | . No entanto, em alguns contextos, como para expressar a complexidade computacional de algoritmos, o tamanho é | V | + | E | (caso contrário, um gráfico não vazio pode ter tamanho 0). O grau ou valência de um vértice é o número de arestas que incidem sobre ele; para gráficos com loops, um loop é contado duas vezes.

Em um gráfico de ordem n , o grau máximo de cada vértice é n - 1 (ou n se loops são permitidos), e o número máximo de arestas é n ( n - 1) / 2 (ou n ( n + 1) / 2 se loops forem permitidos).

As arestas de um grafo definem uma relação simétrica nos vértices, chamada de relação de adjacência . Especificamente, dois vértices x e y são adjacentes se { x , y } for uma aresta. Um grafo pode ser totalmente especificado por sua matriz de adjacência A , que é uma matriz quadrada, com A _ij especificando o número de conexões do vértice i ao vértice j . Enquanto isso, para um gráfico simples,, indicando desconexão ou conexão respectivamente (ou seja, uma aresta não pode começar e terminar no mesmo vértice). Os gráficos com auto-loops serão caracterizados por alguns ou todos serem iguais a um inteiro positivo, e os multigrafos (com várias arestas entre vértices) serão caracterizados por alguns ou todos serem iguais a um inteiro positivo. Grafos não direcionados terão uma matriz de adjacência simétrica ( ). ${\ displaystyle n \ times n}$${\ displaystyle A_ {ij} \ in \ {0,1 \}}$${\ displaystyle A_ {ii} = 0}$${\ displaystyle A_ {ii}}$${\ displaystyle A_ {ij}}$${\ displaystyle A_ {ij} = A_ {ji}}$

Gráfico direcionado

Um gráfico direcionado com três vértices e quatro arestas direcionadas (a seta dupla representa uma aresta em cada direção).

Um gráfico direcionado ou dígrafo é um gráfico no qual as arestas têm orientações.

Em um senso restrito, mas muito comum do termo, um gráfico direcionado é um par que compreende: ${\ displaystyle G = (V, E)}$

• ${\ displaystyle V}$, um conjunto de vértices (também chamados de nós ou pontos );
• ${\ displaystyle E \ subseteq \ {(x, y) \ mid (x, y) \ in V ^ {2} \; {\ textrm {and}} \; x \ neq y \}}$, um conjunto de arestas (também chamadas arestas direcionadas , links direcionados , linhas direcionadas , setas ou arcos ) que são pares ordenados de vértices (ou seja, uma aresta está associada a dois vértices distintos).

Para evitar ambigüidade, esse tipo de objeto pode ser chamado precisamente de gráfico simples direcionado .

Na borda dirigida a partir de , os vértices e são chamados os pontos finais da aresta, a cauda da borda e da cabeça da borda. A borda é dito para se juntar e e ser incidente sobre e sobre . Um vértice pode existir em um gráfico e não pertencer a uma aresta. A aresta é chamada de aresta invertida de . Arestas múltiplas , não permitidas na definição acima, são duas ou mais arestas com a mesma cauda e a mesma cabeça. ${\ displaystyle (x, y)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle y}$ ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (y, x)}$${\ displaystyle (x, y)}$

Em um sentido mais geral do termo permitindo múltiplas arestas, um gráfico direcionado é um triplo ordenado que compreende: ${\ displaystyle G = (V, E, \ phi)}$

• ${\ displaystyle V}$, um conjunto de vértices (também chamados de nós ou pontos );
• ${\ displaystyle E}$, Um conjunto de arestas (também chamados bordos dirigidos , ligações dirigidas , linhas dirigidas , setas ou arcos );
• ${\ displaystyle \ phi: E \ to \ {(x, y) \ mid (x, y) \ in V ^ {2} \; {\ textrm {and}} \; x \ neq y \}}$, uma função de incidência mapeando cada aresta para um par ordenado de vértices (ou seja, uma aresta está associada a dois vértices distintos).

Para evitar ambigüidade, esse tipo de objeto pode ser chamado precisamente de multígrafo direcionado .

Um loop é uma aresta que une um vértice a si mesma. Os gráficos direcionados, conforme definidos nas duas definições acima, não podem ter loops, porque um loop que une um vértice a si mesmo é a aresta (para um gráfico simples direcionado) ou incidente (para um multigrafo direcionado) que não está dentro . Portanto, para permitir loops, as definições devem ser expandidas. Para gráficos simples direcionados, a definição de deve ser modificada para . Para multigrafos direcionados, a definição de deve ser modificada para . Para evitar ambigüidade, esses tipos de objetos podem ser chamados precisamente de um gráfico simples direcionado que permite loops e um multigrafo direcionado que permite loops (ou aljava ), respectivamente. ${\ displaystyle x}$${\ displaystyle (x, x)}$${\ displaystyle \ {(x, y) \ mid (x, y) \ in V ^ {2} \; {\ textrm {e}} \; x \ neq y \}}$${\ displaystyle E}$${\ displaystyle E \ subseteq \ {(x, y) \ mid (x, y) \ in V ^ {2} \}}$${\ displaystyle \ phi}$${\ displaystyle \ phi: E \ to \ {(x, y) \ mid (x, y) \ in V ^ {2} \}}$

As arestas de um grafo simples direcionado que permitem loops é uma relação homogênea - nos vértices de que é chamada de relação de adjacência de . Especificamente, para cada aresta , seus pontos finais e são considerados adjacentes um ao outro, o que é denotado por ~ . ${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle (x, y)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle y}$

Gráfico misto

Um gráfico misto é um gráfico no qual algumas arestas podem ser direcionadas e outras não direcionadas. É um triplo ordenado G = ( V , E , A ) para um gráfico simples misto e G = ( V , E , A , ϕ _E , ϕ _A ) para um multigrafo misto com V , E (as arestas não direcionadas), A (as arestas direcionadas), ϕ _E e ϕ _A definidos como acima. Gráficos direcionados e não direcionados são casos especiais.

Gráfico ponderado

Um gráfico ponderado com dez vértices e doze arestas.

Um gráfico ponderado ou rede é um gráfico no qual um número (o peso) é atribuído a cada aresta. Esses pesos podem representar, por exemplo, custos, comprimentos ou capacidades, dependendo do problema em questão. Esses gráficos surgem em muitos contextos, por exemplo, em problemas do caminho mais curto , como o problema do caixeiro viajante .

Tipos de gráficos

Gráfico orientado

Uma definição de um gráfico orientado é que ele é um gráfico direcionado no qual no máximo um de ( x , y ) e ( y , x ) podem ser as arestas do gráfico. Ou seja, é um gráfico direcionado que pode ser formado como uma orientação de um gráfico não direcionado (simples).

Alguns autores usam "gráfico orientado" para significar o mesmo que "gráfico direcionado". Alguns autores usam "gráfico orientado" para significar qualquer orientação de um dado gráfico não direcionado ou multigrafo.

Gráfico regular

Um grafo regular é um grafo no qual cada vértice possui o mesmo número de vizinhos, ou seja, cada vértice possui o mesmo grau. Um gráfico regular com vértices de grau k é chamado de gráfico k ‑regular ou gráfico regular de grau k .

Gráfico completo

Um gráfico completo com cinco vértices e dez arestas. Cada vértice tem uma aresta para todos os outros vértices.

Um gráfico completo é um gráfico no qual cada par de vértices é unido por uma aresta. Um gráfico completo contém todas as arestas possíveis.

Gráfico finito

Um gráfico finito é um gráfico no qual o conjunto de vértices e o conjunto de arestas são conjuntos finitos . Caso contrário, é chamado de gráfico infinito .

Mais comumente, na teoria dos grafos, está implícito que os grafos discutidos são finitos. Se os gráficos são infinitos, isso geralmente é declarado de forma específica.

Gráfico conectado

Em um gráfico não direcionado, um par não ordenado de vértices { x , y } é chamado de conectado se um caminho leva de x a y . Caso contrário, o par não ordenado é chamado de desconectado .

Um gráfico conectado é um gráfico não direcionado no qual cada par não ordenado de vértices do gráfico está conectado. Caso contrário, é chamado de gráfico desconectado .

Em um gráfico direcionado, um par ordenado de vértices ( x , y ) é chamado de fortemente conectado se um caminho direcionado conduz de x para y . Caso contrário, o par ordenado é chamado de fracamente conectado se um caminho não direcionado levar de x para y após substituir todas as suas arestas direcionadas por arestas não direcionadas. Caso contrário, o par ordenado é denominado desconectado .

Um gráfico fortemente conectado é um gráfico direcionado no qual cada par ordenado de vértices no gráfico está fortemente conectado. Caso contrário, é chamado de gráfico fracamente conectado se cada par ordenado de vértices no gráfico estiver fracamente conectado. Caso contrário, é chamado de gráfico desconectado .

Um grafo conectado ao vértice k ou um grafo conectado à aresta é um grafo no qual não existe nenhum conjunto de k - 1 vértices (respectivamente, arestas) que, quando removido, desconecta o grafo. Um gráfico conectado por k -vértice geralmente é chamado simplesmente de gráfico conectado por k .

Gráfico bipartido

Um grafo bipartido é um grafo simples no qual o conjunto de vértices pode ser particionado em dois conjuntos, W e X , de forma que nenhum dos dois vértices em W compartilhe uma aresta comum e nenhum dos dois vértices em X compartilhe uma aresta comum. Como alternativa, é um gráfico com um número cromático de 2.

Em um gráfico bipartido completo , o conjunto de vértice é a união de dois conjuntos disjuntos, W e X , de modo que todos os vértices de W é adjacente a cada vértice em X , mas não há bordas dentro W ou X .

Gráfico de caminho

Um gráfico de caminho ou gráfico linear de ordem n ≥ 2 é um gráfico no qual os vértices podem ser listados em uma ordem v ₁ , v ₂ , ..., v _{n de} modo que as arestas são { v _i , v _{i +1} } onde i = 1, 2, ..., n - 1. Os gráficos de caminho podem ser caracterizados como gráficos conectados em que o grau de todos, exceto dois vértices é 2 e o grau dos dois vértices restantes é 1. Se um gráfico de caminho ocorre como um subgrafo de outro gráfico, é um caminho nesse gráfico.

Gráfico plano

Um grafo plano é um grafo cujos vértices e arestas podem ser desenhados em um plano tal que nenhuma das arestas se cruzem.

Gráfico de ciclo

Um gráfico de ciclo ou gráfico circular de ordem n ≥ 3 é um gráfico no qual os vértices podem ser listados em uma ordem v ₁ , v ₂ , ..., v _{n de} modo que as arestas são { v _i , v _{i +1} } onde i = 1, 2,…, n - 1, mais a aresta { v _n , v ₁ } . Os gráficos de ciclo podem ser caracterizados como gráficos conectados nos quais o grau de todos os vértices é 2. Se um gráfico de ciclo ocorre como um subgráfico de outro gráfico, é um ciclo ou circuito nesse gráfico.

Árvore

Uma árvore é um grafo não direcionado no qual quaisquer dois vértices são conectados por exatamente um caminho , ou equivalentemente um grafo não direcionado acíclico conectado .

Uma floresta é um grafo não direcionado no qual quaisquer dois vértices são conectados por no máximo um caminho, ou equivalentemente um grafo não direcionado acíclico, ou equivalentemente uma união disjunta de árvores.

Polytree

Um poliárvore (ou árvore dirigida ou árvore orientada ou rede ligada isoladamente ) é um gráfico acíclico dirigido (DAG) cuja subjacente gráfico não dirigida é uma árvore.

Um polyforest (ou floresta dirigida ou floresta orientada ) é um gráfico acíclico dirigido cujo subjacente gráfico não dirigida é uma floresta.

Aulas avançadas

Os tipos mais avançados de gráficos são:

• Gráfico de Petersen e suas generalizações;
• gráficos perfeitos ;
• cografias ;
• gráficos de cordas ;
• outros gráficos com grandes grupos automorfismos : vértice-transitivo , arco-transitória , e gráficos de distância-transitivo ;
• gráficos fortemente regulares e suas generalizações gráficos regulares de distância .

Propriedades dos gráficos

Duas arestas de um gráfico são chamadas de adjacentes se compartilham um vértice comum. Duas arestas de um gráfico direcionado são chamadas de consecutivas se a ponta da primeira for a cauda da segunda. Da mesma forma, dois vértices são chamados de adjacentes se eles compartilham uma aresta comum ( consecutivos se o primeiro é a cauda e o segundo é a cabeça de uma aresta), caso em que a aresta comum é dita que une os dois vértices. Uma aresta e um vértice nessa aresta são chamados de incidente .

O gráfico com apenas um vértice e sem arestas é chamado de gráfico trivial . Um gráfico com apenas vértices e sem arestas é conhecido como gráfico sem arestas . O gráfico sem vértices e sem arestas às vezes é chamado de gráfico nulo ou gráfico vazio , mas a terminologia não é consistente e nem todos os matemáticos permitem esse objeto.

Normalmente, os vértices de um gráfico, por sua natureza como elementos de um conjunto, são distinguíveis. Este tipo de gráfico pode ser denominado rotulado por vértices . No entanto, para muitas questões, é melhor tratar os vértices como indistinguíveis. (Claro, os vértices podem ainda ser distinguíveis pelas propriedades do próprio gráfico, por exemplo, pelo número de arestas incidentes.) As mesmas observações se aplicam às arestas, então os gráficos com arestas rotuladas são chamados de arestas rotuladas . Os gráficos com rótulos anexados às arestas ou vértices são mais geralmente designados como rotulados . Conseqüentemente, os gráficos nos quais os vértices são indistinguíveis e as arestas são indistinguíveis são chamados de não rotulados . (Na literatura, o termo rotulado pode se aplicar a outros tipos de rotulagem, além daquele que serve apenas para distinguir diferentes vértices ou arestas.)

A categoria de todos os gráficos é a categoria de vírgula Set ↓ D onde D : Set → Set é o functor que transforma um conjunto s em s × s .

Exemplos

Um gráfico com seis vértices e sete arestas.

• O diagrama é uma representação esquemática do gráfico com vértices e arestas${\ displaystyle V = \ {1,2,3,4,5,6 \}}$${\ displaystyle E = \ {\ {1,2 \}, \ {1,5 \}, \ {2,3 \}, \ {2,5 \}, \ {3,4 \}, \ {4 , 5 \}, \ {4,6 \} \}.}$
• Na ciência da computação , os gráficos direcionados são usados ​​para representar o conhecimento (por exemplo, gráfico conceitual ), máquinas de estado finito e muitas outras estruturas discretas.
• Uma relação binária R em um conjunto X define um grafo direcionado. Um elemento x de X é um predecessor direto de um elemento y de X se e somente se xRy .
• Um gráfico direcionado pode modelar redes de informação como o Twitter , com um usuário seguindo o outro.
• Exemplos particularmente regulares de gráficos direcionados são dados pelos gráficos Cayley de grupos gerados finitamente, bem como pelos gráficos coset de Schreier
• Na teoria das categorias , cada pequena categoria tem um multigrafo dirigido subjacente cujos vértices são os objetos da categoria e cujas arestas são as setas da categoria. Na linguagem da teoria das categorias, diz-se que existe um functor esquecido da categoria de pequenas categorias para a categoria de aljavas .

Operações de gráfico

Existem várias operações que produzem novos gráficos a partir dos iniciais, que podem ser classificados nas seguintes categorias:

• operações unárias , que criam um novo gráfico a partir de um gráfico inicial, como:
  • contração de borda ,
  • gráfico de linha ,
  • gráfico duplo ,
  • complemento gráfico ,
  • reescrita de gráficos ;
• operações binárias , que criam um novo gráfico a partir de dois gráficos iniciais, como:
  • união disjunta de gráficos ,
  • produto cartesiano de gráficos ,
  • produto tensorial dos gráficos ,
  • forte produto de gráficos ,
  • produto lexicográfico de gráficos ,
  • gráficos de séries paralelas .

Generalizações

Em um hipergrafo , uma aresta pode unir mais de dois vértices.

Um grafo não direcionado pode ser visto como um complexo simplicial consistindo de 1- simplicos (as arestas) e 0-simplicos (os vértices). Como tal, os complexos são generalizações de gráficos, uma vez que permitem simplicidades de dimensões superiores.

Cada gráfico dá origem a uma matróide .

Na teoria do modelo , um gráfico é apenas uma estrutura . Mas, nesse caso, não há limitação no número de arestas: pode ser qualquer número cardinal , consulte o gráfico contínuo .

Em biologia computacional , a análise de gráfico de potência apresenta os gráficos de potência como uma representação alternativa de gráficos não direcionados.

Em sistemas de informações geográficas , as redes geométricas são modeladas de perto com base em gráficos e emprestam muitos conceitos da teoria dos grafos para realizar análises espaciais em redes rodoviárias ou de serviços públicos.

Veja também

• Gráfico conceitual
• Gráfico (tipo de dados abstratos)
• Banco de dados gráfico
• Desenho gráfico
• Lista de tópicos de teoria dos grafos
• Lista de publicações em teoria dos grafos
• Teoria da rede

Notas

Referências

• Balakrishnan, VK (1997). Teoria de grafos (1ª ed.). McGraw-Hill. ISBN 978-0-07-005489-9.
• Bang-Jensen, J .; Gutin, G. (2000). Dígrafos: Teoria, Algoritmos e Aplicações . Springer.
• Bender, Edward A .; Williamson, S. Gill (2010). Listas, decisões e gráficos. Com uma introdução à probabilidade .
• Berge, Claude (1958). Théorie des graphes et ses applications (em francês). Paris: Dunod.
• Biggs, Norman (1993). Algebraic Graph Theory (2ª ed.). Cambridge University Press. ISBN 978-0-521-45897-9.
• Bollobás, Béla (2002). Modern Graph Theory (1ª ed.). Springer. ISBN 978-0-387-98488-9.
• Diestel, Reinhard (2005). Graph Theory (3ª ed.). Berlim, Nova York: Springer-Verlag. ISBN 978-3-540-26183-4.
• Graham, RL; Grötschel, M .; Lovász, L. (1995). Handbook of Combinatorics . MIT Press. ISBN 978-0-262-07169-7.
• Gross, Jonathan L .; Yellen, Jay (1998). Teoria dos grafos e suas aplicações . CRC Press. ISBN 978-0-8493-3982-0.
• Gross, Jonathan L .; Yellen, Jay (2003). Handbook of Graph Theory . CRC. ISBN 978-1-58488-090-5.
• Harary, Frank (1995). Teoria dos grafos . Addison Wesley Publishing Company. ISBN 978-0-201-41033-4.
• Iyanaga, Shôkichi; Kawada, Yukiyosi (1977). Dicionário Enciclopédico de Matemática . MIT Press. ISBN 978-0-262-09016-2.
• Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulas (31ª ed.). Chapman & Hall / CRC. ISBN 978-1-58488-291-6.

Leitura adicional

• Trudeau, Richard J. (1993). Introdução à teoria de grafos (republicação corrigida e ampliada. Ed.). Nova York: Dover Publications . ISBN 978-0-486-67870-2. Retirado em 8 de agosto de 2012 .

links externos

• Mídia relacionada a Graph (matemática discreta) no Wikimedia Commons
• Weisstein, Eric W. "Graph" . MathWorld .