𝖂𝖎ƙ𝖎𝖊

Teoria dos grafos: mudanças entre as edições

imported>Jorge~ptwiki
(=Glossário dos conceitos básicos de Teoria dos Grafos=)
imported>Jorge~ptwiki
(=Glossário dos conceitos básicos de Teoria dos Grafos=)
(Sem diferença)

Edição das 17h07min de 3 de maio de 2004

Predefinição:Emtraducao2

A Teoria dos Grafos é o ramo da matemática que estuda as propriedades de grafos.

6n-graf.png
Um grafo com 6 vértices e 7 arestas.

Um grafo é um conjunto de pontos, chamados vértices (ou nodos), conectados por linhas, chamadas de arestas (ou arcos). A nomenclatura de nodos e arcos está caindo em desuso.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, ou dígrafo.

Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial ou "o ponto".

Estruturas que podem ser representadas por grafos estão em toda parte, e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de links da Wikipedia pode ser representada por um dígrafo: os vértices são os artigos da Wikipedia e existe uma aresta do artigo A para o artigo B se e somente se A contém um link para B. Dígrafos são também usados para representar máquinas de estado finito. O desenvolvimento de algoritmos para manipular grafos é um importante tema da ciência da computação.

Histórico

O artigo de Leonhard Euler em Sete Pontes de Königsberg é considerado o primeiro resultado da teoria dos grafos. É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia.

Definições de Grafos e Dígrafos

Na literatura, as definições básicas da teoria dos grafos variam bastante. Aqui estão as convenções usadas nesta enciclopédia.

Um grafo direccionado (também chamado digrafo ou quiver) consiste de

um conjunto V de vértices,
um conjunto E de arestas e
mapas s, t : E → V, onde s(e) é a fonte e t(e) é o alvo da aresta direccionada e.

Um grafo não direccionado (ou simplesmente grafo) é dado por

um conjunto V de vértices,
um conjunto E de arestas e
uma função w : E → P(V) que associa a cada aresta um subconjunto de dois ou de um elemento de V, interpretado como os pontos terminais da aresta.

Em um grafo ou dígrafo com pesos, uma função uma função adicional E → R associa um valor a cada aresta, o que pode ser considerado seu "custo"; tais grafos surgem em problemas de rota ótima tais como o problema do Caixeiro viajante.

Representação "gráfica" (layout do grafo)

Os grafos são geralmente representados "graficamente" da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades. Se o grafo for direcionado, seu sentido é indicado na aresta por uma seta.

Note que essa representação gráfica (o layout) não deve ser confundida com o grafo em si (a estrutura abstrata, não-gráfica). Vários diferentes layouts podem corresponder ao mesmo grafo (ver http://www.aisee.com/gallery/graph23.htm). O que importe é quais vértices estão conectados entre si por quantas arestas.

Seguem alguns exemplos de layouts de grafos:

Glossário dos conceitos básicos de Teoria dos Grafos

Um laço (loop) num grafo ou num digrafo é uma aresta e em E cujas terminações estão no mesmo vértice. Um digrafo ou grafo é chamado simples se não tem laços e existe no máximo uma aresta entre quaisquer dois vértices.

6n-graf.png

O grafo de exemplo exibido à direita é um grafo simples com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um conjunto de arestas E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} (com o mapeamento w sendo a identidade).

Uma aresta conecta dois vértices; esses dois vértices são ditos como incidentes à aresta. A valência (ou grau_ de um vértice é um vértice é o número de arestas incidentes a ele, com loops contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. Se E é finito, então a valência total dos vértices é o dobro do númeero de arestas. Em um dígrafo, distingue-se o grau de saída (=o número de arestas saindo de um vértice) e o grau de entrada (=o número de arestas entrando em um vértice). O grau de um vértice é igual à some dos graus de saída e de entrada.

Dois vértices são considerados adjacentes se uma aresta existe entre eles. No grafo acima, os vértices 1 e 2 são adjacentes, mas os vértices 2 e 4 não são. O conjunto de vizinhos de um vértice consiste de todos os vértices adjacentes a ele. No grafo-exemplo, o vértice 1 possui 2 vizinhos: vértice 2 and node 5. Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.

Na computação, um grafo finito direcionado ou não-direcionado (com, digamos, n vértices) é geralmente representado por sua matriz de adjacência: uma matriz n-por-n cujo valor na linha i e coluna j fornece o número de arestas do i-ésimo ao j-ésimo vértices.

Um caminho é uma sequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum dos vértices no caminho se repete. O comprimento do caminho é o número de arestas que o caminho usa, contando-se arestas múltiplas múltiplas vezes. O custo de um caminho num grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos são independentes se não tiverem nenhum vértice em comum, excepto o primeiro e o último.

No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.

Se for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo, diz-se que o grafo é ligado. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de remover k-1 vértices, então diz-se que o grafo está k-ligado. Note que um grafo está k-ligado se e só se contém k caminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é ligado (e portanto 1-ligado), mas não é 2-ligado.

Um ciclo (ou circuito) é um caminho que começa e acaba com o mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6. Um ciclo simples é um ciclo que tem um comprimento pelo menos de 3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um grafo chama-se acíclico se não contém ciclos simples.

Um ponto de articulação é um vértice cuja remoção desliga um grafo. Uma ponte é uma aresta cuja remoção desliga um grafo. Um componente biconectado é um conjunto máximo de arestas tal que qualquer par de arestas do conjunto fazem parte de um ciclo simples comum. O contorno de um grafo é o comprimento do ciclo simples mais curto no grafo. O contorno de um grafo acíclico é, por definição, infinito.

A tree is a connected acyclic simple graph. Sometimes, one vertex of the tree is distinguished, and called the root. Trees are commonly used as data structures in computer science (see tree data structure).

A forest is a set of trees; equivalently, a forest is any acyclic graph.

A subgraph of the graph G is a graph whose vertex set is a subset of the vertex set of G, whose edge set is a subset of the edge set of G, and such that the map w is the restriction of the map from G.

Um subgrafo de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arstas de G, e cuja função w é uma restrição da função de G.

A spanning subgraph of a graph G is a subgraph with the same vertex set as G. A spanning tree is a spanning subgraph that is a tree. Every graph has a spanning tree.

A complete graph is a simple graph in which every vertex is adjacent to every other vertex. The example graph is not complete. The complete graph on n vertices is often denoted by Kn. It has n(n-1)/2 edges (corresponding to all possible choices of pairs of vertices).

A planar graph is one which can be drawn in the plane without any two edges intersecting. The example graph is planar; the complete graph on n vertices, for n> 4, is not planar.

An Eulerian path in a graph is a path that uses each edge precisely once. If such a path exists, the graph is called traversable. An Eulerian cycle is a cycle with uses each edge precisely once. There is a dual to this concept: a Hamiltonian path in a graph is a path that visits each vertex once and only once; and a Hamiltonian cycle is a cycle which visits each vertex once and only once. The example graph does not contain an Eulerian path, but it does contain a Hamiltonian path. While determining whether a given graph has an Eulerian path or cycle is trivial, the same problem for Hamiltonian paths and cycles is extremely hard.

The null graph is the graph whose edge set and vertex set are empty.

An independent set in a graph is a set of pairwise nonadjacent vertices. In the example above, vertices 1,3, and 6 form an independent set and 3,5, and 6 are another independent set.

A clique (pronounced "click") in a graph is a set of pairwise adjacent vertices. In the example graph above, vertices 1, 2 and 5 form a clique.

A bipartite graph is any graph whose vertices can be divided into two sets, such that there are no edges between vertices of the same set. A graph can be proved bipartite if there do not exist any circuits of odd length.

A k-partite graph or k-colorable graph is a graph whose vertices can be partitioned into k disjoint subsets such that there are no edges between vertices in the same subset. A 2-partite graph is the same as a bipartite graph.

Problemas que envolvem grafos

  • Problemas de Isomorfismo (casamento de grafos)
    • Canonical Labeling
    • subgraph isomorphism and monomorphisms
    • Maximal common subgraph

Algoritmos Importantes

Generalizações

In a hypergraph an edge can connect more than two vertices.

An undirected graph can be seen as a simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices.

Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs.


Num hypergraph uma aresta pode conectar mais que dois grafos.

Um grafo não-direcionado pode ser visto como um simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices.

Todo grafo gera uma matroide, mas em geral o grafo não pode ser recuperado da sua matróide, logo, matroides não são generelizações reais de grafos.

Popular graph layout tools


Áreas afins na Matemática

See also

External links

de:Graphentheorie en:Graph theory eo:Grafeteorio es:Teoría de los grafos fr:Théorie des graphes he:תורת הגרפים ja:グラフ理論 nl:Grafentheorie pl:Teoria grafów simple:Graph theory sv:Grafteori tr:Çizge Teorisi zh:图论

talvez você goste

Permaneça conectado

Parceiros

Dieta Cetogenica | NutriPro Saúde